9.3.3 Siman

Simulated annealing [11,102] is a modified version of hill climbing. Starting from a random point in the search space, a random move is made. If this move yields a better point, it is accepted. If it yields a worse point, it is accepted only with a certain probability $p(t)$ which depends on the time $t$. The function $p(t)$ is initially close to one, but gradually reduces to zero analogous to the cooling of a solid. Hence initially any moves are accepted, but as the temperature reduces, the probability of accepting a negative move is lowered. Negative moves are sometimes essential if local maxima have to be escaped, but obviously too many negative moves simply lead away from an extremum.

Versions like fast re-annealing, adaptive annealing and parallel annealing have been developed. In the SIESTA framework an interface to an implementation called adaptive simulated annealing [55] is provided.