Optimização através de colónias de formigas © Guy Theraulaz

Optimização através de colónias de formigas

© Guy Theraulaz

Vida Artificial Optimização através de colónias de formigas 2

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


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


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).


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.


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.


Recolha de Alimentos


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


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.

•


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.


Optimização

• 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

QuickTime™ and aTIFF (LZW) decompressor

are needed to see this picture.


Optimização


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


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.


Comportamento “Swarm”

As características “swarm” estão presentes no comportamento de recolha de alimentos

“Feedback” Positivo

“Feedback” Negativo

Aleatoriedade

Interações Múltiplas


“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.


“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.


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.


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


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.


Formigas Artificiais para Problemas de Custo Mínimo

Objectivo

Início


Resultado da Optimização

Objectivo

Início


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.


Rasto de Feromona Artificial

A cada arco (i,j) do grafo G=(N,A) associamos uma variável (ij), 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: ij=1 (i,j) A.


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.


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.


Modo Para a Frente

Quando estiver num nó i, a formiga k utiliza o trilho ij para calcular a

probabilidade de escolher cada um dos nós vinhos j como nó seguinte


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.


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.

se

se

0N

k

il ij

ijk

ijp

Nk

ij

Nk

ij


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).


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ó)


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.


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


Processo de eliminação dos Ciclos

0 - 1 - 3 - 4 - 5 - 3 - 2 - 8 - 5 - 6 - 9

0 - 1 - 3 - 4 - 5 - 3 - 2 - 8 - 5 - 6 - 9

0 - 1 - 3 - 2 - 8 - 5 - 6 - 9

1º nó a ser verificadoDirecção da verificação de nós repetidos

Verificando o nó 31ª ocorrência do nó 3

Não há mais ciclos

Verificando o nó 2


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).

kijij

Em particular, se a formiga k estiver no modo regressso e se atravessar o arco (i,j) modifica o valor da feromona desse arco:


Duas possibilidades de actualização da feromona por parte

da formiga k (no regresso)

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)

k

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.


EvaporaçãoA 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.

ijij p)1( O facto de ser menos importante nas formigas reais é devido a que os problemas artificiais são mais complexos do que os reais. 1,0p


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


Experiências com S-ACO

Dupla Ponte

Dupla Ponte Estendida


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?


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.


Perguntas

Documents

Optimização através de colónias de formigas © Guy Theraulaz