23.1 Simulated Annealing algorithm

We take 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) and another random walk is taken.

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

An initial guess is supplied. At each step, a point is chosen at a random distance from the current one, where the random distance r is distributed according to a Boltzmann distribution r = e^(-E/kT). After a few search steps using this distribution, the temperature T is lowered according to some scheme, for example T -> T/mu_T where \mu_T is slightly greater than 1.