aula t 2 _SA_

Prévia do material em texto

1
Simulated Annealing (S.A.)
O annealing (anelamento, têmpera, recozimento, cristalização)
de certos materiais consiste em submetê-los inicialmente a
altas temperaturas e reduzi-las gradualmente até atingirem,
com aumentos e reduções do estado de energia, o equilíbrio
térmico, tornando-os assim, consistentes e rígidos.
A técnica matemática de Simulated Annealing faz uma
simulação algorítmica do processo físico da têmpera de
materiais. A idéia de aplicar este método para resolver
problemas de otimização combinatória surgiu com Kirkpatrick
et al., 1983 e Aragon et al., 1984.
(têmpera simulada ou anelamento simulado) 
Exemplo 1: Suponha o Problema de Caixeiro Viajante (PCV) constituído de cinco pontos,
dada a matriz com as distâncias inteiras mínimas aproximadas entre todos os pares de pontos.
Determine uma solução ( ótima ou quase ótima) do PVC aplicando a meta-heurística
Simulated Annealing.
A B C D E
A 0 1 1 4 2
B 1 0 4 1 4
C 1 4 0 5 3
D 4 1 5 0 4
E 2 4 3 4 0
•Dados os parâmetros a serem adotados para resolução do problema:
•Nº máximo de iterações → M = 3
•Fator de redução de temperatura → α = 0,9
•Nº máximo de perturbações por iteração → P=3
•Limite de sucessos por iteração (perturbações aceitas a cada iteração) →L = 3
•Adote o número randômico rdn = 0,5 como limite para aceitação ou rejeição 
de uma solução quando esta causar um aumento de energia no processo. 
OBS: Caso não tivéssemos dada a matriz com as 
distâncias mínimas poderíamos obtê-la através da 
aplicação do algoritmo de FLOYD como já foi visto na 
disciplina de Métodos Heurísticos.
3
Determinação da estimativa da temperatura inicial T0: A estimativa da temperatura inicial,
segundo Johnson et al. (1987) poderá ser calculada da seguinte forma:
1) (C,D,E,A,B) C → Energia = 5+4+2+1+4=16
2) (A,B,C,D,E) A → Energia = 1+4+5+4+2=16
3) (E,D,C,B,A) E → Energia = 4+5+4+1+2=16
4) (C,A,E,D,B) C → Energia = 1+2+4+1+4=12
5) (C,D,B,E,A) C → Energia = 5+1+4+2+1=13
 0,8. menteaproximada a igual almente)experiment (obtido empírico fixovalor 
(energia). objetivo função da 
os)(increment variações das es,perturbaçõ de radômico nº um para ,aritmética médiaE :onde 

 
0ξ
A B C D E
A 0 1 1 4 2
B 1 0 4 1 4
C 1 4 0 5 3
D 4 1 5 0 4
E 2 4 3 4 0
 0variação 
 0variação 
 4variação 
 1variação 
   
68,5
22,0
25,1
8,0ln
25,1
ln
25,1
4
1400













0ξ
E
T
E
:Logo
0
Exemplo: Suponha que através de um processo aleatório obtivemos a seguinte amostra de 
cinco soluções viáveis:
Obs: Esta temperatura T0 =5,68 deverá ser adotada para
toda a 1ª iteração. Na sequencia, ao início de cada
iteração, esta temperatura sofrerá um decréscimo (taxa
de resfriamento) gradual e controlado conforme será
observado no desenvolvimento da solução do problema.
 
 
E
T 0
0ξln


Variação em módulo:
 esta. adotaremos aqui
),(T inicial atemperatur aestimar de formas outras Existem :OBS 0
4
Solução do exemplo 1:
Solução inicial (S0) (escolha aleatória de uma solução qualquer):
S0 = (C,D,E,A,B) C → Energia →E0 = 5+4+2+1+4=16
Solução (S1)= Uma perturbação sobre S0 = (C,D,E,A,B) C → E0 =16, é um processo aleatório.
Por exemplo: Troca, entre si, as posições entre C e A.
S1 = (A,D,E,C,B) A → E1 = 4+4+3+4+1=16
Variação de energia: ∆E= E1 – E0 =16-16=0 →Nem aumentou e nem diminuiu a energia,
então podemos aceitar a solução S1.
Nº de sucessos (nº de aceitações) , L= 1
Nº de perturbações executadas , P = 1
OBS: Se E = 0: caso de estabilidade ou equilíbrio. Neste caso temos duas configurações 
vizinhas com a mesma energia ou custo (coincidência pouco provável de acontecer na prática). 
O novo estado pode ser aceito e o processo continua (exploitation-profundidade);
Insere-se uma pequena perturbação(ou alteração) nas posições de algumas
partículas (pontos) da solução resultando uma variação de energia, ou seja, uma
alteração no valor da função objetivo. Isto pode ser feito de três modos:
1º modo: Troca-se, entre si, as posições de dois (ou mais) pontos;
2º modo: Insere-se um ponto retirado de sua posição em outra posição.
3º modo: Pode-se aplicar os dois modos anteriormente descritos de forma mesclada.
Solução (S2)= Uma perturbação sobre S1 = (A,D,E,C,B) A → E1 =16
Por exemplo: Troca, entre si, as posições entre A e B.
S2 = (B,D,E,C,A) B → E2 = 1+4+3+1+1=10
Variação de energia: ∆E= E2 – E1 =10-16= - 6 →Diminuiu a energia, então aceitamos a
solução S2.
Nº de sucessos (nº de aceitações acumuladas) , L= 2
Nº de perturbações executadas (acumuladas) , P=2
A B C D E
A 0 1 1 4 2
B 1 0 4 1 4
C 1 4 0 5 3
D 4 1 5 0 4
E 2 4 3 4 0
OBS: Se E < 0: neste caso houve redução de energia; o novo estado é 
aceito e o processo continua (exploitation-profundidade);
6
A B C D E
A 0 1 1 4 2
B 1 0 4 1 4
C 1 4 0 5 3
D 4 1 5 0 4
E 2 4 3 4 0
Solução(S3)= Uma perturbação sobre S2 = (B,D,E,C,A) B → E2 = 10.
Por exemplo: Troca, entre si, as posições entre B e E .
S3 = (E,D,B,C,A) E → E3 = 4+1+4+1+2=12
Variação de energia: ∆E= E3 – E2 =12-10=+2 →Aumentou a energia, então iremos aceitar ou
rejeitar a solução S3 de acordo com a seguinte probabilidade (Fator de Boltzmann-FB) :
Nº de sucessos (nº de aceitações acumuladas) ,L= 3
Nº de perturbações executadas (acumuladas), P =3
Obs: A iteração finaliza quanto atingimos o valor de nº máx. perturbações/iteração → P=3 ou o
nº limite de sucessos/ iteração→ L = 3, arbitrados no início do problema.
   
 problema. do início no arbitrado e enterandomicam gerado Número 0,5 rdn 2) 
