SIMULATED ANNEALING ALGORITHM
Disciplina: OTIMIZAÇÃO MULTIOBJETIVO
Prof. João Antônio de Vasconcelos
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
ALGORITMO SIMULATED ANNEALING
Termodinâmica: É possível
simular o processo de
Recozimento de um Sólido?
T0
T
Sólido
Fusão
T
Fusão
Cristal
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Algoritmo de Metropolis
Em física de matéria condensada, recozimento (annealing) é
conhecido como um processo térmico para obter estados de
b i energia
baixa
i de
d um sólido
ólid em uma caldeira.
ld i
Este pprocesso baseia-se nos dois ppassos seguintes:
g
• No aumento da temperatura da caldeira até um valor
máximo
á i
para a quall o sólido
ólid se derrete;
d
• Na diminuição cuidadosa da temperatura da caldeira
até que as partículas se arranjem no estado de
mínima energia
g do sólido.
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Na fase líquida, todas as partículas do sólido se arranjam
aleatoriamente. No estado de mínima energia as partículas
se arranjam em uma rede altamente estruturada e a energia
do sistema é mínima (estrutura cristalina).
A existência da estrutura cristalina resulta dos sólidos
cristalinos serem formados a partir da repetição no espaço de
uma estrutura elementar paralelepídica denominada célula
unitária (ver figura).
Célula unitária de um cristal de sal (NaCl).
(NaCl)
Note-se a ordenação dos átomos.
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
O estado de mínima energia é obtido somente se a
temperatura máxima é suficientemente elevada e se o
processo de resfriamento é feito suficientemente
s ficientemente
devagar. Senão o sólido após resfriado estará em um
estado denominado meta
meta-estável,
estável, ao invés de um estado de
mínima energia.
O processo físico de recozimento pode ser modelado com
sucesso usando métodos computacionais oriundos da física
de matéria condensada.
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Algoritmo de Metropolis
(Metropolis, Rosenbluth, Rosenbluth, Teller & Teller [1953])
É um algoritmo simples para simular a evolução de um sólido em uma
caldeira na direção do equilíbrio térmico.
Este algoritmo é baseado na técnica de Monte Carlo,
Carlo o qual gera uma
seqüência de estados de energia do sólido da seguinte maneira:
• Dado um estado atual i do sólido,, com energia
g Ei,, um estado subsequente
q
j
é gerado ao se aplicar um mecanismo de perturbação que transforma o
estado atual em um próximo estado, através de uma pequena alteração, por
exemplo pelo deslocamento de uma partícula.
exemplo,
partícula
• A energia do próximo estado é Ej.
• Se a diferença de energia, Ej - Ei, é menor que ou igual a 0 (zero), o estado
j é aceito como o estado atual.
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
• Se a diferença de energia é maior que 0 (zero),
(zero) o estado j é aceito com uma
certa probabilidade que é dada por:
⎛ Ei − E j
p = exp⎜⎜
⎝ k BT
⎞
⎟
⎟
⎠
onde T é a temperatura da caldeira e kB é uma constante física conhecida
como constante de Boltzmann. O critério de aceite descrito acima é
conhecido como critério de Metropolis e o algoritmo de Algoritmo de
Metropolis.
Se a temperatura é diminuída suficientemente devagar, o sólido, no processo
físico, pode atingir equilíbrio térmico em cada temperatura. No algoritmo de
Metropolis
p
isto é conseguido
g
gerando um g
g
grande número de transições em
um dado valor de temperatura. Equilíbrio térmico é caracterizado por uma
distribuição de Boltzmann. Esta distribuição dá a probabilidade do sólido
estar em um estado i com energia Ei, na temperatura T, e é dada por:
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
⎛ − Ei ⎞
1
⎟⎟
PT {x = i} =
exp⎜⎜
Z(T )
⎝ k BT ⎠
onde X é uma variável estocástica designando o estado atual do sólido. Z(T)
é uma função de partição definida como:
⎛ − Ej ⎞
⎟⎟
Z(T) = ∑ exp⎜⎜
j
⎝ k BT ⎠
onde a soma se estende a todos os estados possíveis.
p
A distribuição de Boltzmann desempenha um papel importante no algoritmo
“Simulated Annealing”.
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
ALGORITMO SIMULATED ANNEALING
(Kirkpatrick et al)
Simulação do Equilíbrio
Térmico
((Metropolis)
p )
Iteração k+1
Calcular variação
Energética : ΔE = Ef - Ei
ΔE < 0
Se: ΔE > 0
Iteração k+1
Perturbação
Perturbação
Se:
otimização
aceitar
aceictar se:
Calcular variação
da função objetivo :
Se: ΔE < 0
Se: ΔE > 0
aceitar
aceictar se:
P(E) > δ
P(E) > δ
Onde: P(E) = exp(- ΔE /kbT)
[0,1)
δ
ΔE =ff - fi
Onde: P(E) = exp(- ΔE /kcT0)
[0,1)
δ
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Simulated Annealing Algoritm - SAA
No SAA o algoritmo de Metropolis é aplicado para gerar uma sequência de
soluções de um dado problema. Assumimos para isto uma analogia entre um
sistema com muitas partículas físicas e um problema de otimização baseado
nas seguintes equivalências:
• Soluções em um problema de otimização são equivalentes a estados de um
sistema
it
fí i
físico.
• O custo de uma solução (valor da função objetivo) é equivalente à energia
de um estado.
A temperatura no processo físico é substituída no SAA por um parâmetro de
controle. Assim, o SAA p
pode agora
g
ser visto como um p
processo iterativo do
algoritmo de Metropolis, avaliado em valores decrescentes do parâmetro de
controle.
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Definição 1.
1 Deixe (S,f)
(S f) designar uma amostra de um problema de
otimização e i e j duas soluções com custo f(i) e f(j), respectivamente. Então
o critério de aceite determina quando j é aceito em substituição a i pela
aplicação da seguinte probabilidade de aceite:
⎧1
⎪
Pc ( aceitar j ) = ⎨ ⎛ − ( f ( j ) − f ( i )) ⎞
⎟
⎪exp⎜
c
⎠
⎩ ⎝
se f ( j ) ≤ f ( i )
se f ( j ) > f ( i )
onde c ∈ R designa o parâmetro de controle. É claro que o mecanismo de
geração
g
ç e o critério de aceite correspondem
p
respectivamente
p
ao mecanismo
de perturbação e ao critério de aceite do algoritmo de Metropolis .
Definição 2.
2 Uma transição é uma ação combinada que resulta na
transformação de uma solução atual em uma subsequente. A ação consiste
nos dois passos seguintes: (i) aplicação do mecanismo de geração, (ii)
aplicação
li ã do
d critério
i é i de
d aceite.
i
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Simulated Annealing Algoritm - SAA: Deixe ck designar o valor do parâmetro
de controle e Lk o número de transições geradas na k-ésima iteração do Algoritmo
de Metropolis. Então, o SAA pode ser descrito em pseudo PASCAL como:
procedure Simulated_Annealing;
begin
INITIALIZE(istart, c0, L0);
)
k := 0;
i := istart;
repeat
for l:=1 to Lk do
begin
GENERATE(j from Si);
if ( f(j) ≤ f(i) ) then i := j
else
⎛ − ( f ( j ) − f ( i )) ⎞
⎟
if ( exp⎜⎜
⎟
c
k
⎝
⎠
end;
> random [0, 1) ) then i :=j
k := k+1;
CALCULATE_LENGTH (Lk);
CALCULATE_CONTROL(ck);
until stopcriterion
p
end;
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Características do SAA
O SAA além de aceitar os ganhos na função custo, ele também aceita dentro de
certos limites
li i
d i
deteriorações
õ no custo. Inicialmente,
I i i l
para grandes
d valores
l
d c,
de
grandes deteriorações no valor da função custo serão aceitos; na medida em que c
diminui, somente menores deteriorações serão aceitas e finalmente, na medida em
que c aproxima-se de 0 (zero), nenhuma deterioração será aceita.
Em contraste com outros algoritmos
g
de busca local,, o SAA pode
p
escapar
p de
mínimos locais enquanto ainda exibe características favoráveis de algoritmos de
busca local, que são simplicidade e aplicabilidade geral.
Dificuldades:
Determinação
D
t
i ã d
do
esquema de
resfriamento
- Valor inicial da temperatura
p
TEMP0
- Fator de redução da temperatura (0.8 - 0.99)
- Número de iterações sobre cada valor de temperatura
(no equilíbrio Na/Nr ~ 1)
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Simulated Annealing Algoritm - SAA
Met-alg: Algoritmo de Metropolis
NUCICL: Número de ciclos auxiliares
LIM: Limite de movimentos com sucesso
j: j-ésimo ciclo auxiliar
i: i-ésima variável contínua
ui: uu-ésimo
ésimo sucesso da ii-ésima
ésima variável
TEMP: Temperatura
p0: Melhor solução
Aj t d
Ajuste
de TEMP
TEMP:
∑u
Se NT
∑
< 0,3
aumentar TEMP
∑u
Se
∑ NT
> 0,7
reduzir TEMP
i
i
i
i
i
i
i
i
Ajuste de H:
hi = hi[1+Ci(Pi-0,6)/0,4] se Pi > 0,6
hi = hi[1+Ci(0,4 - Pi)/0,4]-1 se Pi < 0,4
S íd d
Saída
do Ci
Ciclo
l d
de T
Temperatura:
t
i
Seja
Onde,
Pi = ui/Nti
Normalmente Ci ≈ 0,2
∑u
u=
∑ NT
i
i
i
Se
u ∈ [0.4;0.6]
e j > 2.nd
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Inicialização
H = {h1, h2, ..., hnd}
Ind = 0
Ajustar H
Reduzir TEMP
Ind = Ind + 1
pp’i = pi + rhi
f’ = f(p’)
NTi = NTi + 1
Parar
Não
Não
Met-alg
f’ ≤ f
Não
Sim
Sim
Sim
p = p’
f = f’
ui = ui + 1
i=i+1
S i > nd,
Se
d i=1
p = p0
f = f0
Sim
f’ < f0
Não
p0 = p’
f0 = f’
Não
Sim
j < 10.nd
Não
j > 2.nd e
u ∈ [0.4;0.6]
Nao
j=j+1
Ind = 0 e
j ∈[k, 2k, 3k]
Sim
Sim
Otimização Multiobjetivo - Prof. João Antônio de Vasconcelos – Depto. Eng. Elétrica - UFMG
Ajustar
TEMP
FIM