Otimização por Colônia de Formigas
Ant Colony Optimization
Cassio Conti
[email protected]
Agenda
• Introdução
– Problemas de otimização
– Ideia da otimização por colônia de formigas
•
•
•
•
Ant Colony Optimization (domínio discreto)
Exemplo de aplicação
Ant Colony Optimization (domínio contínuo)
Aplicação em problema real
Problemas de Otimização
Os problemas de otimização
combinatória
possuem
a
qualidade da solução ligada a
ordem em que os elementos
que compõem a solução
aparecem.
Quanto
mais
elementos, mais combinações
são possíveis e maior é o
tempo de processamento
necessário para encontrar a
solução ótima.
• Sequência desejada:
o 2-3-1
• Combinações possíveis:
o 1-2-3
o 1-3-2
o 2-1-3
o 2-3-1
o 3-1-2
o 3-2-1
Problemas de otimização
3 elementos: 6 combinações
4 elementos: 24 combin.
5 elementos: 120 combin.
6 elementos: 720 combin.
7 elementos: 5040 combin.
8 elementos: 40320 combin.
9 elementos: 362880 comb.
n elementos: n! combinações
Algoritmos de otimização
utilizam técnicas para buscar
a melhor solução de um
problema em situações onde
seria necessário muito tempo
computacional para analisar
todos os possíveis valores.
Ideia do ACO
Baseia-se no comportamento de formigas reais.
• As formigas, tanto as reais quanto as do ACO baseiam seu
"conhecimento" do ambiente nas trilhas de feromônio.
• A tendência é escolher a trilha com mais feromônio.
• Feromônio evapora com o tempo.
Caixeiro Viajante
Traveling Salesman Problem
(TSP)
Se existem 2 cidades, A e B,
considerando que o caixeiro
inicialmente está em A, temse apenas 1 solução possível
que é a distância entre A e
B. Se existem 3 cidades,
têm-se 2 caminhos possíveis,
ABC ACB. 4 cidades indicam
6 caminhos possíveis, ABCD
ABDC ACBD ACDB ADBC
ADCB, ou seja, (n – 1)!
possíveis
caminhos
diferentes.
Ant Colony Optimization (ACO)
Algoritmos inspirados no
comportamento das formigas
na busca por alimentos
foram
introduzidos
por
Marco Dorigo em sua tese de
doutorado. Esse tipo de
algoritmo é conhecido na
literatura como Ant Colony
Optimization (ACO).
Ant System foi o primeiro
exemplo de ACO proposto
por Dorigo.
Explora a característica do
feromônio
depositando
diferentes quantidades de
substância
no
caminho
(dependendo da qualidade do
caminho encontrado).
Ant System
– Gera uma solução
(caminho)
– Avalia essa solução
– Deposita sobre cada
aresta desse caminho,
uma quantidade x de
feromônio.
– Sendo x uma função onde
se o caminho é menor, x
possui maior valor.
Caminho 12345 = 16
Caminho 12354 = 12
Caminho 12435 = 15
Caminho 12453 = 11
Caminho 14235 = 13
....
Ex: x = 1 / f(caminho)
+0.8 (÷2.1 = 38%)
+0.6 (÷2.1 = 29%)
+0.7 (÷2.1 = 33%)
------2.1 (100%)
Gera valor aleatório [0 - 1]
[0 - 0.38]: escolhe 2
(0.38 - 0.67]: escolhe 5
(0.67 - 1]: escolhe 4
Heurística (Visibilidade)
gerar_solucao(f) {
escolher_proximo(f)
}
gerar_solucao(f, dist) {
v <- 1 / dist
escolher_proximo(f + v)
}
1
2
3
4
5
1
2
3
4
5
0 0,8
0 0,4 0,5
0,8
0 0,4 0,4
0
0 0,4
0 0,2 0,6
0,4 0,4 0,2
0 0,2
0,5
0 0,6 0,2
0
Heurística (Visibilidade)
+0.8 (÷2.1 = 38%)
+0.6 (÷2.1 = 29%)
+0.7 (÷2.1 = 33%)
------2.1 (100%)
1÷2=0.5
1÷6=0.2
1÷3=0.3
+1.3 (÷3.1 = 42%)
+0.8 (÷3.1 = 26%)
+1.0 (÷3.1 = 32%)
-----3.1 (100%)
ACO Discreto - Importância da
Visibilidade
Tamanho do percurso do caixeiro
Iteração onde o melhor
percurso foi encontrado
6000
600
5000
500
4000
3000
Sem
400
visibilidade
2000
Com
300
visibilidade
200
1000
100
0
oliver30
eil51
a280
0
oliver30
eil51
a280
12
ACO Contínuo – ACOR – Feromônio
s1
s2
...
sj
...
sk
s11
s12
...
s1i
...
s1n
s21
s22
...
s2i
...
S2n
sj1
sj2
...
sji
...
Sjn
sk1
sk2
...
ski
...
Skn
Arquivo
população
f  X   aX1  bX2    zX n
13
  sli
ACOR - Amostragem
k
 li   