iteração. primeira desta início do antes Estimada68,5TT 1) :Onde
.0,5rdn0,7FB Como .70,072,272,2eFB
0i
35,0 5,68
2
 


 

3S solução a Aceitamos
iT
ΔE
 
OBS: Se E > 0: neste caso houve aumento de energia que no processo físico é útil para 
permitir uma futura “acomodação” das partículas (evitando a convergência da função objetivo 
para mínimos locais indesejáveis- (exploration-diversidade)).A probabilidade de aceitar uma 
mudança deste tipo (E > 0) é chamada de “critério de Metrópolis”, estabelecido a partir do 
fator de Boltzmann que é dado pela função exp (- E / T), onde T é a temperatura válida para 
a iteração em que ocorreu a mudança, ou seja, estimada antes do início da iteração em curso 
(em andamento). 
Fim da 1ª iteração, com a solução:
S3 = (E,D,B,C,A) E → E3 =12 
7
Função de
Boltzmann
Fluxograma para o algoritmo de Metropolis.
O algoritmo, proposto por Metropolis e outros (1953), pertence a classe de
métodos estatísticos denominada Métodos de Monte Carlo, os quais, tem a
característica de usar um grande número de amostragens aleatórias.
<
rdn
0 < rdn < 1
ΔE
ΔE
•O resfriamento gradativo de um material a partir de uma alta temperatura inicial leva o 
material a estados mínimos de energia. 
•Informalmente esses estados são caracterizados por uma perfeição estrutural do material 
congelado que não se obteria caso o resfriamento não tivesse sido gradativo. 
•Sob outras condições menos cuidadosas de resfriamento, o material se cristalizaria com 
uma energia “localmente mínima”, apresentando imperfeições estruturais. A esse 
processo cuidadoso de resfriamento dá-se o nome de “annealing” (Têmpera simulada 
ou Anelamento simulado) .
•A simulação (Simulated Annealing) a uma temperatura fixa T consiste em dar um pequeno 
deslocamento a um dos átomos, computando a variação E da energia do sistema. 
1. Se E  0, o deslocamento é incorporado ao estado do sistema, que é então utilizado no 
passo seguinte.
2. Caso contrário, se E > 0, a aceitação ou não do deslocamento passa aser uma decisão 
probabilística, segundo a função de Boltzmann já definida anteriormente.
Comentários:
Resfriamento rápido (amorfo) Resfriamento Lento (critalino)
9
Função de Boltzmann 
Probabilidade de aceitação de uma transição de maior energia:
Comentários:
P
ro
b
a
b
il
id
a
d
e
 d
