Optimização através de colónias
de formigas
© Guy Theraulaz
Insectos, Insectos Sociais e
Formigas
• ~1018 insectos vivos
• ~2% de todos os insectos são sociais
• Os insectos sociais:
–
–
–
–
•
•
•
•
Todas as formigas
Todas as térmitas
Algumas abelhas
Algumas vespas
50% de todos os insectos são formigas
Peso médio de uma formiga: entre 1 e 5mg
As formigas colonizaram a Terra há 100 milhões de anos
O Homo Sapiens há 50000 anos
Vida Artificial
Optimização através de colónias de formigas
1
Colónias de Formigas
• Tamanho das colónias de formigas: de 30 a milhões de operárias
• Divisão do trabalho:
–
–
–
–
–
–
Reprodução: raínha
Defesa:
Recolha de alimentos
Tratamento das crias
Limpeza dos ninhos
Construção e manutenção dos ninhos
Vida Artificial
Optimização através de colónias de formigas
2
Algoritmos Formiga
•
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 a comportamento coordenado das
formigas, podem ser explorados para resolver problemas computacionais.
•
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 para resolverem problemas de optimização e de
controlo distribuído.
•
Vários comportamentos das colónias de formigas inspiraram diferentes tipos de
algoritmos formiga. (recolha de alimentos; divisão do trabalho; transporte
cooperativo, “agrupamento das crias, reconhecimento colonial, etc).
Vida Artificial
Optimização através de colónias de formigas
3
Estigmergia
•
Na maior parte dos casos, as formigas coordenam-se através da
estigmergia, que é uma forma de comunicação indirecta que é mediada
pelas modificações no meio-ambiente. Os Biólogos confirmaram que em
muitos casos, é suficiente considerar a comunicação estigmérgica para
explicar como é que as colónias de formigas se auto-organizam e são
capazes de realizarem tarefas colectivas complexas.
•
O termo pertence a Pierre-Paul Grassé, e foi introduzido em 1959, e
resultou da investigação de Grassé com o comportamento de construção
das térmitas. Segundo Grassé, a estigmergia é a “estimulação das
operárias através da “performance” que realizaram”. As térmitas são
capazes de criar bolas de lama para construírem os ninhos, impregnam
essas bolas de lama com feromonas e largam-nas no chão. As térmitas são
atraídas pelas feromonas e assim, depositam bolas de lama perto umas
das outras, construindo pilares, arcos, túneis e câmaras.
Vida Artificial
Optimização através de colónias de formigas
4
Estigmergia
• O que distingue a estigmergia de outras formas de comunicação é:
– 1) o carácter físico da informação, que corresponde à modificação dos
estados físicos do meio-ambiente visitado pelos insectos e
– 2) a natureza local da informação, a qual apenas pode ser acedida
pelos insectos que visitem o lugar onde foi criada (ou algum lugar
vizinho).
• É possível falar de comunicação estigmergica sempre que exista
comunicação mediada por modificações físicas dos estados do
meio-ambiente, os quais só são localmente acessíveis pelos
agentes.
Vida Artificial
Optimização através de colónias de formigas
5
Recolha de Alimentos
Vida Artificial
Optimização através de colónias de formigas
6
Recolha de Alimentos
•
O comportamento de recolha de
alimentos de muitas sociedades de
formigas (I. Humilis, Linepithema
humile, Lasius Niger) baseia-se na
comunicação indirecta mediada por
feromonas (estigmergia através de
marcas ou signos).
filme
Vida Artificial
Optimização através de colónias de formigas
7
Emergência de umTrilho Químico
•
Enquanto caminham do ninho para as fontes de alimento e vice-versa, as
formigas depositam feromonas no chão, formando um trilho de feromonas.
•
As formigas são capazes de “snifar” 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,
numa espiral crescente.
•
Vida Artificial
Optimização através de colónias de formigas
8
Experiências da ponte bifurcada
•
•
•
Experiência de Deneubourg com formigas reais L. humile.
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, aleatóriamente, depois
de uma fase inicial transitória
Explicação: Não há preferência inicial mas pequenas flutuações iniciais poderão são
amplificadas dando origem à preferência por um dos caminhos.
Vida Artificial
Optimização através de colónias de formigas
9
Optimização
QuickTime™ and a
TIFF (LZW) decompressor
are needed to see this picture.
•
•
•
•
•
As formigas seleccionam colectivamente o caminho mais curto.
As flutuações aleatórias têm muito menos influência.
Explicação: as formigas que optam pelo caminho mais curto, são as primeiras a chegar à fonte de comida e a
regressar. Acumula-se mais feromona nos ramos mais curtos que atrai mais formigas e + feromona, etc.
No entanto, os caminhos mais longos continuam a ser utilizados por formigas (comportamento probabilístico).
Diferencial do comprimento dos caminhos
Vida Artificial
Optimização através de colónias de formigas
10
Optimização
Vida Artificial
Optimização através de colónias de formigas
11
Resumo
 As formigas encontram o caminho mais curto para a comida
 As formigas depositam feromona ao longo do caminho
 A feromona vai-se evaporando
 A intensidade da feromona aumenta com o número de
