AntColonySwarm: Simulação do
Comportamento de uma Colônia de
Formigas
Abner das Dores
Cláudio Antônio Peanho
Fabrizio Ferreira Borelli
Maitê Balhester
Rafael Munhoz
Vida Artificial na Computação
Profª Karla Vittori
Sumário
• Inteligência Coletiva
▫ Insetos Sociais
• As Formigas na Natureza
▫
▫
▫
▫
Busca por Alimento
Estigmergia
Experimento da Ponte Binária
Efeito da Diferença de Comprimentro entre Dois
Caminhos
▫ Auto-organização
• Simulação
Inteligência Coletiva
• É definida como a propriedade de um sistema
onde o comportamento de vários agentes
simples interagindo direta ou indiretamente ao
agir em seu ambiente local acarreta na
emergência de um comportamente global
“inteligente”. (Engelbrecht, 2005)
• Inspirada no comportamento de insetos sociais
• É chamada de swarm intelligence (inteligência
de enxames).
Inteligência Coletiva
• Exemplos de comportamentos de insetos sociais
▫ A divisão de tarefas em uma colônia de formigas
▫ Construção de um ninho por cupins ou vespas
▫ Busca de alimentos por formigas ou abelhas
• Neste trabalho, é apresentada uma simulação do
comportamento de uma colônia de formigas ao
buscarem alimentos.
As Formigas na Natureza
• Busca por Alimentos
▫ Inicialmente, a busca por alimentos é realizada de
forma caótica e randômica (Dorigo et al., 1996;
Gambardella et al., 1997; Nemes e Roska, 1995) .
▫ Assim que uma fonte de alimento é encontrada, a
busca se torna mais organizada, com cada vez
mais formigas seguindo o mesmo caminho.
▫ Até que, finalmente, todas as formigas estejam
seguindo o mesmo caminho, que é também o
menor caminho entre o ninho e a fonte de
alimento
As Formigas na Natureza
• Busca por Alimentos
▫ Comportamento emergente da influência exercida
pelas formigas que encontraram uma fonte de
alimento sobre aquelas que saem do ninho em
busca de alimento.
▫ Normalmente, a comunicação entre as formigas é
realizada de forma indireta.
▫ A busca por alimento utiliza apenas informação
local e funciona de maneira distribuída.
As Formigas na Natureza
• Busca por Alimentos
▫ Quando uma formiga encontra uma fonte de
alimento, ela retorna ao ninho depositando uma
substância química chamada feronômio ao longo
do caminho, formando uma trilha (Beckers et al.,
1992).
▫ A partir da concentração desta substância, uma
formiga decide qual caminho seguir e, ao voltar ao
ninho, reforça a trilha de feronômio existente
neste caminho.
As Formigas na Natureza
• Busca por Alimentos
▫ Caminhos com maior concentração de ferônomio
possuem maior probabilidade de serem
escolhidos.
▫ Este tipo de comunicação indireta entre as
formigas, a partir da modificação de seu ambiente
ao depositar feronômio, é chamado de estigmergia
(stigmergy).
As Formigas na Natureza
• Estigmergia
▫ Termo definido pelo biólogo francês Pierre-Paul
Grassé (1959).
▫ Caracteriza o comportamento complexo
emergente a partir das interações entre simples
indivíduos entre si e com o ambiente, através da
comunicação indireta destes indíviduos ao
modificarem seu ambiente local.
As Formigas na Natureza
• Experimento da Ponte Binária
▫ Denenbourg et al. (1990) estudou a estigmergia
utilizando feronômio a partir de formigas
argentinas da espécie Iridomyrmex humilis, de
forma a desenvolver um modelo formal que
descrevesse o comportamento das formigas para
encontrar o menor caminho entre ninho e fonte de
alimento.
As Formigas na Natureza
• Experimento da Ponte Binária
(a)
(b)
Figura 1:
a) Experimento da ponte binária. (Denenbourg et al., 1990);
b) Resultados obtidos no experimento da ponto binária relacionando a porcentagem
de formigas em cada uma das pontes ao longo do tempo. (Denenbourg et al.,
1990)
As Formigas na Natureza
• Experimento da Ponte Binária
▫ A partir deste estudo, foi desenvolvido um modelo
para descrever o processo de seleção do caminho,
que assume que as formigas depositam a mesma
quantidade de feronômio e que o mesmo não
evapora.
As Formigas na Natureza
• Experimento da Ponte Binária
• Sejam A e B os ramos superior
e inferior, respectivamente, e
nA(t) e nB(t) e o número de
formigas em A e B no instante
t.
• Empíricamente, Pasteels et al.,
(1989) encontraram que a
probabilidade da próxima
formiga escolher o ramo A no
instante é dada por:
onde:
• c é a atratividade de um ramo
sem feronômio e;
• α é o grau de não-lineariedade
da escolha.
As Formigas na Natureza
• Experimento da Ponte Binária
▫ Quanto maior for o valor de α, maior é a
probabilidade da próxima formiga seguir o
caminho com maior concentração de feronômio.
▫ Quanto maior for o valor de c, maior será a
quantidade de feromônio necessária para realizar
a escolha do ramo de forma não randômica.
As Formigas na Natureza
• Efeito da Diferença de Comprimento entre Dois Caminhos
• Goss et al. (1989, 1990)
estenderam o experimento da
ponte binária, onde um dos
ramos era mais longo que o
outro.
• Inicialmente, os ramos eram
escolhidos de forma aleatória,
tendo o mesmo número de
formigas em ambos os ramos.
• Com o passar do tempo, cada
vez mais formigas utilizam o
caminho mais curto.
(a)
(b)
As Formigas na Natureza
• Efeito da Diferença de Comprimento entre Dois
Caminhos (Dorigo et al., 1999; Dorigo et al., 2000).
▫ A seleção pelo menor caminho resulta do fato de que
as formigas que utilizam o menor caminho retornam
ao ninho mais rápido do que aquelas que seguem o
maior caminho.
▫ Goss et al. (1989) descobriu, após este experimento, que a
probabilidade de uma formiga escolher o menor caminho
aumenta de acordo com a diferença do comprimento entre
os dois caminhos.
▫ Chamado de efeito da diferença de comprimento dos
caminhos
As Formigas na Natureza
• Auto-organização
▫ É possível observar a emergência de um comportamento
complexo de uma colônia de formigas através da interação e
cooperação das formigas entre si e o ambiente.
▫ Auto-organização: um processo onde um padrão (arranjo
complicado e particular de objetos organizados no tempo e no
espaço) complexo de um sistema, em nível global, emerge a partir
da interação entre os componentes de baixo nível do sistema
(Camazine et al., 2001).
▫ Numa colônia de formigas, as estruturas emergentes do sistema
são as trilhas de feronômio, que formam padrões organizados no
tempo e no espaço.
Simulação
Referências Bibliográficas
• BECKERS, R., DENEUBOURG, J.-L., GOSS, S. Trails and U-turns in the selection of the
shortest path by the ant Lasius Niger. Journal of Theoretical Biology, 159:397-415,1992.
• DENEUBORG, J.-L., ARON, A., GOSS, S., PASTEELS, J.-M.. The Self-Organization
Exploration Pattern of the Argentine Ant. Journal of Insect Behavior. 3:159-168,1990.
• CAMAZINE, S., DENEUBORG, J-L, FRANKS, N. R., SNEYD, J., THERAULAZ, G.,
BONABEAU, E., Self-organization in Biological Systems. Princeton University Press, 2001.
• DORIGO M., MANIEZZO V,. COLORNI A.. The ant system: Optimization by a colony of
cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics–Part B,
26(1):29–41, 1996.
• DORIGO, M., DI CARO, G., GAMBARDELLA, L. M., Ant algorithms for discrete
optimization. Artificial Life, vol. 5, pp. 97-116, 1999.
• DORIGO, M., BONABEAU, E., THERAULAZ, G., Ant Algorithms and Stigmergy. Future
Generation Computers Systems, 16(9):851-871, 2000.
Referências Bibliográficas
• ENGELBRECHT, A. P., Fundamentals of Computational Swarm Intelligence, 1ª Ed., John
Willey & Sons Ltda, 2005.
• GAMBARDELLA, L.M., TAILLARD, E., DORIGO, M. Ant Colonies for the QAP. Techinical
Report, IDSIA, 1997.
• GOSS, S.; ARON, S.; DENEUBOURG, J. L.; PASTEELS, J. M. Self-organized shortcuts in
the Argentine ant. Naturwissenschaften, 76:579–581, 1989.
• GOSS S., BECKERS R., DENEUBOURG J.L., ARON S., PASTEELS J.M., How Trail Laying
and Trail Following Can Solve Foraging Problems for Ant Colonies, in Hughes R.N. (ed.)
NATO ASI Series, Vol. G 20, Behavioural Mechanisms of Food Selection, Springer Verlag,
Berlin, 1990.
• GRASSÉ, P.-P. La Reconstruction du nid et le coordinations interindividuelles. La théorie
de la stigmergie: Essai d’interprétation du Comportement des Termites Constructeurs.
Insectes Sociaux, 6:41-60, 1959.
• NEMES, L., ROSKA, T., A CNN Model of Oscilation and Chaos of Ant Colonies: A Case
Study. IEEE Transactions on Circuits and Systems I: Fundamental Theory and
Applications, 42(10): 741-745, 1995.