e
 a
c
e
it
a
ç
ã
o
.
P
ro
b
a
b
il
id
a
d
e
 d
e
 a
c
e
it
a
ç
ã
o
.
ΔE ΔE/T
A aceitação temporária de soluções “piores” significa que o método 
admite caminhar “morro acima”, na esperança de encontrar “vales” 
mais profundos.
iT
ΔE
 
 eFB
10
Início da 2ª iteração:
5,115,68 9,0TT αT 101 
Solução inicial (S0)= Solução obtida no final da 1ª iteração, ou seja, “S3” = (E,D,B,C,A) E :
S0 = (E,D,B,C,A) E → E0 = 12
Solução (S1)= Uma perturbação sobre S0 = (E,D,B,C,A) E → E0 = 12, é um processo aleatório.
Por exemplo: Troca, entre si, as posições entre B e C.
S1 = (E,D,C,B,A) E → E1 = 4+5+4+1+2=16
Variação de energia: ∆E= E1 – E0 =16-12=+4 → Aumentou a energia, então podemos
aceitar ou rejeitar a solução S1 de acordo com a seguinte probabilidade (Fator de
Boltzmann-FB) :
Nº de sucessos (nº de aceitações acumuladas) , L= 0
Nº de perturbações executadas (acumuladas) ,P=1
A B C D E
A 0 1 1 4 2
B 1 0 4 1 4
C 1 4 0 5 3
D 4 1 5 0 4
E 2 4 3 4 0
   
 problema. do início no arbitrado e enterandomicam gerado Número 0,5 rdn 2) 
iteração. segunda desta início do antes Estimada11,5TT 1) :Onde
0,5rdn0,45FB Como .45,072,272,2eFB
0i
78,0 5,11
4
 
T
E
 
i


 



.S solução a aceitamos Não 1
Atualização da temperatura Ti : Uma das formas de se obter o
fator de decréscimo da temperatura, proposta por Romeo et al.,
1985, onde  = 0,9, em geral é dada por:
1-ii T αT 
11
Solução (S2)= Uma perturbação sobre S0 = (E,D,B,C,A) E → E0 = 12, é
um processo aleatório.
Por exemplo: Troca, entre si, as posições entre A e C.
S2 = (E,D,B,A,C) E → E2 = 4+1+1+1+3=10
Variação de energia: ∆E= E2 – E0 =10-12=-2 → Diminuiu a energia, então aceitamos a solução S2.
Nº de sucessos (nº de aceitações acumuladas) ,L= 1
Nº de perturbações executadas (acumuladas), P=2
A B C D E
A 0 1 1 4 2
B 1 0 4 1 4
C 1 4 0 5 3
D 4 1 5 0 4
E 2 4 3 4 0
Solução (S3)= Uma perturbação sobre S2 = (E,D,B,A,C) E → E2 =10, é um processo aleatório.
Por exemplo: Troca, entre si, as posições entre D e C.
S3 = (E,C,B,A,D) E → E3 = 3+4+1+4+4=16
Variação de energia: ∆E= E3 – E2 =16-10=+6 → Aumentou a energia, então podemos aceitar ou rejeitar a
solução S3 de acordo com a seguinte probabilidade (Fator de Boltzmann-FB) :
Nº de sucessos (nº de aceitações acumuladas) , L= 1
Nº de perturbações executadas (acumuladas) ,P=3
   
 problema. do início no arbitrado e enterandomicam gerado Número 0,5 rdn 2) 
iteração. segunda desta início do antes Estimada11,5TT 1) :Onde
.0,5rdn0,31FB Como .31,072,272,2eFB
1i
17,15,11
6
T
E
i


 



