SECTION 2
SIMULATED ANNEALING
2.1 Overview
As noted in the introduction, a very commonly employed approach to the solution
of nonconvex combinatorial optimization problems is a stochastic relaxation technique
introduced by Kirkpatrick et al. and referred to as simulated annealing [KiGe83]. The
technique is so named by virtue of its analogy to the annealing of solids, in which a crys-
talline solid is heated to its melting point and then allowed to cool very gradually until it
is again in the solid phase at some nominal temperature. In the limiting case of
infinitesimal cooling rate and absolute zero final temperature, the resulting solid achieves
its most regular possible crystal lattice configuration (i.e. minimum lattice energy state),
and hence is free of crystal defects. Simulated annealing establishes the connection
between this sort of thermodynamic behavior and the search for the global minimum of
an objective function in a combinatorial optimization problem, and further, it provides an
algorithmic means of exploiting the connection. This section is a review of the technique
with special emphasis on known results which bound the convergence behavior of com-
puter algorithms belonging to the class.
2.2 Statistical Mechanics and Annealing of Solids
The fundamental assumption of statistical physics is that the thermodynamic behav-
ior of a many particle system can be represented by a statistical ensemble, and that if the
system is in thermal equilibrium, the time averages of macroscopic thermodynamic
properties of the system are equal to the corresponding ensemble averages (crgodicity
hypothesis). The random variable represented by the ensemble is the system thermal
energy, and at thermal equilibrium the probability distribution is completely determined