Simulated Annealing

Enrico Schumann

## Keywords

Simulated Annealing

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.