Otimização com Colônias
de Formigas
Giuliano Mega
Márcio Akyama
Estrutura do Seminário
• Introdução
– Fundamentação
– Experimentos
– Características do sistema
• A meta-heurística ACO [1]
– Formigas
– Estrutura geral
• Aplicação – Ant System [2]
Contexto: Caixeiro Viajante
– ACS – Ant Colony System
– Job-shop Scheduling
– Aplicação geral do AS/ACS
• Conclusão
Introdução
• Formigas
– Insetos sociais
– Indivíduos simples
– Colônias altamente estruturadas
• Comportamentos de interesse
– Busca por comida
– Capazes de encontrar caminhos
mínimos entre fontes de comida e
o ninho
• Como?
– Trilhas de feromônio
– Induzem outras formigas
Introdução (cont.)
• Heurísticas de Colônias de
Formigas
– Estudo do comportamento das
formigas
• Trilha de feromônio
– Induzem a formação dos
caminhos mínimos
– Experimento da ponte bifurcada
Introdução (cont.)
–Resultados:
(U m  k )h
PU (m) 
(U m  k )h  ( Lm  k )h
Introdução (cont.)
•Caminhos desiguais
–Intuitivamente:
30
15
20
15
10
15
10
15
20
30
– Trilhas com alta concentração de
feromônio = caminhos mais curtos.
Introdução (cont.)
• Chaves
– 1 formiga – comportamento
aleatório
– Várias formigas – caminhos
mínimos
– Comunicação estigmergética
• Forma indireta de comunicação
• Modificação do estado das
localizações visitadas
• Informações locais
– Implicit evaluation
– Processo autocatalítico
– Otimização distribuída.
Formigas
• Formigas artificais e reais –
semelhanças:
– Colônia cooperativa de indivíduos
• Formiga: capaz de produzir
soluções viáveis
• Cooperação -> soluções de boa
qualidade.
– Trilha de feromônio e
comunicação estigmergética local
• Informações adicionais associadas
a cada estado visitado(a)
• Percepção do ambiente e histórico
da colônia
• Evaporação (estagnação)
Formigas (cont.)
– Seqüência de movimentações
locais para a descoberta de
caminhos mínimos
• Caminho mínimo entre um par de
estados
• Caminhada pelas vizinhanças
– Política de decisão estocástica:
• Baseada em informações locais
– Feromônio
– Informações heurísticas
• Sem lookahead
Formigas (cont.)
• Formigas artificiais e reais –
diferenças:
– Mundo discreto
– Estado interno (memória de
ações passadas)
– Quantia de feromônio dada em
função da qualidade da solução
– Características temporais
– Capacidades extras
• Lookahead
• Otimizações locais
• Backtracking
A meta-heurística
• Forma geral
procedimento Meta_heurística_ACO()
enquanto(
critério_de_término_não_satisfeito )
agendar_atividades
gera_e_movimenta_formigas();
evaporar_feromônio();
ações_dos_daemons();
fim agendar_tarefas
fim enquanto
fim procedimento
procedimento gera_e_movimenta_formigas()
enquanto( houver_recursos )
agenda_criação_de_nova_formiga();
nova_fformiga_ativa();
fim enquanto
fim procedimento
A meta-heurística (cont.)
procedimento nova_formiga_ativa()
inicializa_formiga();
M = atualiza_memória_da_formiga();
enquanto (estado_atual != estado_pretendido)
A = lê_tabela_de_roteamento_local();
P = computa_probabilidades_de_transição
(A, M, restrições);
próximo_estado = aplica_política_decisão
(P, restrições);
move_para_próximo_estado(próximo_estado);
se (atualiza_feromônio_on-line)
deposita_feromônio_no_arco_visitado();
atualiza_tabela_roteamento();
fim se
M = atualiza_estado_interno();
fim enquanto
se (atualização_de_feromônio_posposta)
avalia_solução();
deposita_feromônio_nos_arcos_visitados();
atualiza_tabela_roteamento();
fim se
morre();
fim procedimento
A meta-heurística (cont.)
• Características
–
–
–
–
–
Populacional
Estocástica
Comunicação indireta
Distribuível/paralelizável
Aplicável a problemas
dinâmicos
O Ant System
• Caixeiro Viajante
Dadas n cidades, queremos o menor passeio em que
todas as cidades são visitadas.
Formalmente:
Dado um grafo não-dirigido e completo G  ( N , E),
encontrar o ciclo Hamiltoniano de menor custo em G.
• Formiga
– Escolha da cidade: distância
(heurística) e rastros
– Lista tabu
– Atualização de rastros: final de
cada iteração
O Ant System (cont.)
• Trilhas
 (t  n)    ij (t )   ij
