Neural Networks without Training for Optimization - Neural Networks: Methodology and Applications - page 451

avoids the system being trapped in metastable states corresponding to high-
energy local minima.
The principle of simulated annealing, defined independently by Kirkpatrick
in 1983 [Kirkpatrick et al. 1983], Siarry in 1984 [Siarry et al. 1984] and Cerny
in 1985 [Cerny 1985], consists in implementing those concepts as a numerical
algorithm. The idea is the following: at decreasing temperature steps, the al-
gorithm uses an iterative procedure, proposed by Metropolis in 1953, to reach
a thermodynamical quasi-equilibrium state. That procedure allows escaping
from local minima with a probability that increases with temperature. When
the algorithm reaches the very low temperatures, the most probable states
are excellent solutions to the optimisation problem.

The Metropolis Algorithm

In 1953, Metropolis devised an iterative algorithm that allows finding the ther-
modynamical equilibrium state of a simulated system at a given temperature
T [Metropolis et al. 1953]. It consists in iterating the two following steps:
• Evaluation of the energy variation associated with a random elementary

transition from the current state i ,ofenergy E i , to a new state j ,ofenergy
E j :∆ E ij = E j −E i .

• Acceptance of the transition to that new state with probability A ij defined

as:

⎧
⎨ 1 if ∆ E ij =0 ,

exp

otherwise .

A ij ( T )=

∆ E ij
T

⎩

−

Simulated Annealing

The simulated annealing algorithm consists in decreasing the temperature in
a systematic way, from a high initial temperature, within the Metropolis algo-
rithm. In practice, several cooling schedules can be used. One is a geometric
decrease, in which the temperature at step k is given by

T ( k )= αT ( k − 1) ,

where α is a constant strictly smaller than 1, but close to 1.
Two types of simulated annealing were defined, depending on the cooling
schedule:
• in homogeneous simulated annealing, the temperature parameter is de-

creased only when the thermodynamical equilibrium is reached at the cur-
rent temperature; that algorithm assumes that the Metropolis procedure
has been iterated an infinite number of times, and therefore has only a
theoretical interest;

• in practice, the temperature parameter is decreased after a finite number

of evaluations of transitions at a given temperature: then the algorithm is
called in-homogeneous.