Simulated annealing

Recozimento simulado (ou Simulated Annealing) é uma meta-heurística para otimização que consiste numa técnica de busca local probabilística, e se fundamenta numa analogia com a termodinâmica. A metaheurística usada é uma metáfora de um processo térmico, dito recozimento ou annealing, 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 fase perlítica em austenita; 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 resulta em 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 uma redução dos defeitos do material, como resultado prático. 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 {\displaystyle T} (dita Temperatura, por analogia). Quanto maior for T {\displaystyle 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 {\displaystyle 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.