Simulated Annealing

Algoritmos e Programação de Computadores II

Prof. MSc. Leanderson André

leandersonandre@univille.br

Universidade da Região de Joinville

Simulated Annealing

Definição

Recozimento Simulado (Simulated Annealing): metaheurística de otimização inspirada no processo de aquecimento e resfriamento controlado de materiais, utilizado na metalurgia.

Proposto por Kirkpatrick, Gelatt e Vecchi (1983).

Simulated Annealing

Processo de recozimento de materiais metálicos.

Simulated Annealing

Aplicações

Engenharia: otimização de circuitos, projetos e estruturas.
Medicina: planejamento de radioterapia e processamento de imagens médicas.
Pesquisa operacional: problemas de roteamento, escalonamento e alocação de recursos.

Analogia com o recozimento

Processo físico	Algoritmo
Temperatura	Temperatura de controle
Estado do material	Solução candidata
Energia do material	Função de custo
Resfriamento gradual	Redução da temperatura
Equilíbrio térmico	Estabilização da busca

Analogia com o recozimento

Temperaturas elevadas: permitem maior mobilidade dos átomos, favorecendo a exploração de diferentes regiões do espaço de busca (diversificação).
Temperaturas baixas: reduzem a mobilidade dos átomos, favorecendo a estabilização em regiões promissoras (intensificação).

Simulated Annealing

Características

Solução única: trabalha com uma solução candidata por vez.
Iterativo: gera soluções vizinhas e atualiza a solução atual ao longo das iterações.
Espaço de busca: pode ser aplicado a problemas de otimização contínua e discreta.

Pseudocódigo

x ← solução inicial
E ← custo(x)
T ← temperatura inicial

enquanto critério de parada não for atingido faça
    T ← atualizar temperatura(T)

    x' ← gerar vizinho(x)
    E' ← custo(x')

    ΔE ← E' - E

    se ΔE < 0 ou aleatório(0,1) < exp(-ΔE/T) então
        x ← x'
        E ← E'
    fim se
fim enquanto

retornar x

Geração da solução inicial

Solução inicial: pode ser gerada aleatoriamente ou construída por meio de uma heurística.
Avaliação: calcula-se o custo da solução inicial.
Inicialização: a solução gerada passa a ser a solução atual e a melhor solução encontrada.

Critério de parada

O algoritmo pode encerrar sua execução quando uma das seguintes condições for atingida:

Temperatura mínima: a temperatura atinge um valor limite predefinido.
Número máximo de iterações: atinge-se o limite de iterações estabelecido.
Número de iterações sem melhoria: não ocorre melhoria na melhor solução encontrada após determinado número de iterações.
Tempo máximo: o tempo de execução atinge o limite estabelecido.

Atualização da temperatura

A temperatura é reduzida gradualmente durante a execução do algoritmo, controlando a probabilidade de aceitação de soluções piores.

Resfriamento geométrico:

$$T_{k+1} = \alpha \cdot T_k$$

Simulated Annealing

Onde:

$T_k$: temperatura atual.
$T_{k+1}$: nova temperatura.
$\alpha$: taxa de resfriamento, com $0 < \alpha < 1$.
$\alpha$ próximo de 1: resfriamento mais lento.
$\alpha$ menor: resfriamento mais rápido.

Geração do vizinho (perturbação)

Consiste em modificar a solução atual para gerar uma nova solução candidata.

Problemas discretos: troca, inserção, remoção ou inversão de elementos.
Problemas contínuos: alteração dos valores das variáveis por meio de pequenas perturbações.
Vizinhança: conjunto de soluções que podem ser obtidas a partir da solução atual.

Perturbação em domínio contínuo

A nova solução é gerada adicionando um ruído aleatório com distribuição normal à solução atual:

$$x' = x + \epsilon$$

$$\epsilon \sim \mathcal{N}(0,\sigma^2)$$

Onde:

$\epsilon$: perturbação aleatória.
$\sigma$: desvio padrão, que controla a magnitude da perturbação.

Aceitação de soluções

Diferentemente de uma busca local tradicional, o Simulated Annealing pode aceitar soluções que apresentam um custo maior.

Melhores soluções: sempre são aceitas.
Piores soluções: podem ser aceitas com determinada probabilidade.
Temperatura elevada: maior probabilidade de aceitar soluções piores.
Temperatura baixa: menor probabilidade de aceitar soluções piores.

Probabilidade de aceitação

A probabilidade de aceitar uma solução pior é calculada por:

$$P(\text{aceitar}) = e^{-\frac{\Delta E}{T}}$$

Probabilidade de aceitação

Onde:

$\Delta E$: aumento do custo da solução ($\Delta E > 0$).
$T$: temperatura atual.
$e$: constante de Euler.
Quanto maior a temperatura, maior a probabilidade de aceitar soluções piores.
Quanto maior o aumento do custo, menor a probabilidade de aceitação.

Parâmetros

Parâmetro	Descrição
`T₀`	Temperatura inicial do algoritmo.
`Tmin`	Temperatura mínima utilizada como critério de parada.
`α`	Taxa de resfriamento, utilizada para reduzir a temperatura.
`k`	Iteração atual do algoritmo.
`x₀`	Solução inicial do algoritmo.
`E(x)`	Função objetivo que avalia o custo de uma solução.
`ΔE`	Variação do custo entre a solução candidata e a solução atual.
`ε`	Perturbação aleatória utilizada para gerar vizinhos em problemas contínuos.
`σ`	Desvio padrão da distribuição normal, controla a intensidade da perturbação.
`iterMax`	Número máximo de iterações.
`iterSemMelhoria`	Limite de iterações consecutivas sem melhoria na melhor solução.
`tempoMax`	Tempo máximo de execução do algoritmo.

Pseudocódigo

x ← solução inicial
E ← custo(x)
T ← temperatura inicial

enquanto critério de parada não for atingido faça
    T ← atualizar temperatura(T)

    x' ← gerar vizinho(x)
    E' ← custo(x')

    ΔE ← E' - E

    se ΔE < 0 ou aleatório(0,1) < exp(-ΔE/T) então
        x ← x'
        E ← E'
    fim se
fim enquanto

retornar x

Prof. MSc. Leanderson André

leandersonandre@univille.br

Universidade da Região de Joinville