Author
Keywords
Simulated Annealing
Review Status
Unreviewed
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
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, 671680.

Weblinks 