formigas
 Os “bons” caminhos são reforçados e os “maus”
desaparecem gradualmente
Vida Artificial
Optimização através de colónias de formigas
12
Suboptimalidade
•
O que acontece se depois da convergência para um caminho,
adicionarmos um caminho ainda mais curto?
•
O novo caminho mais curto é seleccionado apenas esporadicamente,
ficando a colónia presa ao caminho subóptimo.
•
Explicação: A elevada concentração de feromona aliada à baixa taxa de
evaporação são as causas desse fenómeno.
•
A evaporação, que pode favorecer a exploração de novos caminhos, é
demasiado lenta, impedindo que a colónia se esqueça dos caminhos
suboptimais, e que descubra um caminho novo e “aprenda” a escolhê-lo.
Vida Artificial
Optimização através de colónias de formigas
13
Comportamento “Swarm”
As características “swarm” estão presentes
no comportamento de recolha de
alimentos
“Feedback” Positivo
“Feedback” Negativo
Aleatoriedade
Interações Múltiplas
Vida Artificial
Optimização através de colónias de formigas
14
“Feedback” Positivo
• O “Feedback” Positivo reforça as boas
soluções
• As formigas são capazes de recrutar
outras quando encontram comida
• Mais formigas num trilho aumentam o
nível de feromona e atraiem ainda mais
formigas.
Vida Artificial
Optimização através de colónias de formigas
15
“Feedback” Negativo
• O “Feedback” Negativo remove da memória
colectiva (exterior) as soluções antigas e as más
soluções
• Evaporação da Feromona
• 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.
– A Feromona tem menos tempo para se evaporar nas
soluções mais curtas.
Vida Artificial
Optimização através de colónias de formigas
16
Aleatoriedade
A aleatoriedade permite que novas soluções
sejam procuradas e dirigem a exploração
das soluções correntes.
• As decisões das formigas são
probabilísticas
– Probabilidade de exploração, dado que a
subida do gradiente é probabilística
• As fontes de comida são encontradas de
modo aleatório.
Vida Artificial
Optimização através de colónias de formigas
17
Interacções Múltiplas
• Nenhum indivíduo pode resolver um problema.
Só através da interacção de muitos é que a
solução pode ser encontrada.
• Uma única formiga não pode “recolher” comida.
A feromona evaporar-se-ia demasiado
rapidamente.
• São precisas muitas formigas para manter o
trilho
• Pode-se encontrar comida mais rapidamente
Vida Artificial
Optimização através de colónias de formigas
18
Algoritmos Formiga
• A ideia por detrás dos algoritmos formiga é
utilizar uma forma de estigmergia artificial para
coordenar sociedades de agentes artificiais.
• As características da estigmergia referidas em
cima podem ser facilmente estendidas aos
agentes artificiais através de
(i) associar variáveis aos estados do
problema e
(ii) dar aos agentes um acesso local a essas
variáveis.
Vida Artificial
Optimização através de colónias de formigas
19
Formigas Artificiais para
Problemas de Custo Mínimo
Início
Objectivo
Vida Artificial
Optimização através de colónias de formigas
20
Resultado da Optimização
Início
Objectivo
Vida Artificial
Optimização através de colónias de formigas
21
S-ACO
S-ACO: Simple Ant Colony Optimization
Ferramenta Didáctica para explicar o mecanismo
básico dos algoritmos ACO.
Representa um passo significativo para a
definição de um algoritmo eficiente.
Vida Artificial
Optimização através de colónias de formigas
22
Rasto de Feromona Artificial
A cada arco (i,j) do grafo G=(N,A) associamos uma variável (tij), a que
chamamos de rasto de feromona artificial
Os rastos de feromonas artificiais são lidos e escritos pelas formigas
A quantidade (intensidade) de feromona é proporcional à utilidade,
estimada pelas formigas, de utilizarem esse arco para construirem
boas soluções.
Inicialmente, todos os arcos possuem a mesma quantidade de
feromona: tij=1 (i,j) A.
Vida Artificial
Optimização através de colónias de formigas
23
Dois Modos
As formigas S-ACO executam passo a passo (de nó a nó) e
têm dois modos de funcionamento:
Estão no modo para a frente quando estão a mover-se
do nó inicial (ninho) para o nó final (fonte de alimento)
Estão no modo regresso sempre que estiverem a
mover-se em direcção ao ninho partindo da fonte de
alimento.
Quando uma formiga no modo para a frente atinge o
nó final, passa para o modo regresso e vice-versa.
Vida Artificial
Optimização através de colónias de formigas
24
Modo Para a Frente
As formigas para a frente constroiem uma
solução escolhendo probabilisticamente o
próximo nó entre os nós vizinhos do nó
onde estão.
Vida Artificial
Optimização através de colónias de formigas
25
Modo Para a Frente
Quando estiver num nó i, a formiga k utiliza
o trilho tij para calcular a probabilidade de
escolher cada um dos nós vinhos j como
nó seguinte
Vida Artificial
Optimização através de colónias de formigas
26
Modo Para a Frente
Consideram-se só como nós vizinhos todos os nós ligados
directamente ao nó corrente i, excepto o nó predecessor
de i (onde estava antes de se mover para i).
No caso de não haver vizinhos (beco sem saída), o nó
predecessor é o único vizinho e é para esse nó que a
formiga vai.
Ciclos: Esta forma de decisão do próximo nó leva
facilmente à formação de ciclos.
Vida Artificial
Optimização através de colónias de formigas
27
Modo Para a Frente
Quando localizada num nó i a formiga k usa o
trilho de feromona para calcular a probabilidade
de escolher cada uma dos nós vizinhos j.


