Upload
internet
View
105
Download
1
Embed Size (px)
Citation preview
_____________________________________________________________________________
Otimização com Simulated Annealing e Tabu Search
Marcílio SoutoDIMAp/UFRN
_____________________________________________________________________________
Otimização
– Problema de Otimização:
• Sendo S o conjunto de soluções possíveis, em que cada solução tem um custo, o objetivo é encontrar a solução com menor custo possível.
• Ex.: Problema do Caixeiro Viajante.
A
B
CD
E
3
3
2
5
4
454
65
– Soluções possíveis:• Todos os percursos fechados
passando por cada cidade uma única vez.
– Função de custo:• Distância total do percurso.
_____________________________________________________________________________
Algoritmo Hill Climbing (Subida da Encosta)
– Estrutura básica:
Escolhe aleatoriamente uma solução inicial.
Enquanto critérios de parada não forem satisfeitos,
Gera uma nova solução (vizinha) a partir da atual.
Se (custo da solução nova < custo da solução atual),
Aceita solução nova.
Se não,
Rejeita solução nova (continua com a atual).
– Limitação:
• Facilidade de ficar preso em mínimos locais.
– Todas as soluções vizinhas têm custo maior.
_____________________________________________________________________________
Simulated Annealing e Tabu Search
– Simulated Annealing:
• Procura minimizar esta limitação, permitindo aceitar vizinhos piores com uma certa probabilidade.
– Tabu Search:
• Procura minimizar esta limitação, aceitando sempre os vizinhos gerados e guardando a melhor solução encontrada.
_____________________________________________________________________________
Simulated Annealing
– Idéia básica:
• Se a nova solução for melhor que a atual (custo menor), esta nova solução é aceita.
• Se for pior, a nova solução pode ser aceita com uma dada probabilidade.
• Esta probabilidade é controlada por um parâmetro chamado de temperatura, que diminui ao longo das iterações.
_____________________________________________________________________________
Simulated Annealing
– Estrutura básica:
Escolhe aleatoriamente uma solução inicial.Enquanto critérios de parada não forem satisfeitos, Gera uma nova solução (vizinha) a partir da atual. Se (custo da solução nova < custo da solução atual), Aceita solução nova. Se não, Pode aceitar solução nova com probabilidade
p = exp (–(custo da sol. nova – custo da sol. atual) / temperatura)
Retorna solução atual.
– Obs.: O parâmetro temperatura diminui a cada N iterações.
_____________________________________________________________________________
Simulated Annealing
– Probabilidade de aceitar a nova solução (se o custo aumentar):
p = exp (–(custo da sol. nova – custo da sol. atual) / temperatura)
• Mantendo fixo o aumento no custo, se a temperatura diminuir, a probabilidade diminui.
– Ao longo das iterações, fica mais difícil aceitar soluções que aumentam o custo.
• Mantendo fixa a temperatura, se a variação no custo aumentar, a probabilidade diminui.
– Em uma mesma iteração, quanto maior o aumento no custo, mais difícil é aceitar a nova solução.
aumento no custo
_____________________________________________________________________________
Simulated Annealing
– Implementação da probabilidade de escolha (critério de Metropolis):
• Gera-se um número aleatório retirado de uma distribuição uniforme no intervalo [0, 1].
• Se este número for menor ou igual a “p”, aceita-se a solução.
• Se for maior que “p”, rejeita-se a solução.
_____________________________________________________________________________
Simulated Annealing– Resolvendo um problema com Simulated Annealing:
• Representação das soluções:– Como as soluções do problema serão representadas no
espaço de busca.
• Função de custo:– Como será calculado o custo de cada solução.
• Operador (mecanismo de geração de vizinhos):– Como novas soluções serão geradas a partir da atual.
• Esquema de esfriamento:– Como a temperatura será reduzida ao longo das iterações.
• Máximo número de iterações permitidas.
_____________________________________________________________________________
Problema do Caixeiro Viajante
A
B
CD
E
3
3
2
5
4
454
65
– Representação das soluções:• Seqüência de cidades do percurso.• Ex.: s = [B,D,E,C,A]
– Função de custo:• Distância total do percurso.• Ex.: custo (s) = 6 + 4 + 5
+ 4 + 2 = 21
– Operador:• Permutar 2 cidades consecutivas
escolhidas aleatoriamente.• Ex.: s’ = [B,E,D,C,A]
– Esquema de esfriamento:• Temperatura inicial: T0 = 1• Regra de esfriamento: Ti+1 = 0.9 Ti
– Máximo de 5 iterações.
_____________________________________________________________________________
Problema do Caixeiro Viajante
Iteração Temp. Solução Custo Aleatório Probabilidade Aceita?
0 1 BDECA 21
1 0.9 BDEAC 20 S
2 0.81 BDAEC 22 0.02 e – (22 – 20)/0.81 = 0.085 S
3 0.73 BADEC 19 S
4 0.66 BADCE 21 0.13 e – (21 – 19)/0.66 = 0.047 N
Solução final: BAEDC – Custo: 17
5 0.59 BAEDC 17 S
_____________________________________________________________________________
Tabu Search
– Idéia básica:
• A partir da solução atual, gerar um conjunto de novas soluções.
• Aceitar sempre a melhor solução deste conjunto.– Pode ser melhor ou pior que a solução atual.
– Pode haver ciclos na trajetória (aceitar soluções que já foram visitadas).
• Guardar na memória:– A melhor solução encontrada desde o início da execução.
– Uma lista tabu, contendo as K soluções mais recentemente visitadas. Estas soluções são proibidas (para evitar ciclos).
• A solução final dada pelo algoritmo é a melhor solução encontrada desde o início da execução, e não a atual.
_____________________________________________________________________________
Tabu Search
– Estrutura básica:
Escolhe aleatoriamente uma solução inicial.Guarda a solução em melhor solução e na lista tabu.Enquanto critérios de parada não forem satisfeitos, Gera um conjunto de N soluções vizinhas a partir da atual. Escolhe o vizinho de menor custo que não esteja na lista tabu. Atualiza melhor solução e lista tabu.Retorna melhor solução.
– Obs.: A lista tabu guarda as K soluções mais recentemente visitadas ou as K alterações mais recentes, dependendo da abordagem.
_____________________________________________________________________________
Problema do Caixeiro Viajante
A
B
CD
E
3
3
2
5
4
454
65
– Representação das soluções:• Seqüência de cidades do percurso.• Ex.: s = [B,D,E,C,A]
– Função de custo:• Distância total do percurso.• Ex.: custo (s) = 6 + 4 + 5 + 4 +
2 = 21
– Operador:• Permutar 2 cidades consecutivas, gerando 5
vizinhos por iteração.• Ex.: s1 = [D,B,E,C,A]
s2 = [B,E,D,C,A]
s3 = [B,D,C,E,A]
s4 = [B,D,E,A,C]
s5 = [A,D,E,C,B]
– Máximo de 2 iterações.
_____________________________________________________________________________
Problema do Caixeiro ViajanteIteração Solução Atual
– CustoLista Tabu
Melhor Solução – Custo
Vizinhos – Custo
0 BEDCA – 19
BEDCA
BEDCA – 19
EBDCA – 22
BDECA – 21
BECDA – 21
BEDAC – 20
AEDCB – 17
1 AEDCB – 17
BEDCA
AEDCB – 17
EADCB – 20
AEDCB ADECB – 19
AECDB – 21
AEDBC – 20
BEDCA – 19 X
_____________________________________________________________________________
Problema do Caixeiro ViajanteIteração Solução Atual
– CustoLista Tabu
Melhor Solução – Custo
Vizinhos – Custo
1 AEDCB – 17
BEDCA
AEDCB – 17
EADCB – 20
AEDCB ADECB – 19
AECDB – 21
AEDBC – 20
BEDCA – 19 X
2 ADECB – 19
BEDCA
AEDCB – 17
DAECB – 22
AEDCB AEDCB – 17 X
ADECB ADCEB – 21
ADEBC – 20
BDECA – 21
Solução final: AEDCB – Custo: 17
_____________________________________________________________________________
Observações Importantes
– Esforço computacional por iteração:
• Uma iteração de Tabu Search exige mais esforço computacional do que uma iteração de Simulated Annealing (mais vizinhos são avaliados).
• Por este motivo, em geral, Tabu Search precisa de menos iterações para convergir do que Simulated Annealing.
– Variações dos algoritmos:
• Existem diversas variações de Simulated Annealing e Tabu Search.
• Nesta aula, só foram vistas noções básicas.
_____________________________________________________________________________
Simulated Annealing e Tabu Search para Treinamento de Redes MLP
w1
w2
w3
w4
w5
w6
s = [w1, w2, w3, w4, w5, w6]
– Representação:
• Cada rede é representada por um vetor contendo seus pesos.
• Ex.: Para a topologia abaixo, temos:
(2 x 2) + (2 x 1) = 6 conexões.
Obs.: Os termos de polarização (bias) também são representados na solução, pois geralmente são ajustáveis.
_____________________________________________________________________________
Simulated Annealing e Tabu Search para Treinamento de Redes MLP
– Função de custo:
• Erro para o conjunto de treinamento.
– Ex.: SSE ou Erro de Classificação.
• SSE:
Saídas da rede: 0.98 0.12 ... 0.16
Saídas desejadas: 1.00 0.00 ... 0.00
SSE = (0.98 – 1.00)2 + (0.12 – 0.00)2 + ... + (0.16 – 0.00)2.
• Erro de Classificação:
Erro Class. = 100 . Nº de padrões classificados erradamente pela rede
Nº total de padrões
_____________________________________________________________________________
Simulated Annealing e Tabu Search para Treinamento de Redes MLP
– Operador (geração de soluções novas):
• A cada peso, adicionar um número aleatório retirado de uma distribuição uniforme no intervalo [-n , +n].
• Ex.: Aleatórios na faixa [-1, +1].
Solução atual = [0.2, -0.1, 0.7, 0.5, -0.3, -0.9]
Aleatórios = [0.1, 0.2, -0.3, -0.7, 0.6, 0.2]
Solução nova = [0.3, 0.1, 0.4, -0.2, 0.3, -0.7]
_____________________________________________________________________________
Observações Importantes– Overfitting:
• Assim como backpropagation, Simulated Annealing e Tabu Search procuram o conjunto de pesos que minimiza o erro de treinamento.
• Da mesma forma, deve-se evitar o overfitting (erro alto para dados não usados no treinamento).
– Funções de ativação:
• Diferentemente do treinamento com backpropagation, os neurônios não precisam ter funções de ativação contínuas (diferenciáveis).
• Ex.:
0
1
f (x)
x
Função do tipo degrau (step).
_____________________________________________________________________________
Bibliografia Sugerida
– Introdução de Simulated Annealing e Tabu Search: • D.T. Pham and D. Karaboga, “Introduction”, Intelligent
Optimisation Techniques (Edited by D.T. Pham and D. Karaboga), pp. 1-50, Springer-Verlag, 2000.
– Simulated Annealing para treinar redes neurais:• S. Chalup and F. Maire, “A Study on Hill Climbing Algorithms
for Neural Network Training”, Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), Volume 3, pp. 2014-2021, Washington, D.C., USA, July 6-9, 1999.
– Tabu Search para treinar redes neurais:• R. S. Sexton, B. Alidaee, R. E. Dorsey and J. D. Johnson, “Global
optimization for artificial neural networks: a tabu search application”, Eur. J. Operational Research (106)2-3, pp. 570-584, 1998.