Simulated Annealing

Author

Enrico Schumann

Keywords

Simulated Annealing

Review Status

Unreviewed

The algorithm

PC_SA1.pdf

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

Concepts
Threshold Accepting
Tutorials
Tips
Related Articles

External links

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

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