39
Otimização por Colônia de Formigas Ant Colony Optimization Cassio Conti [email protected]

Otimização por Colônia de Formigas Ant Colony Optimization

Embed Size (px)

DESCRIPTION

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 - PowerPoint PPT Presentation

Citation preview

Page 1: Otimização por Colônia de Formigas Ant Colony Optimization

Otimização por Colônia de FormigasAnt Colony Optimization

Cassio [email protected]

Page 2: Otimização por Colônia de Formigas Ant Colony Optimization

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

Page 3: Otimização por Colônia de Formigas Ant Colony Optimization

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-3o 1-3-2o 2-1-3o 2-3-1o 3-1-2o 3-2-1

Page 4: Otimização por Colônia de Formigas Ant Colony Optimization

Problemas de otimização

3 elementos: 6 combinações4 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.

Page 5: Otimização por Colônia de Formigas Ant Colony Optimization

Ideia do ACOBaseia-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.

Page 6: Otimização por Colônia de Formigas Ant Colony Optimization

Caixeiro Viajante

Traveling Salesman Problem (TSP)

Se existem 2 cidades, A e B, considerando que o caixeiro inicialmente está em A, tem-se 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.

Page 7: Otimização por Colônia de Formigas Ant Colony Optimization

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

Page 8: Otimização por Colônia de Formigas Ant Colony Optimization

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 = 16Caminho 12354 = 12Caminho 12435 = 15Caminho 12453 = 11Caminho 14235 = 13....

Ex: x = 1 / f(caminho)

Page 9: Otimização por Colônia de Formigas Ant Colony Optimization

+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 

Page 10: Otimização por Colônia de Formigas Ant Colony Optimization

Heurística (Visibilidade)

gerar_solucao(f) { escolher_proximo(f)}

gerar_solucao(f, dist) { v <- 1 / dist escolher_proximo(f + v)}

1 2 3 4 51 0 0,8 0 0,4 0,52 0,8 0 0,4 0,4 03 0 0,4 0 0,2 0,64 0,4 0,4 0,2 0 0,25 0,5 0 0,6 0,2 0

Page 11: Otimização por Colônia de Formigas Ant Colony Optimization

+0.8 (÷2.1 = 38%)+0.6 (÷2.1 = 29%)+0.7 (÷2.1 = 33%)------- 2.1 (100%)

1÷2=0.51÷6=0.21÷3=0.3

+1.3 (÷3.1 = 42%)+0.8 (÷3.1 = 26%)+1.0 (÷3.1 = 32%)------3.1 (100%)

Heurística (Visibilidade)

Page 12: Otimização por Colônia de Formigas Ant Colony Optimization

12

ACO Discreto - Importância da Visibilidade

oliver30 eil51 a2800

1000

2000

3000

4000

5000

6000

Tamanho do percurso do caixeiro

Sem visibil-idadeCom visibil-idade

oliver30 eil51 a2800

100

200

300

400

500

600

Iteração onde o melhor percurso foi encontrado

Page 13: Otimização por Colônia de Formigas Ant Colony Optimization

13

ACO Contínuo – ACOR – Feromônio

s1 s11 s1

2 ... s1i ... s1

n

s2 s21 s2

2 ... s2i ... S2

n

...sj sj

1 sj2 ... sj

i ... Sjn

...sk sk

1 sk2 ... sk

i ... Skn

Arquivo população

nzXbXaXXf 21

Page 14: Otimização por Colônia de Formigas Ant Colony Optimization

14

s1 s11 s1

2 ... s1i ... s1

n

s2 s21 s2

2 ... s2i ... S2

n

...sj sj

1 sj2 ... sj

i ... Sjn

...sk sk

1 sk2 ... sk

i ... Skn

ACOR - Amostragem

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

k

j

il

iji

l

il

k

ss

s

1 1

Page 15: Otimização por Colônia de Formigas Ant Colony Optimization

15

ACOR – Sequência de passosInicializaçã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:

Seta a média sj

i.

Calcula o valor de desvio

padrão.

Amostra um novo valor.

Atualização

da população

• Avalia e adiciona as novas soluções ao arquivo população.• Ordena as soluções pela qualidade e mantém somente as k melhores.

Verificação do critério de parada

• Se o critério de parada não for alcançado, voltar ao segundo passo.• Caso contrário, encerrar o algoritmo.

sl = {sl1, sl

2, ..., sln}

X = {X1, X2, ..., Xn}

Page 16: Otimização por Colônia de Formigas Ant Colony Optimization

16

