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
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
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.
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.
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.
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.
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
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
Abrir referência DOICopiado.van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
ISBN: 9789027725431Copiado.