3S solução a aceitamos Não
Fim da 2ª iteração, com a solução:
S2 = (E,D,B,A,C) E → E2 =10
Obs: A iteração finaliza quanto atingimos o valor de nº máx. perturbações/iteração → P=3 ou
o nº limite de sucessos/ iteração→L = 3, arbitrados no início do problema.
12
Solução (S1)= Uma perturbação sobre S0 = (E,D,B,A,C) E → E0 =10, é um processo aleatório.
Por exemplo: Inserir o E imediatamente antes do A.
S1 = (D,B,E,A,C) D → E1 = 1+4+2+1+5=13
Variação de energia: ∆E= E1 – E0 =13 -10=+3 → Aumentou a energia, então podemos aceitar ou rejeitar
a solução S1 de acordo com a seguinte probabilidade (Fator de Boltzmann-FB) :
Nº de sucessos (nº de aceitações acumuladas), L = 1
Nº de perturbações executadas (acumuladas), P=1
   
 problema. do início no arbitrado e enterandomicam gerado Número 0,5 rdn 2) 
iteração. segunda desta início do antes Estimada60,4TT 1) :Onde
0,5rdn0,52FB Como .52,072,272,2eFB
2i
65,0 4,60
3
 
T
E
 
i


 



.S solução a Aceitamos 1
A B C D E
A 0 1 1 4 2
B 1 0 4 1 4
C 1 4 0 5 3
D 4 1 5 0 4
E 2 4 3 4 0
Início da 3ª iteração:
Atualização da temperatura Ti :  = 0,9
60,45,11 9,0TT αTT αT 2121-ii 
Solução inicial (S0)= Solução obtida no final da 2ª iteração, ou seja, “S2”= (E,D,B,A,C) E :
S0 = (E,D,B,A,C) E → E0 =10
Solução (S2)= Uma perturbação sobre S1 = (D,B,E,A,C) D → E1=13, é
um processo aleatório.
Por exemplo: Troca, entre si, as posições entre A e E.
S2 = (D,B,A,E,C) D → E2 = 1+1+2+3+5=12
Variação de energia: ∆E= E2 – E3 =12-13=-1 → Diminuiu a energia, então aceitamos a solução S2.
Nº de sucessos (nº de aceitações acumuladas) ,L= 2
Nº de perturbações executadas (acumuladas), P=2
A B C D E
A 0 1 1 4 2
B 1 0 4 1 4
C 1 4 0 5 3
D 4 1 5 0 4
E 2 4 3 4 0
Solução (S3)= Uma perturbação sobre S2 = (D,B,A,E,C) D → E2 =12, é um processo aleatório.
Por exemplo: Inserir o C imediatamente antes do D.
S3 = (C,D,B,A,E) C → E3 = 5+1+1+2+3=12
Variação de energia: ∆E= E3 – E2 =12-12=0→ Nem aumentou e nem diminuiu a energia,
então podemos aceitar a solução S3.
Nº de sucessos (nº de aceitações acumuladas) , L= 3
Nº de perturbações executadas (acumuladas) ,P=3
Fim da 3ª iteração, com a solução:
S3 = (C,D,B,A,E) C → E3 =12
Obs: 1) A iteração finaliza quanto atingimos o valor de nº máx. perturbações/iteração →
P=3 ou o nº limite de sucessos/ iteração→L = 3, arbitrados no início do problema.
2) Como inicialmente a solução foi limitada em três iterações (M=3) interrompemos
aqui a continuidade da solução. Fim
Atenção: Caso prosseguíssemos com as iterações a solução inicial S0 
para próxima iteração seria S0 =S3 = (C,D,B,A,E) C → E3 =12 
14
Obs: No final do processo (após várias iterações),
espera-se que o sistema estacione em um estado
de energia globalmente mínima, por analogia com
a física do problema. (A temperatura se aproxima
de zero e soluções de piora não são mais
aceitas.) Assim a melhor solução tende a ser a
última obtida da última interação.
15
Um exemplo de simulação para maximização:
Start temperature: 25
Temperature step: 0.1
End temperature: 0
Iterations : 1,000,000
16
Exemplo 2: Dado o seguinte problema de designação, determine uma solução ótima (ou quase 
ótima). Faça duas iterações completas explicando bem cada passo. A Metalúrgica Araucária S/A, 
dentro de 60 dias, deverá começar a funcionar em sua nova sede localizada na Cidade Industrial 
de Curitiba (CIC). O Presidente da Metalúrgica deseja que a distribuição das salas, dessa nova 
instalação, seja feita de modo a atender, na medida do possível, as preferências já manifestadas. 
Em uma pesquisa realizada, os Diretores manifestaram as suas preferências, sendo que 1 indica 
a sala de maior preferência e 6 indica a sala de menor preferência :
Sala
Diretor
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
Se você fosse convidado a 
opinar sobre a distribuição das 
salas qual seria a sua 
recomendação, de forma a 
satisfazer ao máximo as 
preferências dos diretores?
•Dados os parâmetros a serem adotados para resolução do problema:
•Nº máximo de iterações → M = 2
•Fator de redução de temperatura → α = 0,9
•Nº máximo de perturbações por iteração → P=4
•Limite de sucessos por iteração (perturbações aceitas a cada iteração) →L = 3
•Adote o número randômico rdn = 0,5 como limite para aceitação ou rejeição de uma 
solução quando esta causar um aumento de energia no processo. 
17
Sala
Diretor
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
Como o número deDiretores (5) é menor que o número de salas (6), toda solução 
implicará em uma sala vazia cuja designação será feita a um diretor inexistente 
(artificial), que representaremos por A.
Salas em ordem crescente : 1 2 3 4 5 6
Configuração do ex. de uma a solução tipo:→ Diretores designados (ex.) : (2 3 A 5 4 1)
Exemplo: Suponha que através de um processo aleatório obtivemos a seguinte amostra de 
cinco soluções viáveis:
Estimativa da temperatura inicial T0: 
1ª) (2,3,A,5,4,1)→ Energia = 1+3+0+6+6+6=22
2ª) (4,5,1,3,2,A)→ Energia = 1+2+3+2+3+0=11
3ª) (3,1,4,5,A,2)→ Energia = 5+4+2+6+0+2=19
4ª) (1,2,3,4,5,A)→ Energia = 2+5+4+4+1+0=16
5ª) (A,5,4,3,2,1)→ Energia = 0+2+2+2+3+6=15
 11 variação 
 8 variação 
 3 variação 
 1 variação 
   
