Simulated annealing

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde setembro de 2013).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

Arrefecimento simulado ou simulated annealing é uma metaheurística para otimização que consiste numa técnica de busca local probabilística, e se fundamenta numa analogia com a termodinâmica.

Esta metaheurística é uma metáfora de um processo térmico, dito annealing ou recozimento, utilizado em metalurgia para obtenção de estados de baixa energia num sólido. O processo consiste de duas etapas: na primeira a temperatura do sólido é aumentada para um valor próximo de 1100°C que é a temperatura de início de transformação da austenita em ferrita; na segunda o resfriamento deve ser realizado lentamente até que o material se solidifique, sendo acompanhado e controlado esse arrefecimento. Nesta segunda fase, executada lentamente, os átomos que compõem o material organizam-se numa estrutura uniforme com energia mínima. Isto provoca que os átomos desse material ganhem energia para se movimentarem livremente e, ao arrefecer de forma controlada, dar-lhes uma melhor hipótese de se organizarem numa configuração com menor energia interna, para ter, como resultado prático, uma redução dos defeitos do material.

De forma análoga, o algoritmo de arrefecimento simulado substitui a solução atual por uma solução próxima (i.e., na sua vizinhança no espaço de soluções), escolhida de acordo com uma função objetivo e com uma variável T (dita Temperatura, por analogia). Quanto maior for T, maior a componente aleatória que será incluída na próxima solução escolhida. À medida que o algoritmo progride, o valor de T é decrementado, começando o algoritmo a convergir para uma solução ótima, necessariamente local.

Uma das principais vantagens deste algoritmo é permitir testar soluções mais distantes da solução atual e dar mais independência do ponto inicial da pesquisa.

Descrição[editar | editar código-fonte]

Esta técnica começa sua busca a partir de uma solução inicial qualquer, o procedimento principal consiste em um loop ou laço que gera aleatoriamente, em cada iteração, um único vizinho s’ da solução corrente s. A cada geração de um novo vizinho s’ de s, é testada a variação ∆ do valor da função objetivo, isto é, ∆ = f (s’) – f (s), onde temos as seguintes situações:

  • ∆ < 0: Há uma redução de energia, a qual implica que a nova solução é melhor que a anterior. O método aceita a solução e s’ passa a ser a nova solução corrente.
  • ∆ = 0: Caso de estabilidade, não havendo redução de energia. Na verdade, situação pouco provável de acontecer na prática. A aceitação da solução é, portanto, indiferente.
  • ∆ ≥ 0: Houve um aumento do estado de energia. A aceitação desse tipo de solução é mais provável a altas temperaturas e bastante improvável a temperaturas reduzidas. Para reproduzir essas características, geralmente usa-se, para calcular a probabilidade de se aceitar a nova solução, uma função conhecida por fator de Boltzmann, que é dada por e^(-∆/T), onde T é um parâmetro do método, chamado de temperatura e que regula a probabilidade de soluções com pior custo. Por exemplo, esta poderá ser:
    • 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.

A temperatura T assume inicialmente um valor elevado, T0. Após um número fixo de iterações (o qual representa o número de iterações para o sistema atingir o equilíbrio térmico em uma dada temperatura), a temperatura é gradativamente diminuída por uma razão de resfriamento α, tal que Tn ← α * Tn -1, sendo 0 < α < 1. Como esse procedimento se dá no início, há uma chance maior de se escapar de mínimos locais e, à medida que T se aproxima de zero, o algoritmo se comporta como o método de descida, uma vez que diminui a probabilidade de se aceitar movimentos que possa piorar (T → 0 => e-∆/T → 0).

O procedimento é finalizado quando a temperatura chega a um valor próximo de zero e nenhuma solução que piore o valor da melhor solução seja mais aceita, ou seja, quando o sistema estiver estável. A solução obtida quando o sistema encontra-se nesta situação evidencia o encontro de um mínimo local.

Algoritmos baseados em Simulated Annealing geralmente incluem reaquecimento seguido de um novo processo de resfriamento, utilizado quando a quantidade de movimentos consecutivamente rejeitados é alta. É também comum trabalhar nas temperaturas mais altas com taxa de resfriamento menor e aumentá-la quando a temperatura reduzir.

Pseudo-código[editar | editar código-fonte]

Antes de apresentar o algoritmo, vejam-se os identificadores neles utilizados:

  • S0 → Configuração Inicial (Entrada);
  • Si → Configuração da Iteração i;
  • S → Configuração Final;
  • T0 → Temperatura Inicial;
  • Ti → Temperatura na Iteração i;
  • M → Número máximo de iterações (Entrada);
  • P → Número máximo de Perturbações por iteração (Entrada);
  • L → Número máximo de sucessos por iteração (Entrada);
  • α → Factor de redução da temperatura (Entrada);
  • f(Si) → Valor da função objetivo correspondente á configuração Si;
  • nSucesso → Contador de sucesso em uma iteração;
  • i e j → Variáveis de controle de Loops.

Além dos indicadores acima, consideremos as seguintes funções:

  • Perturba(S) → Função que realiza uma perturbação na Solução S;
  • Randomiza() → Função que gera um número aleatório no intervalo [0,1];
  • TempInicial() → Função que calcula a temperatura inicial;

Pseudo-Código Simulated Annealing
Inicio
/* Entradas do Algoritmo */
Ler (S0, M, P, L, α)
/* Inicialização das variáveis */
S = S0
T0 = TempInicial()
T = T0
j = 1
/*Loop principal – Verifica se foram atendidas as condições de termino do algoritmo*/
Repita

i = 1
nSucesso = 0
/*Loop Interno – Realização de perturbação em uma iteração*/
Repita
Si = Perturba(S)
∆Fi = f(Si) – f(S)
/*Teste de aceitação de uma nova solução*/
Se (∆fi ≤ 0) ou (exp(-∆fi/T) > Randomiza()) então
S= Si
nSucesso = nSucesso + 1
Fim-se
i = i + 1
Até (nSucesso ≥ L) ou (i > P)
/*Actualização da Temperatura*/
T = α.T
/*Actualização do Contador de iterações*/
j = j + 1

Até (nSucesso = 0) ou (j > M)
/*Saída do Algoritmo*/
Imprima(S)

Veja também[editar | editar código-fonte]

Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.