Heuristicas2

UNIVERSIDADE FEDERAL DE GOIÁS
ESCOLA DE ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO
PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO

JULIANO ADORNO MAIA
RAMON DE FREITAS ELIAS CAMPOS
RENATO DE SOUSA GOMIDE

GOIÂNIA, JUNHO DE 2010
ESTUDO DO ALGORITMO DE OTIMIZAÇÃO DA COLÔNIA DE FORMIGAS

RESUMO
Alguns problemas de otimização como os de roteamento podem ser solucionados através de métodos heurísticos, como o sistema de colônias de insetos sociais. Neste será realizados testes com diferentes configurações para se obter uma analise do comportamento computacional e de satisfação dos resultados utilizando o algoritmo em questão.

PALAVRAS-CHAVE caixeiro viajante; colônia de formigas; convergência; otimização; roteamento.

INTRODUÇÃO O algoritmo de colônias de formigas foi baseado em observações feitas por pesquisadores que analisaram o comportamento de colônias do mundo real. Esses seres por sua vez são classificados como insetos sociais, ou seja, que necessitam de viver em conjunto e não individualmente, prezando sempre a coletividade à individualidade. Nos problemas de roteamento como por exemplo, o PCV (Problema do Caixeiro Viajante), a utilização de algoritmos baseados em colônias de formiga pode ser uma grande ferramenta para a otimização destes, pois uma formiga real quase não enxerga e esta utiliza do ferormônio de suas companheiras para se guiar e executar uma determinada rota, pois esses insetos sempre andam juntos. Com isso as que irão à frente, ao alcançar um caminho menor do que outras formigas até o objetivo determinado emitirá um ferormônio mais constante do que as que foram pelo caminho mais longe, atraindo desta maneira os outros indivíduos desta população irem por este caminho menor. (ROMERO, 2004) Este trabalho tem como objetivo realizar o estudo do algoritmo de otimização da colônia de formigas procurando uma solução ótima para o problema do caixeiro viajante.
1 ALGORITMO DE OTIMIZAÇÃO DA COLÔNIA DE FORMIGAS Esta seção aborda a