Algoritmo Colonia de Formigas

Algoritmo Colônia de Formigas:

O Algoritmo Colônia de Formigas é baseado no comportamento das formigas à procura de alimento. A organização das formigas funciona da seguinte forma:

 Em geral, as formigas seguem o menor caminho entre o formigueiro e sua fonte de alimento.

 Enquanto andam, as formigas depositam no solo uma substância chamada feromônio.

 Na presença de feromônio, elas possuem certa tendência a seguir o caminho marcado com a substância.

 Essa tendência é baseada na quantidade de feromônio presente em cada caminho: quanto maior concentração, maior a chance da trilha ser seguida.

 Inicialmente, como não há feromônio nos caminhos, as formigas andam aleatoriamente em busca de alimento.

 As formigas que escolhem (ao acaso) o menor caminho voltam por ele.

 Como a ida e a volta são mais rápidas, há um pouco mais de feromônio nesse caminho.

 Como essa trilha possui mais feromônio, outras formigas tendem a segui-la.

 Com isso, o feromônio na trilha irá aumentar.

 Com o passar do tempo, os menores caminhos recebem uma carga maior de feromônio, sendo escolhidos pelas formigas.

 O feromônio também evapora com o tempo.

 Dessa forma, os caminhos menos visitados perdem feromônio, levando as formigas aos caminhos escolhidos pelas demais.

Os algoritmos de colônias de formigas:

 São aplicados a problemas representados por um grafo G(V, A).
 São algoritmos de construção: a cada iteração, cada formiga, individualmente, constrói uma solução para o problema.
 São algoritmos que, a cada iteração, trabalham com uma população de formigas (e, portanto, com uma população de soluções).

Na construção da solução, a formiga leva em conta:

 Informações heurísticas (fixas), que indicam a conveniência, para a obtenção da solução do problema, de se tomar determinado caminho.
 A quantidade de feromônio (variável), que indica quão desejável é um determinado caminho.