Colônia de formigas (otimização)

O algoritmo da otimização da colônia de formigas (ACO, do inglês ant colony optimization algorithm), introduzido por Marco Dorigo em sua tese de PhD é uma heurística baseada em probabilidade, criada para solução de problemas computacionais que envolvem procura de caminhos em grafos. Este algoritmo foi inspirado na observação do comportamento das formigas ao saírem de sua colônia para encontrar comida.

Visão geral

No mundo real, as formigas andam sem rumo (pelo menos inicialmente) até que, encontrada comida, elas retornam à colônia deixando um rastro de feromônio. Se outras formigas encontram um desses rastros, elas tendem a não seguir mais caminhos aleatórios. Em vez disso, seguem a trilha encontrada, retornando e inclusive enfatizando se acharam alimento.

Com o transcorrer do tempo, entretanto, as trilhas de feromônio começam a evaporar, reduzindo, assim, sua força atrativa. Quanto mais formigas passarem por um caminho predeterminado, mais tempo será necessário para o feromônio da trilha evaporar. Analogamente, elas marcharão mais rapidamente por sobre um caminho curto, o que implica aumento da densidade de feromônio depositado antes que ele comece a evaporar. A evaporação do feromônio também possui a vantagem de evitar a convergência para uma solução local ótima: se a evaporação não procedesse, todas as trilhas escolhidas pelas primeiras formigas tornar-se-iam excessivamente atrativas para as outras e, neste caso, a exploração do espaço da solução delimitar-se-ia consideravelmente.

Todavia, quando uma formiga encontra um bom (curto) caminho entre a colônia e a fonte de alimento, outras formigas tenderão a seguir este caminho, gerando assim feedback positivo, o que eventualmente torna um determinado caminho mais interessante. A ideia do algoritmo da colônia de formigas é imitar este comportamento através de "formigas virtuais" que caminham por um grafo que por sua vez representa o problema a ser resolvido.

O ACO tem sido utilizado para produzir soluções quase ótimas para o problema do caixeiro viajante. Este algoritmo apresenta uma vantagem sobre o algoritmo de arrefecimento simulado (simulated annealing) e o algoritmo genético, se o grafo muda dinamicamente. A colônia de formigas pode mudar várias vezes e se adaptar às mudanças em tempo real. É de grande interesse para soluções de problemas em sistemas de roteamento de redes de computadores e transporte urbano.

Métodos relacionados

Algoritmos genéticos mantêm um grupo de soluções, e não uma única. O processo de busca de soluções superiores imita o processo de seleção natural, com combinações ou mutações aplicadas às soluções para que possam alterar o grupo, através do descarte das soluções de qualidade inferior. O arrefecimento simulado é uma técnica heurística que percorre o espaço de busca através da geração de soluções vizinhas à solução atual. Um vizinho "melhor" sempre é aceito. Um "pior" é aceito probabilisticamente, baseado na diferença de qualidade e na temperatura em relação à solução atual. O parâmetro de temperatura é modificado à medida que o algoritmo progride ao alterar a natureza da pesquisa.

A técnica de busca tabu é similar ao arrefecimento simulado, uma vez que ambos transcorrem a solução testando mutações em soluções individuais. Contudo, enquanto a técnica de arrefecimento gera apenas uma solução modificada, a busca tabu gera várias e move-se para uma solução mais satisfatória, atendendo, para tanto, a algum critério predeterminado. Com o intuito de prevenir ciclos e encorajando maior movimentação através do espaço, uma lista de tabus das soluções parciais ou completas é mantida. É proibido mover-se para uma solução que contenha elementos presentes nesta lista, que por sua vez é atualizada assim que uma determinada solução transcorre todo o espaço. Pesquisa harmônica é um algoritmo baseado na analogia entre improvisação musical e otimização. Cada músico (variável) busca as melhores harmonias (vetores).

Publicações

M. Dorigo, 1992. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy.
M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26 (1): 29–41.
M. Dorigo & L. M. Gambardella, 1997. "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem". IEEE Transactions on Evolutionary Computation, 1 (1): 53–66.
M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Artificial Life, 5 (2): 137–172.
E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
M. Dorigo & T. Stützle, 2004. Ant Colony Optimization, MIT Press. ISBN 0-262-04219-3
M. Dorigo, 2007. "Ant Colony Optimization". Scholarpedia.

Colônia de formigas (otimização)

Índice

Visão geral

Métodos relacionados

Publicações

Ligações externas