Go to the first, previous, next, last section, table of contents.

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

if @math{E_{i+1} > E_i}, and @math{p = 1} when @math{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 @math{T} and inversely proportional to the energy difference @math{E_{i+1} - E_i}.

The temperature @math{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 After a few search steps using this distribution, the temperature T is lowered according to some scheme, for example where @math{\mu_T} is slightly greater than 1.


Go to the first, previous, next, last section, table of contents.