14,26
22,0
75,5
8,0ln
75,5
ln
E
T
75,5
4
13811
E
:Logo
0
0 













S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
E
19
Início da 
1ª iteração:
Solução inicial (S0) (escolha aleatória de uma sol. qq.):
S0 = (4,5,1,3,2,A)→ E0 = 1+2+3+2+3+0=11
Solução (S1)= Uma perturbação sobre S0 = (4,5,1,3,2,A)→ E0 =11, é
um processo aleatório.
Por exemplo: Troca, entre si, as posições entre 4 e 3.
S1= (3,5,1,4,2,A)→ E1 =5+2+3+4+3+0=17
Variação de energia: ∆E= E1 – E0 =17-11=+6 → Aumentou a energia, então podemos
aceitar ou não a solução S1.
Nº de sucessos (nº de aceitações) , L= 1
Nº de perturbações executadas , P = 1
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
   
 problema. do início no arbitrado e enterandomicam gerado Número 0,5 rdn 2) 
iteração. primeira desta início do antes Estimada26,14TT 1) :Onde
0,5rdn0,79FB Como .79,072,272,2eFB
0i
23,0 26,14
6
 
T
E
 
i


 



.S solução a Aceitamos 1
Solução (S2)= Uma perturbação sobre S1 = (3,5,1,4,2,A) → E1 =17, é um processo aleatório.
Por exemplo: Troca, entre si, as posições entre 2 e 3.
S2= (2,5,1,4,3,A)→ E2 =1+2+3+4+1+0=11
Variação de energia: ∆E= E2 – E1 =11-17=-6 → Diminuiu a energia, então aceitamos a
solução S2.
Nº de sucessos (nº de aceitações) , L= 2
Nº de perturbações executadas , P = 2
Solução (S3)= Uma perturbação sobre S2 = (2,5,1,4,3,A)→ E2 =11, é
um processo aleatório.
Por exemplo: Troca, entre si, as posições entre 4 e 5.
S3= (2,4,1,5,3,A) → E3 =1+3+3+6+1+0=14
Variação de energia: ∆E= E3 – E2 =14-11=+3 → Aumentou a energia, então podemos
aceitar ou não a solução S3.
Nº de sucessos (nº de aceitações) , L= 3
Nº de perturbações executadas , P = 3
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
   
 problema. do início no arbitrado e enterandomicam gerado Número 0,5 rdn 2) 
iteração. primeira desta início do antes Estimada26,14TT 1) :Onde
0,5rdn0,89FB Como .89,072,272,2eFB
0i
11,0 26,14
3
 