Proposta de Visibilidade para ACO contínuo

s1s2

s3

s1’ s2’s3’

s3

s2

s1

s3’

s2’

s1’

Quando todas as soluções do arquivo estiverem na mesma região a visibilidade é desligada.

Page 17: Otimização por Colônia de Formigas Ant Colony Optimization

17

Proposta para Visibilidade

s1 s11 s1

2 ... s1i ... s1

n

s2 s21 s2

2 ... s2i ... S2

n

...sj sj

1 sj2 ... sj

i ... Sjn

...sk sk

1 sk2 ... sk

i ... Skn

nXXXX ,,, 21

',,','' 21 nXXXX

Page 18: Otimização por Colônia de Formigas Ant Colony Optimization

18

Experimentos – Testes e Resultados

Problemas1 B22 Branin RCOS3 Cigar4 De Jong5 Eason6 Ellipsoid7 Goldstein and Price8 Martin and Gaddy9 Sphere model10 Tablet11 Zakharov Os mesmo parâmetros utilizados

por Socha e Dorigo foram aplicados para que fosse possível a comparação.

Page 19: Otimização por Colônia de Formigas Ant Colony Optimization

19

Experimentos – Testes e Resultados - Iterações

B2

Branin RCOS

Cigar

De Jong

Eason

Ellipsoid

Goldstein and Price

Martin and Gaddy

Sphere model

Tablet

Zakharov

0 500 1000 1500 2000 2500

Com visibilidadeSem visibilidade

Número médio de iterações

Page 20: Otimização por Colônia de Formigas Ant Colony Optimization

20

Experimentos – Testes e Resultados - Avaliações

B2

Branin RCOS

Cigar

De Jong

Eason

Ellipsoid

Goldstein and Price

Martin and Gaddy

Sphere model

Tablet

Zakharov

0 1000 2000 3000 4000 5000

Com visibilidadeSem visibilidade

Número médio de avaliações

Page 21: Otimização por Colônia de Formigas Ant Colony Optimization

Aplicação Real – Exploração de Petróleo

Page 22: Otimização por Colônia de Formigas Ant Colony Optimization

Aquisição Sísmica

Page 23: Otimização por Colônia de Formigas Ant Colony Optimization

Aquisição Sísmica

Page 24: Otimização por Colônia de Formigas Ant Colony Optimization

Sísmica

Page 25: Otimização por Colônia de Formigas Ant Colony Optimization

Poço

Page 26: Otimização por Colônia de Formigas Ant Colony Optimization

Sísmica e Poço

Page 27: Otimização por Colônia de Formigas Ant Colony Optimization

Impedância

𝑖𝑚𝑝𝑒𝑑 â𝑛𝑐𝑖𝑎=𝑑𝑒𝑛𝑠𝑖𝑑𝑎𝑑𝑒×𝑣𝑒𝑙𝑜𝑐𝑖𝑑𝑎𝑑𝑒

Page 28: Otimização por Colônia de Formigas Ant Colony Optimization

Propriedade dos Dados (rochas)

𝑟𝑒𝑓 𝑖=𝑖𝑚𝑝𝑖+1−𝑖𝑚𝑝𝑖

𝑖𝑚𝑝𝑖+1+𝑖𝑚𝑝𝑖

Page 29: Otimização por Colônia de Formigas Ant Colony Optimization

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

Page 30: Otimização por Colônia de Formigas Ant Colony Optimization

Estimação do Pulso Sísmico

Page 31: Otimização por Colônia de Formigas Ant Colony Optimization

Estimação do Pulso Sísmico

Page 32: Otimização por Colônia de Formigas Ant Colony Optimization

Inversão Sísmica

Page 33: Otimização por Colônia de Formigas Ant Colony Optimization

Heurísticas para acelerar a busca

Gera diversas configurações similares ao poço.

Page 34: Otimização por Colônia de Formigas Ant Colony Optimization

Inversão utilizando ACO

• Para os demais traços, usa-se o traço vizinho (que já foi otimizado) como modelo de referência.

Page 35: Otimização por Colônia de Formigas Ant Colony Optimization

R=0.97289

• 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

Page 36: Otimização por Colônia de Formigas Ant Colony Optimization

R=0.95604

• 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

Page 37: Otimização por Colônia de Formigas Ant Colony Optimization

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.

Page 38: Otimização por Colônia de Formigas Ant Colony Optimization

Otimização por Colônia de FormigasAnt Colony Optimization

Cassio [email protected]

Page 39: Otimização por Colônia de Formigas Ant Colony Optimization

• 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