Skip to content
Voltar aos resultados

Annealing Simulado — Otimização Probabilística

Ano
1983
Tipo
Probabilistic metaheuristic / local search

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Annealing simulado é uma meta-heurística probabilística de busca local introduzida por Kirkpatrick, Gelatt e Vecchi em 1983.

Ela modela o processo físico de recozimento na metalurgia — onde um material é aquecido e depois lentamente resfriado para atingir um estado cristalino de baixa energia — e usa essa analogia para escapar de ótimos locais em problemas de otimização combinatória e contínua.

A intuição por trás do método

Imagine tentar encontrar o ponto mais baixo em uma paisagem montanhosa com os olhos vendados. Uma busca puramente gulosa sempre desce e fica presa no primeiro vale que encontra — que pode não ser o mais profundo. O annealing simulado introduz uma aleatoriedade controlada: no início, quando a 'temperatura' está alta, o algoritmo está disposto a subir ocasionalmente, aceitando uma solução pior por acaso. À medida que a temperatura diminui de acordo com um cronograma de resfriamento, o algoritmo se torna cada vez mais seletivo, convergindo para uma solução. Essa disposição para aceitar movimentos piores em alta temperatura é o que permite que o método escape de ótimos locais rasos e explore a paisagem de forma mais completa.

História

O annealing simulado foi introduzido por Kirkpatrick, Gelatt e Vecchi em seu artigo marco de 1983 na Science, que traçou uma analogia explícita entre o recozimento termodinâmico de sólidos e a otimização combinatória. A mesma ideia foi proposta independentemente por Cerny (1985) no contexto do problema do caixeiro viajante. van Laarhoven e Aarts (1987) forneceram o primeiro tratamento teórico rigoroso, provando propriedades de convergência sob vários cronogramas de resfriamento. Desde então, o método se tornou uma das meta-heurísticas mais estudadas e aplicadas, utilizada em projeto de engenharia, pesquisa operacional, layout VLSI e ajuste de hiperparâmetros de aprendizado de máquina.

Quando usar

O annealing simulado é aplicável a qualquer problema onde uma estrutura de vizinhança possa ser definida sobre o espaço de soluções, independentemente de a função objetivo ser diferenciável, convexa ou mesmo analiticamente expressável. É particularmente adequado para problemas combinatórios (agendamento, roteamento, problemas de grafos) e otimização contínua de caixa preta. Nenhum dado de treinamento ou suposição de normalidade é necessário. O cronograma de resfriamento e a estrutura de vizinhança devem ser ajustados ao problema; executar menos de aproximadamente 1.000 iterações arrisca a convergência prematura para um ótimo local, caso em que uma busca local determinística mais simples deve ser preferida.

Limitações e considerações

  • A qualidade da solução é sensível ao cronograma de resfriamento; um cronograma ruim pode gerar resultados não melhores que a busca aleatória.
  • A estrutura de vizinhança deve ser projetada para cada classe de problema, o que requer conhecimento de domínio.
  • A convergência para o ótimo global requer resfriamento extremamente lento na prática, tornando o tempo de execução longo para garantias de alta qualidade.
  • Não utiliza informação de gradiente ou estrutural, portanto, métodos baseados em gradiente o superam em problemas suaves e diferenciáveis.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Pode escapar de ótimos locais através da aceitação probabilística de soluções piores, ao contrário do hill-climbing puro.
  • Aplica-se a praticamente qualquer tipo de problema — combinatório, contínuo, misto — desde que uma estrutura de vizinhança seja definida.
  • Não requer informação de gradiente e é indiferente à estrutura matemática da função objetivo.
  • Possui uma garantia teórica de convergência para o ótimo global sob resfriamento suficientemente lento (Hajek 1988).
  • Poucos hiperparâmetros: temperatura inicial, taxa de resfriamento e estrutura de vizinhança.

Aplicações

  • Problemas combinatórios de agendamento e elaboração de horários onde o espaço de soluções é muito grande para busca exaustiva.
  • Problemas do caixeiro viajante e de roteamento de veículos em logística e pesquisa operacional.
  • Layout de circuitos VLSI e planejamento de chips em engenharia elétrica.
  • Problemas de dobramento de proteínas e conformação molecular em biologia computacional.
  • Otimização de hiperparâmetros para modelos de aprendizado de máquina quando a informação de gradiente está indisponível.
  • Problemas de alocação e atribuição de recursos em engenharia e ciência da gestão.

Como funciona

Como funciona

1

O algoritmo começa com uma solução inicial — qualquer ponto factível no espaço de busca — e uma temperatura inicial alta. A solução inicial pode ser aleatória ou específica do problema; a temperatura inicial é tipicamente definida alta o suficiente para que quase qualquer solução vizinha seja aceita no início.

2

