_____________________________________________________________________________
Otimização com
Simulated Annealing e Tabu Search
Marcílio Souto
DIMAp/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
3
2
5
4
4
E
5
B
6
4
3
D
5
C
– 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)
aumento no custo
• 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.
_____________________________________________________________________________
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
– Representação das soluções:
• Seqüência de cidades do percurso.
• Ex.: s = [B,D,E,C,A]
– Função de custo:
A
3
• Distância total do percurso.
• Ex.: custo (s) = 6 + 4 + 5 + 4 + 2 = 21
2
5
4
4
E
5
B
6
4
3
D
5
C
– Operador:
• Permutar 2 cidades consecutivas
escolhidas aleatoriamente.
• Ex.: s’ = [B,E,D,C,A]
– Esquema de esfriamento:
• Temperatura inicial:
• Regra de esfriamento:
– Máximo de 5 iterações.
T0 = 1
Ti+1 = 0.9 Ti
_____________________________________________________________________________
Problema do Caixeiro Viajante
Iteração Temp.
Solução
Custo
0
1 BDECA
21
1
0.9 BDEAC
20
2
0.81 BDAEC
22
3
0.73 BADEC
19
4
0.66 BADCE
21
5
0.59 BAEDC
17
Aleatório
Solução final: BAEDC – Custo: 17
Probabilidade
Aceita?
S
0.02 e – (22 – 20)/0.81 = 0.085
S
S
0.13 e – (21 – 19)/0.66 = 0.047
N
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
– Representação das soluções:
• Seqüência de cidades do percurso.
• Ex.: s = [B,D,E,C,A]
– Função de custo:
A
3
• Distância total do percurso.
• Ex.: custo (s) = 6 + 4 + 5 + 4 + 2 = 21
2
5
4
4
E
5
B
6
4
3
D
5
C
– 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 Viajante
Iteração
Solução Atual
– Custo
Lista
Tabu
BEDCA
Melhor Solução –
Custo
Vizinhos – Custo
EBDCA – 22
BDECA – 21
0 BEDCA – 19
BEDCA – 19 BECDA – 21
BEDAC – 20
AEDCB – 17 
1 AEDCB – 17
BEDCA
EADCB – 20
AEDCB
ADECB – 19 
AEDCB – 17 AECDB – 21
AEDBC – 20
BEDCA – 19 X
_____________________________________________________________________________
Problema do Caixeiro Viajante
Iteração
Solução Atual
– Custo
Lista
Tabu
Melhor Solução –
Custo
Vizinhos – Custo
BEDCA
EADCB – 20
AEDCB
ADECB – 19 
1 AEDCB – 17
AEDCB – 17 AECDB – 21
AEDBC – 20
BEDCA – 19 X
2 ADECB – 19
BEDCA
DAECB – 22
AEDCB
AEDCB – 17 X
ADECB
AEDCB – 17 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
– 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.
w1
w5
w3
w2
s = [w1, w2, w3, w4, w5, w6]
w6
w4
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:
Saídas desejadas:
0.98 0.12 ... 0.16
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.:
f (x)
1
0
Função do tipo degrau (step).
x
_____________________________________________________________________________
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. 20142021, 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.