j 1
s ij  sli
k 1
• A função de densidade de probabilidade usada nas
amostragens do algoritmo é a função gaussiana
(distribuição normal), entretanto ela não é capaz de
descrever a situação onde há duas áreas
promissoras disjuntas no domínio.
s1
s2
...
sj
...
sk
s11
s12
...
s1i
...
s1n
s21
s22
...
s2i
...
S2n
sj1
sj2
...
sji
...
Sjn
sk1
sk2
...
ski
...
Skn
14
ACOR – Sequência de passos
Inicialização da
População
• Inicia o arquivo população com k soluções aleatórias.
• Ordena as soluções pela qualidade [f(s1) ≥ f(s2) ≥ ...].
Construção de
novas soluções
• Para cada agente (formiga), faça:
• Escolha uma solução sl dentre as k soluções do arquivo população.
Para cada uma das
n variáveis que
compões uma
solução:
Amostra um
novo valor.
Seta a média
sji.
Calcula o
valor de
desvio
padrão.
Atualização da
população
Verificação
do critério
de parada
X = {X1, X2, ..., Xn}
sl = {sl1, sl2, ..., sln}
• Avalia e adiciona as novas soluções ao arquivo população.
• Ordena as soluções pela qualidade e mantém somente as k melhores.
• Se o critério de parada não for alcançado, voltar ao segundo passo.
• Caso contrário, encerrar o algoritmo.
15
Proposta de Visibilidade para ACO
contínuoQuando todas as soluções
do arquivo estiverem na
mesma região a
visibilidade é desligada.
s1’
s3’
s2’
s3
s1
s2
s1
s2
s3
s1’
s2’
s3’
16
Proposta para Visibilidade
X  X1, X 2 ,, X n 
X '  X1 ' , X 2 ' ,, X n '
s1
s2
...
sj
...
sk
s11
s12
...
s1i
...
s1n
s21
s22
...
s2i
...
S2n
sj1
sj2
...
sji
...
Sj n
sk1
sk2
...
ski
...
17 n
Sk
Experimentos – Testes e Resultados
Problemas
1
B2
2
Branin RCOS
3
Cigar
4
De Jong
5
Eason
6
Ellipsoid
7
Goldstein and Price
8
Martin and Gaddy
9
Sphere model
10
Tablet
11
Zakharov
Os mesmo parâmetros utilizados
por Socha e Dorigo foram
aplicados para que fosse possível a
comparação.
18
Experimentos – Testes e Resultados Iterações
0
Número médio de iterações
500
1000
1500
2000
2500
B2
Branin RCOS
Cigar
De Jong
Eason
Ellipsoid
Sem visibilidade
Com visibilidade
Goldstein and Price
Martin and Gaddy
Sphere model
Tablet
Zakharov
19
Experimentos – Testes e Resultados Avaliações
0
Número médio de avaliações
1000
2000
3000
4000
5000
B2
Branin RCOS
Cigar
De Jong
Eason
Ellipsoid
Sem visibilidade
Com visibilidade
Goldstein and Price
Martin and Gaddy
Sphere model
Tablet
Zakharov
20
Aplicação Real – Exploração de
Petróleo
Aquisição Sísmica
Aquisição Sísmica
Sísmica
Poço
Sísmica e Poço
Impedância
𝑖𝑚𝑝𝑒𝑑â𝑛𝑐𝑖𝑎 = 𝑑𝑒𝑛𝑠𝑖𝑑𝑎𝑑𝑒 × 𝑣𝑒𝑙𝑜𝑐𝑖𝑑𝑎𝑑𝑒
Propriedade dos Dados (rochas)
𝑖𝑚𝑝𝑖+1 − 𝑖𝑚𝑝𝑖
𝑟𝑒𝑓𝑖 =
𝑖𝑚𝑝𝑖+1 + 𝑖𝑚𝑝𝑖
• Não existe um método de inversão sísmica
que dê a solução exata.
• Existem várias soluções possíveis.
• Propício ao uso de heurísticas para adaptar a
técnica ao problema.
ACO (Ant Colony
Optimization)
Estimação do Pulso Sísmico
Estimação do Pulso Sísmico
Inversão Sísmica
Heurísticas para acelerar a busca
Gera diversas configurações
similares ao poço.
Inversão utilizando ACO
• Para os demais traços, usa-se o traço vizinho
(que já foi otimizado) como modelo de
referência.
• Resultados
– Inversão Traço-a-Traço
• 4 replicações - 1000 iterações do algoritmo –
Utiliza-se a média
• Tempo em uma SUN Workstation ULTRA 27:
~3.5min por in-line
R=0.97289
• Resultados
– Inversão pelo Filtro Inverso
• 10 replicações – 100 mil iterações do algoritmo
– Utiliza-se o melhor
• Tempo em uma SUN Workstation ULTRA 27 :
~2min45seg
R=0.95604
Problemas
• Poucos poços
– Pouca informação sobre os tipos de rochas
existentes.
– Pulso sísmico ruim (mal estimada)
• Consequentemente, inversão ruim.
• Sísmica ruidosa
– Podem gerar falsas propriedades de rocha
• Características que podem levar a decisões erradas.
Otimização por Colônia de Formigas
Ant Colony Optimization
Cassio Conti
[email protected]
• Cassio Rodrigo Conti
– [email protected]
– Departamento de Informática e Estatística (INE)
• Ciência da Computação (PPGCC)
– Laboratório de Conexionismo e Ciências
Cognitivas (L3C)
• Orientador: Prof. Dr. Mauro Roisenberg
• Área de Inteligência Artificial / Computacional