Gibbs distribution only represents the system's energy distribution in the stationary case
(i.e. equilibrium). If this requirement is not satisfied, defects can be frozen into the crystal
lattice preventing the system from achieving the minimum possible energy state. This
behavior is analogous to local minima entrapment in combinatorial optimization search.
The restriction on the annealing schedule necessary to avoid it is the fundamental limita-
tion on the annealing technique.
2.3 Combinatorial Optimization by Simulated Annealing
Simulated annealing approaches combinatorial optimization problems in a closely
analogous fashion. In simulated annealing, the optimization problem's solution space cor-
responds to the state space of the analogous thermodynamic system and its cost function
is analogous to the thermodynamic system's energy surface. The analog of the
thermodynamic system's temperature is a nonnegative algorithm control parameter, T.
Two other algorithm components are also required. They are the stochastic next
state generation and acceptance mechanisms, and they incorporate the dependence of the
algorithm on the control parameter, T. The next state generation mechanism is employed
by the algorithm to transform a current solution into a new candidate solution, and the
acceptance mechanism is employed to decide whether to retain or discard the proposed
new solution. Together, these stochastic operators are responsible for making the search
algorithm simulate the thermodynamic system's statistical behavior. Consequently, they
must satisfy certain requirements to assure coherent algorithm behavior. These require-
ments are explored in some depth later in the context of algorithm convergence behavior.
Conceptually, the operation of the simulated annealing algorithm can be described
as follows. The algorithm starts at some initial value of the control parameter and with
some initial solution. Then, the state generation mechanism is employed to synthesize a
new candidate solution. The new solution is examined by the acceptance mechanism and
either accepted or rejected. If it is accepted, the new solution becomes the current solu-
tion. Otherwise, the old current solution is retained. This process is repeated, generating a