T
E
 
i


 



.S solução a Aceitamos 3
Obs: A iteração finaliza quanto atingimos o valor de nº máx. perturbações/iteração → P=4 ou
o nº limite de sucessos/ iteração → L = 3, arbitrados no início do problema.
Fim da 1ª iteração, com a solução:
S3= (2,4,1,5,3,A) → E3 =14
21
Início da 2ª iteração:
Atualização da temperatura Ti :  = 0,9
53,2326,14 9,0TT αTT αT 2121-ii 
Solução inicial (S0)= Solução obtida no final da 1ª iteração, ou seja, “S3” = (2,4,1,5,3,A)
S0= (2,4,1,5,3,A) → E0 =14
Solução (S1)= Uma perturbação sobre S0 = (2,4,1,5,3,A) → E0 =14, é um processo aleatório.
Por exemplo: Troca, entre si, as posições entre A e 1.
S1 = (2,4,A,5,3,1) → E1 = 1+3+0+6+1+6=17
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
Variação de energia: ∆E= E1 – E0 =17-14=+3 → Aumentou a energia, então podemos
aceitar ou rejeitar a solução S1 de acordo com a seguinte probabilidade (Fator de
Boltzmann-FB) :
Nº de sucessos (nº de aceitações acumuladas) , L= 1
Nº de perturbações executadas (acumuladas) ,P=1
   
 problema. do início no arbitrado e enterandomicam gerado Número 0,5 rdn 2) 
iteração. segunda desta início do antes Estimada53,23TT 1) :Onde
0,5rdn0,88FB Como .88,072,272,2eFB
0i
13,0 23,53
3
 
T
E
 
i


 



