COMPORTAMENTO DE FORMIGAS

CHRISTIANE WENCK NOGUEIRA

•VIDA ARTIFICIAL•OTIMIZAÇÃO ATRAVÉSDE COLÔNIAS DE FORMIGAS

-Soluções para uma variedade de problemas baseiam-se nos chamados sistemas-formigueiros, modelos computacionaisem que os algoritmos são inspirados no comportamento decolônias de formigas.

-Trata-se de uma área recente, desenvolvida a partir de 95, no âmbito da chamada Inteligência de Enxame ,um campo da investigação científica em vida artificial.

-Os desenvolvimentos nestas áreas têm levado à conclusão de que os fenômenos complexos podem resultar da interação simultânea entre múltiplos mecanismos simples.

COMPORTAMENTO DE FORMIGAS

O campo dos “algoritmos formiga” estuda modelos derivados das observações do comportamento das formigas reais e utiliza esses modelos como fonte de inspiração para o “design” de novos algoritmos em problemas de otimização.

Vários comportamentos das colônias de formigas inspiraram soluções para diferentes problemas (recolher alimentos, divisão do trabalho, transporte cooperativo, agrupamento das crias, reconhecimento colonial, etc).

Colônias de Formigas

- Dois físicos, Dante Chialvo e Mark Millonas em 1995, construíram um modelo algorítmico que conseguiu reproduzir o comportamento das colônias de formigas na formação de carreiros.

Colônias de Formigas

Colônias de Formigas

As colônias de formigas são sistemas distribuídos que apresentam organizações sociais altamente estruturadas independentemente da simplicidade ao nível individual.

Os princípios da auto-organização que permitem o comportamento coordenado das formigas, podem ser explorados para resolver diversos problemas.

Estigmergia: É a estimulação das operárias através da “performance” de realização. As térmitas são capazes de criar bolas de lama para construírem os ninhos, impregnam essas bolas de lama com feromônios e largam-nas no chão. As térmitas são atraídas pelo feromônio e assim, depositam bolas de lama perto umas das outras, construindo pilares, arcos, túneis e câmaras.

Pierre-Paul Grassé,1959.

Colônias de Formigas

A importância da estgmergia está no fato da comunicação estar mediada por modificações físicas dos estados do meio-ambiente, os quais só são localmente acessíveis pelos agentes.

O comportamento de recolher alimentos de muitas sociedades de formigas baseia-se na comunicação indireta mediada por feromônios (estigmergia através de marcas).

Colônias de Formigas

Colônias de Formigas

Emergência de um trilho

Enquanto caminham as formigas depositam feromônios no chão, formando um trilho de feromônio.

As formigas são capazes de perceber o químico e tendem a escolher, de modo probabilístico, caminhos onde haja maior concentração de químico.

O trilho químico, é uma estrutura emergente e auto-organizada e resulta do “feedback” positivo. Quanto mais químico, mais formigas são atraídas e ainda mais químico, reforçando-se o trilho que atrai ainda mais formigas.

Colônias de Formigas

Colônias de FormigasExperiência da ponte bifurcada (Deneubourg,1958)

Colônias de Formigas

Ponte entre o ninho e a fonte de comida, com dois ramos de igual comprimento. As formigas acabam por escolher um único dos dois caminhos, aleatoriamente, depois de uma fase inicial transitória

Explicação: Não há preferência inicial mas pequenas flutuações iniciais poderão ser ampliadas dando origem a preferência por um dos caminhos.

Experiência da ponte bifurcada (Deneubourg,1958)

•O “Feedback” Negativo remove da memória coletiva (exterior) as soluções antigas e as más soluções;

•Evaporação do Feromônio:O desaparecimento da comida + evaporação impedem que um lugar esgotado continue a ser procurado;

•As fontes de alimentação mais distantes são exploradas depois das mais curtas.O Feromônio tem menos tempo para se evaporar nas soluções mais curtas.

Colônias de Formigas

A aleatoriedade permite que novas soluções sejam procuradas e guia a exploração das soluções atuais;

As decisões das formigas são probabilísticas;

As fontes de comida são encontradas de modo aleatório.

Nenhum indivíduo pode resolver um problema. Só através da interação de muitos é que a solução pode ser encontrada.

Uma única formiga não pode “recolher” comida. O feromônio evaporar-se-ia rapidamente.

Colônias de Formigas

A idéia do que foi apresentado é utilizar uma forma artificial para caracterizar agentes autônomos;

As características da estigmergia podem ser estendidas aos agentes através de

(i) associar variáveis aos estados do problema e

(ii) dar aos agentes um acesso a essas variáveis.

Colônias de Formigas

Modo Para o açúcar As formigas para a frente constroem uma solução

escolhendo probabilisticamente o próximo passo entre as possibilidades em sua volta.

Devido as diferenças entre os caminhos das formigas, o instante temporal em que as diversas formigas atingem o objetivo difere de formiga para formiga.(As formigas que escolham caminhos mais curtos chegarão mais depressa).

Colônias de Formigas

Modo Regresso

As formigas no modo de regresso,devido a memória do caminho percorrido, refazem o mesmo caminho, desde o açúcar até o ninho.

As formigas utilizam o sol como referência. A engenhosa "Catagliphys bicolor" usa sua parte traseira para se orientar através da sensibilidade à luz solar, tomando-a como referência para encontrar o caminho de casa.

Colônias de Formigas

Colônias de Formigas

Formiga "conta passos" para voltar ao ninho, estudo de 30 de junho de 2006,pesquisadores da Universidade de Ulm, na Alemanha, e de Zurique, na Suíça .

-Usaram pernas de pau para alongar pernas de formigas

-Eles já sabiam que as formigas do Saara se orientavam pelas dunas desérticas através de uma espécie de “bússola interna”, funcionando a partir da luz solar. A dúvida era sobre como os insetos se relacionavam com as distâncias.

Colônias de Formigas

-Fizeram as formigas caminhar até alcançar a comida.

-Para o trajeto de volta, no entanto, os pesquisadores mudaram o comprimento das pernas das cobaias: partedo grupo teve as pernas parcialmente amputadas; a outra parte teve as pernas alongadas com pernas de pau.

Colônias de Formigas

- Na experiência, as formigas com pernas mais longascaminharam uma distância mais longa para voltarà casa; já os insetos com pernas mais curtasencerraram seu trajeto antes de chegar ao ponto de origem.

-Os pesquisadores concluíram que as formigas “contavam” os passos da ida para medir a distância na volta.

-Tanto que os insetos que caminharam a ida e a voltacom pernas mais curtas ou mais longas conseguiram julgar com bastante precisão a distância entre o ninho e a comida.

PROGRAMA DELPHI

-PONTO DE REFERÊNCIA ÀS FOMIGAS – SOL;

-RETORNAR AO NINHO NÃO DE MANEIRA ALEATÓRIA;

-RETORNAR PELO MESMO CAMINHO QUE FORAM(CONTAR OS PASSOS);

-QUANTO MAIOR O NÚMERO DE FORMIGAS MELHORSERÁ A PERFORMANCE DO PROGRAMA EM RELAÇÃOAO TEMPO PARA FORMAREM O “CARREIRO”.