Simulated Annealing
O Simulated Annealing é uma meta-heurística probabilística inspirada no processo de recozimento na metalurgia. Começa com uma solução inicial e explora iterativamente soluções vizinhas. Aceita soluções melhores e também aceita soluções piores com uma probabilidade que diminui ao longo do tempo (agenda de arrefecimento da temperatura), permitindo-lhe escapar de ótimos locais.
Como Funciona
O algoritmo inicia com uma "temperatura" alta, permitindo movimentos amplos pelo espaço de busca, inclusive aceitando soluções piores com alta probabilidade. À medida que a temperatura diminui gradualmente, o algoritmo torna-se mais seletivo, eventualmente convergindo para um comportamento semelhante ao Hill Climbing.
Pontos Fortes e Fracos
Pontos Fortes
- ✅ Melhor capacidade de escapar de ótimos locais em comparação com o Hill Climbing
- ✅ Pode ser aplicado a problemas de otimização combinatória e contínua
- ✅ Balanço entre exploração global e refinamento local
Pontos Fracos
- ❌ Pode ser computacionalmente dispendioso, frequentemente requerendo um grande número de iterações
- ❌ O desempenho é sensível à escolha da temperatura inicial e da agenda de arrefecimento
- ❌ Não há garantia de encontrar o ótimo global dentro de um número finito de iterações
Aplicabilidade à Otimização Semafórica
O Simulated Annealing poderá ser uma melhor alternativa ao Hill Climbing para a otimização semafórica devido à sua capacidade de explorar mais amplamente e potencialmente encontrar melhores soluções em paisagens complexas e multimodais.
No entanto, a necessidade de um ajuste cuidadoso dos parâmetros (agenda de arrefecimento) e o número potencialmente grande de avaliações necessárias ainda precisam ser considerados dado o custo das simulações.
Importância da Agenda de Arrefecimento
A aceitação probabilística de soluções piores no Simulated Annealing permite-lhe "saltar" para fora de ótimos locais e explorar outras regiões do espaço de busca que poderão conter melhores soluções. Isto torna-o mais robusto do que o Hill Climbing. No entanto, a eficácia deste processo depende fortemente de como a "temperatura" (que controla a probabilidade de aceitar soluções piores) é diminuída ao longo do tempo. Uma agenda de arrefecimento mal escolhida pode levar a uma convergência prematura ou a tempos de execução excessivamente longos.