Simulated Annealing


Enrico Schumann


Simulated Annealing

Review Status


The algorithm


Simulated Annealing (SA) was introduced by Kirkpatrick (1983) [1]. Like other trajectory methods, it evolves a single solution over time. By changing this solution gradually, the algorithm follows some path (‘trajectory’) through the search space. The algorithm to the right gives the pseudocode for the procedure.
SA starts with a random solution $x^{\mathrm{c}}$ and creates a new solution $x^{\mathrm{n}}$ by adding a small perturbation to $x^{\mathrm{c}}$. If the new solution is better ($\vartriangle \, < 0$), it is accepted. In case it is worse, though, SA applies a stochastic acceptance criterion, thus there is still a chance that the new solution is accepted, albeit only with a certain probability. This probability is a decreasing function of both the order of magnitude of the deterioration and the time the algorithm has already run. The latter feature is controlled by the temperature parameter $T$ which is reduced over time; hence impairments in the objective function become less likely to be accepted and eventually SA turns into classical local search. Here, the algorithm stops after a predefined number of iterations $R_{\mathrm{max}}$; of course, alternative stopping criteria are possible.

Internal Links

Threshold Accepting
Related Articles

External links

1. Kirkpatrick, S., C. D. Gelatt and M. P. Vecchi (1983). Optimization by simulated annealing. Science 220, 671-680.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License