Simulated Annealing

INTRODUÇÃO

Otimizar significa partir de uma configuração inicial e caminhar no sentido de melhorar um dado critério de desempenho, através da modificação de parâmetros que o caracterizam. Para um problema de otimização pode-se ter várias soluções diferentes. O conceito de “melhor” projeto depende do problema, do método de solução e da tolerância adotada (BORGES, 2003).

Os métodos de otimização tradicional quase sempre são baseados em técnicas do cálculo diferencial com alta dependência do gradiente. Já os métodos randômicos adotam critérios “inteligentes” para sua implementação, como os métodos que são inspirados na natureza. Esses métodos trabalham com probabilidades para selecionar um conjunto de parâmetros que delimita uma dada função objetivo em um espaço de busca.

O algoritmo conhecido como Recozimento Simulado (Simulated Annealing), assim como os Algoritmos Genéticos são métodos de otimização baseados em processos naturais. A ideia principal é reproduzir o comportamento de metais submetidos um tratamento térmico conhecido como recozimento.

Os tratamentos térmicos empregados em metais ou ligas metálicas, são definidos como qualquer conjunto de operações de aquecimento e resfriamento, sob condições controladas de temperatura, tempo, atmosfera e velocidade de resfriamento, com o objetivo de alterar suas propriedades ou conferir-lhes características pré-determinadas.

Quando um material é submetido a um aquecimento, sua estrutura cristalina é deformada e surgem vários pontos de tensão. Os cristais deformados têm mais energia que os não deformados, por causa da desorganização da estrutura cristalina nas interfaces entre os grãos. Estas estruturas são estáveis nesta temperatura, já que os átomos não têm mobilidade suficiente para alterar a sua organização cristalina. Havendo oportunidade, os átomos irão se deslocar visando um arranjo mais perfeito e regular, de menor energia.

RECOZIMENTO SIMULADO

Experimentos que levam a baixos níveis de energia interna do material são baseados em um recozimento cuidadoso, ou seja, numa redução bem lenta da temperatura desde o estado de fusão do material, que vai resultar numa estrutura cristalina pura. Se não for feito assim os cristais resultantes terão muitos defeitos ou a substância pode se transformar em um vidro, que é uma estrutura apenas ótima localmente. Este processo de se achar um estado de baixa energia e esses pontos onde ocorrem defeitos e intrusões no material podem ser comparados em otimização como quando se encontra mínimos locais.

Os parâmetros principais da programação do Recozimento Simulado (RS) são os seguintes fatores:

A temperatura inicial

O número de iterações do algoritmo com a mesma temperatura

A estratégia de redução de temperatura ao longo da execução do algoritmo

Método de resolução

A partir de um ponto no espaço de soluções X calcula-se um novo ponto vizinho X' do atual. Se a energia (o valor da função objetivo) é menor neste novo ponto, este passa a ser o ponto atual, então um ponto seu vizinho é calculado e o algoritmo continua. Se a energia é maior neste novo ponto, ele não é automaticamente descartado. Há certa probabilidade de ele ser aceito como o novo ponto atual, e esta probabilidade é tão maior quanto maior for o parâmetro temperatura ou quanto menor for a diferença de energia entre os dois pontos.

Essa ideia é baseada no critério de Metrópolis (METRÓPOLIS et al., 1953), que consiste em avaliar a diferença de energia entre a solução atual e a nova solução, ou seja

∆E=E_(k+1)-E_k (2.1)

E_k – é o valor da função objetivo encontrada na última iteração (f(X));

E_(k+1) – é o novo valor da função objetivo encontrado (f(X')).

Se ∆E é negativo, isto significa que a nova solução é melhor que a anterior, e esta última é substituída. Entretanto, se é positivo, a probabilidade de esta solução de maior energia substituir a anterior é dada por:

P(∆E)=exp⁡((-∆E)/kT) (2.2)

P(∆E) – probabilidade de uma solução inferior ser aceita;

T – parâmetro de controle;

k – constante de Boltzma;

O Recozimento Simulado executa uma perturbação randômica que modifica as variáveis independentes, mantendo o melhor valor da função custo para cada iteração. Depois de muitas iterações, o conjunto que produziu o melhor valor da função é designado para ser o centro sobre o qual a perturbação acontecerá para a próxima temperatura. Para escapar do “ótimo local”, o algoritmo reinicia a busca partindo de várias soluções iniciais diferentes e utiliza a melhor solução encontrada como solução do algoritmo. Esta estratégia reduz a dependência da solução inicial,