.S solução a Aceitamos 1
22
Solução (S2)= Uma perturbação sobre S1 =(2,4,A,5,3,1) → E1 = 17,
é um processo aleatório.
Por exemplo: Troca, entre si, as posições entre 3 e 5.
S2 = (2,4,A,3,5,1) → E2 = 1+3+0+2+1+6=13
Variação de energia: ∆E= E2 – E1 =13-17=-4→ Diminuiu a energia,
então podemos aceitar a solução S2 :
Nº de sucessos (nº de aceitações acumuladas) , L= 2
Nº de perturbações executadas (acumuladas) ,P=2
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
Solução (S3)= Uma perturbação sobre S2 = (2,4,A,3,5,1) → E2 =13, é um processo aleatório.
Por exemplo: Troca, entre si, as posições entre 1 e 2.
S3 = (1,4,A,3,5,2) → E3 = 2+3+0+2+1+2=10
Variação de energia: ∆E= E3 – E2 =10-13=-3→ Diminuiu a energia, então podemos aceitar a
solução S3 :
Nº de sucessos (nº de aceitações acumuladas) , L= 3
Nº de perturbações executadas (acumuladas) ,P=3
Obs: A iteração finaliza quanto atingimos o valor de nº máx. perturbações/iteração → P=4 ou
o nº limite de sucessos/ iteração → L = 3, arbitrados no início do problema.
2) Como inicialmente a solução foi limitada em duas iterações (M=2) interrompemos aqui a
continuidade da solução.
Fim da 2ª iteração, com a solução:
S3 = (1,4,A,3,5,2) → E3=10
Fim
Atenção: Caso prosseguíssemos com as iterações a solução inicial S0 
para próxima iteração seria S0 =S3 = (1,4,A,3,5,2) → E3=10
23
Fim da 2ª iteração, com a solução:
S3 = (1,4,A,3,5,2) → E3=10
Interpretação desta solução:
Sala Diretor Preferência
1 1 2
2 4 3
3(vazia) A(inexistente) 0
4 3 2
5 5 1
6 2 2
- - Total:10
S
D
1 2 3 4 5 6
1 2 4 3 1 5 6
2 1 5 4 6 3 2
3 5 3 4 2 1 6
4 1 3 2 4 6 5
5 3 2 5 6 1 4
A 0 0 0 0 0 0
Lembrete: A melhor solução
tende a ser a última obtida
da última interação.
Suponha o Problema de Caixeiro Viajante (PCV) constituído de seis pontos, dada a matriz com
as distâncias inteiras mínimas aproximadas entre todos os pares de pontos. Determine uma
solução do PVC aplicando a meta-heurística Simulated Annealing.
1 2 3 4 5 6
1 0 2 2 4 4 4
2 2 0 1 2 3 2
3 2 1 0 2 2 3
4 4 2 2 0 3 3
5 4 3 2 3 0 5
6 4 2 3 3 5 0
Problema proposto:
•Dados os parâmetros a serem adotados para resolução do problema:
•Nº máximo de iterações → M = 2
•Fator de redução de temperatura → α = 0,9
•Nº máximo de perturbações por iteração → P=4
•Limite de sucessos por iteração (perturbações aceitas a cada iteração) →L = 3
•Adote o número randômico rdn = 0,5 como limite para aceitação ou rejeição 
de uma solução quando esta causar um aumento de energia no processo. 24
Alguns Exemplos Adicionais:
Legenda:
•n : nº de nós
•M: Nº máximo de iterações
•α: Fator de redução detemperatura
•P:Nº máximo de perturbações por iteração
•L:Limite de sucessos por iteração 
•S0: Solução inicial
•T0: Temperatura inicial
•S :Solução Final
Legenda:
•n : nº de nós
•M: Nº máximo de iterações
•α: Fator de redução de temperatura
•P:Nº máximo de perturbações por iteração
•L:Limite de sucessos por iteração 
•S0: Solução inicial
•T0: Temperatura inicial
•S :Solução Final
Simulated Annealing
1. Introdução
A origem da técnica de otimização conhecida por Simulated Annealing (têmpera 
simulada ou anelamento simulado) vem de 1953, quando foi usada para 
simular em um computador o processo de annealing de cristais. 
O annealing (anelamento ou têmpera) de certos materiais consiste em 
submetê-los inicialmente a altas temperaturas e reduzi-las gradualmente até 
atingirem, com aumentos e reduções do estado de energia, o equilíbrio térmico, 
tornando-os assim, consistentes e rígidos. 
A técnica matemática de Simulated Annealing faz uma simulação algorítmica do 
processo físico da têmpera de materiais. A idéia de aplicar este método para 
resolver problemas de otimização combinatória surgiu bem mais tarde com 
Kirkpatrick et al., 1983 e Aragon et al., 1984.
Tarefa: Leitura Integral do Material a Seguir.
Profa. Maria Teresinha Arns Steiner.
2. Fundamentação:
A fundamentação desta metaheurística baseia-se em simulações da evolução 
do equilíbrio térmico de materiais, proposto por Metrópolis et al., 1953, a qual 
utiliza o Método de Monte Carlo para gerar sequências de estados do material 
caracterizados pelas posições de suas partículas. 
Sob altas temperaturas as partículas estão totalmente “desorganizadas” 
correspondendo a uma configuração aleatória de um problema de otimização 
(em geral, distante da configuração ótima desejada). 
Uma pequena alteração (perturbação) nas posições de algumas destas 
partículas resulta numa variação de energia, que equivale a uma alteração no 
valor da função objetivo. 
Considerando dois estados sucessivos de energia Ei+1 e Ei, temos as 
seguintes situações:
Se E < 0: neste caso houve redução de energia; o novo estado é aceito e o 
processo continua;
Se E = 0: caso de estabilidade ou equilíbrio. Neste caso temos duas 
configurações vizinhas com o mesmo custo (coincidência pouco provável de 
acontecer na prática).
Se E > 0: neste caso houve aumento de energia que no processo físico é útil 
para permitir uma futura “acomodação” das partículas (evitando a convergência 
da função objetivo para mínimos locais indesejáveis). 
A probabilidade de aceitar uma mudança deste tipo (E > 0) é chamada de 
“critério de Metrópolis”, estabelecido a partir do fator de Boltzmann que é 
dado pela função exp (- E / T), onde T é a temperatura no momento em que 
ocorreu a mudança.
O Quadro 1 (Valdísio Viana, 1998) a seguir mostra o comportamento desta 
função para alguns valores de temperatura e variação de energia E > 0:
E
T 0.1 0.5 1 10
0.001 99% 99.8% 99.9% 99.99%
0.1 36.79% 81.87% 90.48% 99%
1 0% 13.53% 36.79% 90.48%
10 0% 0% 0% 36.79%
50 0% 0% 0% 0.67%
Quadro 1. Valores da função exp (-E / T)
iT
E
eFB