t
ij

k


pij   lN ikt ij

0
Vida Artificial
j Ni
k
se
se
Optimização através de colónias de formigas
j Ni
k
28
Modo Para a Frente
As formigas andam de nó em nó desde o nó
inicial até que eventualmente deparem
com o nó final.
Devido às diferenças entre os caminhos das
formigas, o instante temporal em que as
diversas formigas atingem o objectivo
difere de formiga para formiga
(As formigas que escolham caminhos mais
curtos chegarão mais depressa).
Vida Artificial
Optimização através de colónias de formigas
29
Modo Regresso
As formigas no modo de regresso, devido à
memória do caminho percorrido, refazem
deterministicamente (quase) o mesmo
caminho depois da eliminação dos ciclos,
desde o objectivo até ao nó inicial, passo
a passo (nó a nó)
Vida Artificial
Optimização através de colónias de formigas
30
Problema dos Ciclos
O problema dos ciclos é que os nós que
fazem parte de um ciclo podem receber
muita feromona levando aos ciclos que se
auto-reforçam.
Vida Artificial
Optimização através de colónias de formigas
31
Regresso: Eliminação dos Ciclos
Os ciclos são eliminados pela mesma ordem
que são criados.
Se o caminho contiver ciclos imbrincados
uns nos outros então o ciclos mais longos
não são necessariamente eliminados
Vida Artificial
Optimização através de colónias de formigas
32
Processo de eliminação dos Ciclos
Direcção da verificação de nós repetidos
1º nó a ser verificado
0-1-3-4-5-3-2-8-5-6-9
1ª ocorrência do nó 3
Verificando o nó 3
0-1-3-4-5-3-2-8-5-6-9
Verificando o nó 2
0-1-3-2-8-5-6-9
Não há mais ciclos
Vida Artificial
Optimização através de colónias de formigas
33
Regresso: actualização da
feromona
Durante o regresso desde o objectivo até ao nó inicial, a formiga vai
depositando feromona em cada um dos arcos que visitou
(exceptuando os que foram removidos devido ao processo de
remoção de ciclos).
Em particular, se a formiga k
estiver no modo regressso e
se atravessar o arco (i,j)
modifica o valor da feromona
desse arco:
Vida Artificial
tij  tij  t
Optimização através de colónias de formigas
k
34
Duas possibilidades de
actualização da feromona por parte
da formiga k (no regresso)