Uma solução vizinha é gerada aplicando uma pequena mudança aleatória (um 'movimento') à solução atual. A estrutura de vizinhança deve ser adaptada ao problema: para um problema de agendamento, um movimento pode trocar duas tarefas; para uma função contínua, pode adicionar uma pequena perturbação aleatória ao vetor de parâmetros atual.

3

A diferença no valor objetivo entre a nova solução e a atual é calculada. Se a nova solução for melhor, ela é sempre aceita. Se for pior, ela é aceita com uma probabilidade que decai com o tamanho da deterioração e a temperatura atual — tipicamente exp(−ΔE / T). Essa aceitação probabilística é o mecanismo central que impede a convergência prematura.

4

Após cada iteração (ou após um número fixo de movimentos na mesma temperatura), a temperatura é reduzida de acordo com um cronograma de resfriamento — comumente um cronograma geométrico T ← α·T onde α é ligeiramente abaixo de 1. A escolha do cronograma de resfriamento afeta fortemente a qualidade da solução: resfriar muito rápido prende a busca em um ótimo local; resfriar muito lentamente desperdiça tempo computacional.

5

O algoritmo para quando a temperatura cai abaixo de um limite mínimo, um número máximo de iterações é atingido, ou a solução não melhorou por um número especificado de passos. A melhor solução encontrada durante toda a execução — não apenas o estado final — é retornada como resultado.

Erros comuns

  • Executar poucas iterações (aproximadamente menos de 1.000) impede que o cronograma de resfriamento funcione corretamente e deixa a busca presa em um ótimo local — prefira busca tabu ou uma busca local determinística se o tempo de execução for severamente limitado.
  • Definir a temperatura inicial muito baixa significa que o algoritmo se comporta imediatamente como um hill-climbing guloso e perde sua capacidade de escapar de ótimos locais.
  • Definir a taxa de resfriamento de forma muito agressiva (por exemplo, α abaixo de 0,9) causa convergência prematura; verifique a qualidade da solução final reiniciando de múltiplas soluções iniciais.
  • Aplicar um movimento de vizinhança projetado para um tipo de problema a um problema diferente pode tornar os movimentos inviáveis ou sem sentido — sempre verifique se cada vizinho gerado é uma solução válida.
  • Relatar apenas o estado final em vez da melhor solução já vista durante a execução pode perder o verdadeiro ótimo encontrado em um passo intermediário.

Perguntas frequentes

Como escolho o cronograma de resfriamento?

O cronograma geométrico T ← α·T com α entre 0,90 e 0,99 é o ponto de partida mais comum. Uma abordagem prática é definir a temperatura inicial alta o suficiente para que aproximadamente 80% dos movimentos sejam aceitos no início, depois reduzi-la até que menos de 1% dos movimentos ascendentes sejam aceitos. Se a qualidade da solução final for ruim, diminua a taxa de resfriamento (aumente α); se o tempo de execução for muito longo, acelere-o. Sempre execute o algoritmo várias vezes a partir de diferentes soluções iniciais para avaliar a robustez.

Como o annealing simulado difere de algoritmos genéticos ou otimização por enxame de partículas?

O annealing simulado mantém uma única solução e explora a vizinhança através de perturbações aleatórias, aceitando probabilisticamente soluções piores. Algoritmos genéticos e otimização por enxame de partículas mantêm uma população de soluções e usam cruzamento, mutação ou movimento de enxame para evoluir a população. O annealing simulado é geralmente mais simples de implementar para problemas com uma estrutura de vizinhança natural, enquanto métodos baseados em população podem ser mais eficazes para problemas contínuos de alta dimensão.

O ótimo global é garantido?

Teoricamente sim, sob a condição de que a temperatura diminua suficientemente devagar (resfriamento logarítmico). Na prática, tal resfriamento é computacionalmente inviável, então o algoritmo encontra uma solução quase ótima. A qualidade do resultado melhora com resfriamento mais lento e mais iterações, mas não há garantia em tempo finito. Executar múltiplos reinícios e manter a melhor solução encontrada é uma maneira prática de aumentar a confiança.

Quando devo preferir busca tabu ou um algoritmo genético em vez disso?

Escolha a busca tabu quando precisar de uma busca determinística guiada por memória que evite revisitar soluções recentes e possa explorar a estrutura do problema de forma eficiente em uma execução mais curta. Escolha um algoritmo genético ou otimização por enxame de partículas quando o problema for de alta dimensão e contínuo, ou quando uma população de soluções diversas for necessária para mapear a paisagem ótima. O annealing simulado é uma forte opção padrão para problemas combinatórios com uma estrutura de vizinhança clara e quando a simplicidade de implementação é importante.

Métodos relacionados

Fontes

  1. Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.

    Abrir referência DOI
    Copiado.
  2. van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.

    ISBN: 9789027725431
    Copiado.