O método surgiu da seguinte observação da mecânica estatística: 
O resfriamento gradativo de um material a partir de uma alta temperatura inicial leva o 
material a estados mínimos de energia. 
Informalmente esses estados são caracterizados por uma perfeição estrutural do material 
congelado que não se obteria caso o resfriamento não tivesse sido gradativo. 
Sob outras condições menos cuidadosas de resfriamento, o material se cristalizaria com 
uma energia “localmente mínima”, apresentando imperfeições estruturais. A esse 
processo cuidadoso de resfriamento dá-se o nome de “annealing”.
A referida simulação a uma temperatura fixa T consiste em dar um pequeno deslocamento 
a um dos átomos, computando a variação E da energia do sistema. 
Se E  0, o deslocamento é incorporado ao estado do sistema, que é então utilizado no 
passo seguinte.
Caso contrário, isto é, se E > 0, a aceitação ou não do deslocamento passa a ser uma 
decisão probabilística, segundo a função de Boltzmann já definida anteriormente.
O procedimento da técnica Simulated Annealing compreende basicamente 
os seguintes 2 passos:
1) Identifica-se a função energia do sistema com a função objetivo que se quer 
otimizar, por exemplo minimizar, e os átomos do sistema são associados às 
variáveis do problema.
2) Para cada temperatura de uma seqüência de temperaturas decrescentes 
realiza-se a simulação descrita. No final do processo, espera-se que o sistema 
estacione em um estado de energia globalmente mínima, por analogia com a 
física do problema.
O fato do método Simulated Annealing permitir a aceitação de configurações 
intermediárias do problema em que cresce o valor da função objetivo que se 
deseja minimizar é crucial. 
Essa aceitação temporária de soluções “piores” significa que o método admite 
caminhar “morro acima”, na esperança de encontrar “vales” mais 
profundos.
Laarhoven e Aarts, 1987, que trazem um estudo detalhado da teoria e aplicações 
de Simulated Annealing, apresentam várias formas de se obter o fator de 
decréscimo da temperatura, dentre as quais se tem a seguinte:
Ti =  Ti-1
proposta por Romeo et al., 1985, onde  = 0,9, em geral.
Laarhoven e Aarts, 1987 indicam, também, várias formas de se obter a 
temperatura inicial, dentre as quais se tem a seguinte:
T0 = - E
+ / ln (0)
proposta por Johnson et al., 1987, onde E+ é a média aritmética, para um 
número randômico de perturbações, dos incrementos da função objetivo e 0 é 
um valor empírico, em torno de 0,8.
Pode-se estimar previamente o número de iterações m necessárias para 
variação da temperatura, pois em geral as fórmulas contêm implicitamente um 
fator  de seu decréscimo:
Se Ti =  Ti-1, então T1 =  T0; T2 =  T1 =  ( T0) = 
2 T0; ...; Tm = 
m T0; 
Assim: 
m = log  (Tm / T0).
Sugere-se os seguintes valores:  = 0,9 com um número aproximado de m = 100 
iterações e para T0 valores na faixa de 0,5 a 100.
3. Algoritmo Simulated Annealing:
Os passos do algoritmo contidos em Barbosa, 1989, são os seguintes:
Seja x0  D a solução inicial e T0 a temperatura inicial;
k = 0; xk = x0; Tk = T0
While Tk  Tmin do
begin
While ainda não em equilíbrio a temperatura Tk do
begin
selecione aleatoriamente um ponto x’ A(xk)  D
 = f (x’) - f (x) 
if   0 then
xk = x’
else
xk = x’ com probabilidade 
end
Tk+1= r(k); xk+1 = xk; k = k + 1
end
A solução é xk. 
Uma outra forma de apresentação do algoritmo Simulated Annealing
(Viana, 1998):
onde:
n = número de cidades;
M = número máximo de iterações;
P = número máximo de perturbações 
por iteração;
L = limite de sucessos por iteração 
(perturbações aceitas a cada 
iteração);
 = fator de redução de temperatura;
S0 = custo da configuração inicial;
S = melhor solução (configuração) 
obtida;
T0 = temperatura inicial.
4. Alguns Exemplos Adicionais:
Exemplo 1. PCV (Viana, 1998) 
 
Figura 1.1. Evolução do SA para o PCV (n = 44) 
(onde: n = 44; M = 100; P = 4400; L = 440;  = 0,90; S0 = 17,19; T0 = 2,5; S = 4,40). 
 
Figura 1.2. Configuração Inicial do PCV (f0 = 17,19). 
 
Figura 1.3. Configuração Final do PCV (fótimo = 4,40) 
 
Figura 2.2. Configurações Inicial e Final do PCV (S0 = 481,82; Sótimo = 100,00).