t
k
Constante: O acréscimo de feromona é constante para todas as
formigas e para todos os arcos.
(Depende apenas do diferencial do tamanho do caminho: as formigas
com melhores caminhos depositam feromona mais cedo)
Variável: Além do acréscimo constante, as formigas depositam uma
quantidade de feromona que depende da qualidade do caminho.
Quanto mais pequeno o caminho maior essa quantidade.
Vida Artificial
Optimização através de colónias de formigas
35
Evaporação
A evaporação do trilho de feromona pode ser visto como um
mecanismo de exploração que evita uma convergência rápida
para um caminho suboptimal. Favorece a exploração de
diferentes caminhos durante o processo de pesquisa. Favorece
o esquecimento das más escolhas e limita o nível de feromona
nos arcos.
O facto de ser menos
importante nas formigas
reais é devido a que os
problemas artificiais são
mais complexos do que os
reais.
Vida Artificial
t ij
 (1  p)
t ij
p  0,1
Optimização através de colónias de formigas
36
Ciclo S-ACO
1- Cada uma das formigas escolhe o próximo
nó a visitar (seja em modo regresso seja em
modo para a frente.
2 -A feromona evapora-se em todos os arcos
3- Actualização da feromona no arco escolhido
para o caso das formigas que estão a
regressar
Vida Artificial
Optimização através de colónias de formigas
37
Experiências com S-ACO
Dupla Ponte
Dupla Ponte Estendida
Vida Artificial
Optimização através de colónias de formigas
38
Critério de Convergência
A experiência acaba quando todas
as formigas utilizam o mesmo
caminho.
Contam-se as iterações
A qualidade do caminho: O Melhor
ou Não?
Vida Artificial
Optimização através de colónias de formigas
39
Resultados das experiências
O Diferencial do Comprimento do Caminho, embora importante,
não é suficiente para problemas mais complexos.
As actualizações de feromona baseado na qualidade das soluções
são importantes para uma convergência mais rápida.
Valores elevados do parâmetro  dão maior importância às
flutuações iniciais e a um comportamento deficiente do
algoritmo
Quanto maior o número de formigas melhor a performance com o
custo de tempos de simulação maiores.
Vida Artificial
Optimização através de colónias de formigas
40
Perguntas
Vida Artificial
Optimização através de colónias de formigas
41