Next: Simulated Annealing functions, Up: Simulated Annealing [Index]

The simulated annealing algorithm takes random walks through the problem space, looking for points with low energies; in these random walks, the probability of taking a step is determined by the Boltzmann distribution,

p = e^{-(E_{i+1} - E_i)/(kT)}

if
*E_{i+1} > E_i*, and
*p = 1* when
*E_{i+1} <= E_i*.

In other words, a step will occur if the new energy is lower. If
the new energy is higher, the transition can still occur, and its
likelihood is proportional to the temperature *T* and inversely
proportional to the energy difference
*E_{i+1} - E_i*.

The temperature *T* is initially set to a high value, and a random
walk is carried out at that temperature. Then the temperature is
lowered very slightly according to a *cooling schedule*, for
example: *T -> T/mu_T*
where *\mu_T* is slightly greater than 1.

The slight probability of taking a step that gives higher energy is what allows simulated annealing to frequently get out of local minima.