Estudo experimental, modelagem e implementação do comportamento de colônias de formigas em um ambiente dinâmico

Autor(es)

Karla Vittori

• Tipo de documento: Tese de Doutorado
• Imprenta: São Carlos.
• Instituição: Universidade de São Paulo (USP). Escola de Engenharia de São Carlos (EESC/SBD)
• Data de defesa: 2005-06-27

Membros da banca

Aluízio Fausto Ribeiro Araújo; André Carlos Ponce de Leon Ferreira de Carvalho; Alexandre Cláudio Botazzo Delbem; Heitor Silvério Lopes; Leandro Nunes de Castro Silva

• Orientador: Aluízio Fausto Ribeiro Araújo

Resumo

O comportamento de insetos sociais, em especial de formigas, tem sido muito estudado nos últimos tempos, devido à capacidade destes insetos realizarem tarefas complexas a partir de interações entre indivíduos simples. Ao se moverem sobre um ambiente na busca de alimento, as formigas depositam no solo uma substância química, denominada feromônio, que atrai as formigas que se encontram no ninho e as guia em direção ao alimento encontrado. O processo de construção e seguimento destas trilhas permite que as formigas descubram os menores caminhos e as melhores fontes de alimento no ambiente. Com o objetivo de estudar as características das formigas que contribuem para a sua adaptação a diferentes condições do meio, diversos experimentos vêm sendo realizados com estes insetos. Dentro deste contexto, esta tese apresenta experimentos inéditos realizados com formigas em laboratório, sobre uma rede artificial de túneis, onde diversos caminhos interconectados conduzem a uma fonte de alimento. As decisões das formigas foram analisadas nos níveis individual e coletivo, sob mudanças no meio, compreendendo o bloqueio/desbloqueio de ramos. A medição de diversas características individuais das formigas permitiu desenvolver dois modelos matemáticos sobre o seu comportamento, que foram aplicados à situação em que não se alterou a condição do ambiente com relação ao acesso aos ramos (estática), como também a mudanças no meio (dinâmica). A análise realizada do comportamento coletivo foi utilizada na comparação dos resultados obtidos pelas simulações dos modelos. De forma geral, o segundo modelo proposto foi mais eficiente que o primeiro na situação estática, porém ele ainda necessita de ajustes nas demais situações. O bom desempenho do segundo modelo proposto levou a aplicação de sua principal característica, a função de escolha que considera a concentração de feromônio sobre os ramos do meio e a capacidade de orientação das formigas, a um problema de otimização combinatorial, o roteamento em redes de telecomunicações. O algoritmo de roteamento proposto foi avaliado sob variações no nível de tráfego e topologia da rede, e seu desempenho foi comparado ao de dois algoritmos usados por concessionárias de telecomunicações, considerando diversas medidas de desempenho. O algoritmo desenvolvido obteve resultados encorajadores, sugerindo a aplicabilidade da estrutura do modelo proposto a outros problemas complexos de otimização. (AU)

• Processo FAPESP: 00/08251-2 - Aprendizagem-q e comportamento de colonias de formigas em roteamento de redes de telecomunicacoes.
• Beneficiário: Karla Vittori
• Modalidade de apoio: Bolsas no Brasil - Doutorado