m
 ij   
k 1
k
ij
 Q , se a k-ésima formiga utiliza a
 aresta (i,j) entre t e t+n
k
 ij   Lk
0 , caso contrário

O Ant System (cont.)
•Decisão



 ij (t )   ij 

, se k  {N  tabuk }



k
(1) pij (t )     ik (t )   ik 
 k{ N tabuk }
0, caso contrário
1

d ij
visibilidade
•Modalidades
–ant-cycle*
–ant-quantity
–ant-density
Q
  
0
k
ij
Q
d
k
 ij   ij
0

O Ant System (cont.)
•Desempenho e parâmetros
–Oliver30 [3]:
–Q: irrelevante (1 nos artigos
posteriores)
–342 ciclos (média)
–5824 segundos
–num 286
O Ant Colony System
• Ant Colony System [3, 4]
– Algoritmo igual ao AS, ant-cycle
– Regra de decisão diferente




arg
max

(
r
,
u
)


(
r
,
u
)
, se q  q o





s

S , caso contrário
q – número aleatório distribuído uniformemente
entre [0,1]
S – variável aleatória distribuída de acordo com (1) –
mas com  fixo e igual a 1.
– Só a melhor formiga deposita
feromônio (elitist ant)
 (r, s)  (1   )  (r, s)     (r, s)
O Ant Colony System (cont.)
1

 Lgb  , se (r , s)  Tmax
 (r , s)  

0, caso contrário
•Modalidades de atualização:
–global-best*
–iteration-best
•Mais dirigido que o AS
•Mais eficaz
–Desempenho comparável ao das
melhores heurísticas
–Até mesmo de heurísticas
especializadas
Aplicando o AS/ACS
• O que é necessário definir?
– Representação sob a forma de
grafo
– Processo autocatalítico
– Heurística construtiva (“força
gulosa”)
– Método de satisfação de
restrições (lista tabu)
Aplicando o AS/ACS (cont.)
• Job-shop scheduling
Jm | recrc, pij | C j
M máquinas e J tarefa. A j-ésima tarefa consiste de
uma seqüência (cadeia) ordenada de operações
tiradas de um conjunto O  {...o jm ...}.
A operação o jm  O pertence à tarefa j e deve ser
processada na máquina m por d jm instantes
consecutivos.
Tarefa 1
m1 (1)
m2 (2)
Tarefa 2
m2 (3)
m1 (4)
Tarefa 3
m1 (5)
m2 (6)
Aplicando o AS/ACS (cont.)
Peso do arco: par ( ij ,ij ) .
-Longest Processing Time
-Shortest Completion Time
  (0,1, 2,3, 4,5,6)
{(1, 4),(1,5),(4,5)};{(2,3),(2,6),(3,6)}
Conclusão
• Ant Colony
– Heurística populacional
– Computação evolutiva
• Principais aplicações
– Otimização combinatória
– Problemas difíceis
– Problemas dinâmicos
• Algoritmos mais conhecidos
– AS/ACS/ACS-opt3
Referências
[1] Dorigo M., G. Di Caro & L. M. Gambardella (1999). Ant
Algorithms for Discrete Optimization. Artificial Life, 5(2):137-172.
[2] Dorigo M., V. Maniezzo & A. Colorni (1996). Ant System:
Optimization by a colony of cooperating agents. IEEE Transactions
on Systems, Man, and Cybernetics-Part B, 26(1):29-41
[3] Dorigo M. & L.M. Gambardella (1997). Ant Colonies for the
Traveling Salesman Problem. BioSystems, 43:73-81.
[4] Dorigo M. & L.M. Gambardella (1997). Ant Colony System: A
Cooperative Learning Approach to the Traveling Salesman Problem.
IEEE Transactions on Evolutionary Computation, 1(1):53-66.
Dúvidas?