Estudo comparativo de buscas aleatórias com distribuições de tamanhos de passos do tipo lei de potência, Lévy e exponenciais simples e dupla em uma e duas dimensões

Abstract

Nesta dissertação analisamos o problema da busca aleatória em uma e duas dimensões, em que o caminhante aleatório tem os tamanhos de seus passos com distribuições do tipo lei de potên- cia, Lévy e exponenciais simples e duplas. Em uma dimensão, consideramos um espaço finito de busca com extensão 𝐿, no qual o caminhante parte de uma posição 0 < 𝑥0 ≪ 𝐿 na busca por sítios alvos localizados nos extremos do intervalo, 𝑥 = 0 e 𝑥 = 𝐿. Em duas dimensões, em um espaço de busca 𝐿 × 𝐿, o caminhante parte de uma distância 𝑥0 ≪ 𝐿 do sítio mais próximo. Estudamos, então, a melhor estratégia para encontrar um desses alvos no regime de baixa densidade de sítios. O problema da otimização de buscas aleatórias possui várias aplicações, sendo uma das mais relevantes a busca de alimentos por animais ("animal foraging"). Nesse contexto, um novo impulso surgiu na década de 1990 pela aplicação da distribuição de Lévy para explicar a existência de longos passos, permitindo, assim, explorar diferentes regiões do espaço de busca de maneira mais eficiente, principalmente quando não se tem informações prévias sobre a localização dos sítios alvos. Observa-se, de fato, que quando o buscador não tem informações sobre o espaço de busca e inicia próximo a um sítio alvo a distribuição de Lévy com índice de estabilidade 𝛼 ≈ 1 apresenta a maior eficiência. Contudo, alguns trabalhos recentes questionam se a distribuição de Lévy ainda é a mais eficiente quando o buscador possui informações específicas a respeito de comprimentos típicos relevantes do sistema, tais como o espaçamento médio entre os sítios e a dimensão do espaço de busca. Nesse contexto, a distribuição exponencial dupla com escolhas dos comprimentos característicos 𝜏1 ≫ 𝐿 e 𝜏2 ≪ 𝐿 apresenta maior eficiência. No presente trabalho comparamos as eficiências de buscas uni e bidimensionais para distribuições de tamanhos de passos dos tipos exponencial simples, exponencial dupla, lei de potência (limite assintótico para grandes passos da distribuição de Lévy) e Lévy. Realizamos um estudo da eficiência máxima aumentando os valores de 𝐿 (isto é, tornando o ambiente mais escasso em sítios), utilizando simulações computacionais via método de Monte Carlo. Obtivemos, de fato, uma maior eficiência da busca aleatória para a distribuição exponencial dupla (com 𝜏1 ≫ 𝐿 e 𝜏2 ≪ 𝐿), seguida da lei de potência e por último a exponencial simples, tanto em uma quanto em duas dimensões. Verificamos que isso ocorre por causa da escolha específica de comprimentos característicos e pesos específicos para a exponencial dupla. No entanto, caso o buscador não tenha conhecimento prévio do espaço, tal escolha específica é muito pouco provável, e assim, na ausência de informações sobre o espaço de busca, a distribuição de Lévy permanece como a mais eficiente em buscas aleatórias em uma e duas dimensões.