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.