Otimização por Colônias de Formigas
– ACO (Ant Colony Optimization)
• Inspirada no comportamento de busca por
alimentos das formigas
• Aplicações em problemas de otimização
combinatorial
ACO :: Aplicações
• Problema do Caixeiro Viajante
• Descobrimento de Rotas
– Roteamento de veículos
– Roteamento em redes de telecomunicação
• Escalonamento de Tarefas
• Coloração de Mapas
• Bioinformática
– Árvores filogenéticas
– Dobramentos de proteínas
• Mineração de Dados
– Clustering
– Classificação (Ant-Miner)
http://sourceforge.net/projects/guiantminer/
ACO :: Colônias de Formigas Reais
• Curiosidades
–  9000 espécies conhecidas
– Colônias compostas de dúzias a milhões de
indivíduos
– Tempo de vida da rainha pode superar 20 anos
– As formigas são seres praticamente cegos
ACO :: Colônias de Formigas Reais
• Comunicação
– Direta
• Contatos através das antenas, troca de comida ou líquido,
contato mandibular
– Indireta
• Interações a nível microscópico (substâncias químicas)
• Estigmergia
– Semitectônica: construção de ninhos
– Baseada em sinal/substância: busca por alimento
ACO :: Colônias de Formigas Reais
• Busca por alimento
– Estigmergia através de trilhas de feromônio
– Preferência probabilística por caminhos com
alta taxa de feromônio
– Adaptação a mudanças do ambiente (autoorganização)
Colônias de Formigas Reais
(encontrando o melhor caminho...)
• Situação 1:
• Situação 2:
?
?
Colônias de Formigas Reais
(encontrando o melhor caminho...)
• Situação 3:
• Situação 4:
ACO :: Colônias de Formigas Reais
• Busca por alimento
ACO :: Colônias de Formigas Artificiais
• Proposta inicialmente por Marco Dorigo
(1996)
• Inspirada no comportamento das colônias de
formigas reais na procura de alimento
• Baseada em população
– Agentes simples (artificial ants)
• Sistema auto-organizável
– Comunicação entre agentes (estigmergia)
ACO :: Semelhanças e Diferenças
• Semelhanças com o sistema real
– Uma colônia de indivíduos (agentes) que
cooperam entre si
– Trilhas de feromônio artificiais (informações
numéricas) para comunicação local
– Preferência probabilística por caminhos com
maior quantidade de feromônio
• Caminhos curtos tendem a ter alta taxa de feromônio
– Política de decisão probabilística que faz uso
somente de informação local
ACO :: Semelhanças e Diferenças
• Diferenças com o sistema real
– Possuem memória das ações passadas
– O mundo em que ‘vivem’ é discreto
– Depositam quantidades de feromônio em
função da qualidade da solução encontrada
ACO :: O Algoritmo ACO
• Deve-se definir
– Uma representação apropriada do problema
– Função heurística ()
– Método para forçar a construção de soluções
válidas
– Regra para atualização do feromônio ()
– Regra probabilística de transição: em função
dos valores da heurística e da quantidade de
feromônio
ACO :: Problema do Caixeiro Viajante
• Representação do problema
– Grafo (N, A)
• N é o conjunto de cidades (itens componentes das
soluções)(nós)
• A é o conjunto dos caminhos entre as cidades
(arestas)
• Função heurística
– ij = 1/dij
– dij é a distância entre as cidades i e j
ACO :: Problema do Caixeiro Viajante
• Propriedade de fechamento das soluções
– Visitar todas as cidades uma única vez
• Regra de atualização do feromônio
– Evapora
 ij(t)  1    ij(t), i,j  A,   (0, 1]
– Atualiza
 ij(t  1 )   ij(t)   ij(t) Q, i,j  R
• Regra probabilística de transição


ij  ij(t)
P 
ij



 ij  ij(t) 

jS 
ACO :: Pseudo-Código
• Pseudo-código:
– Inicializar Trilhas
– Do While (Critério de parada não alcançado) – Cycle Loop
• Do Until (Cada formiga completar um caminho) – Tour Loop
• Atualização local da trilha
• End Do
• Evaporar feromônio nas trilhas
• Analizar caminhos
• Atualização global da trilha
– End Do