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
• DENEUBORG, J.-L., ARON, A., GOSS, S., PASTEELS, J.-M.. The SelfOrganization 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., 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.
• ENGELBRECHT, A. P., Fundamentals of Computational Swarm
Intelligence, 1ª Ed., John Willey & Sons Ltda, 2005.
Referências Bibliográficas
• 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.