13.3 Simulated Annealing 703
13.3.2 Procedure
The simulated annealing method simulates the process of slow cooling of molten
metal to achieve the minimum function value in a minimization problem. The cooling
phenomenon of the molten metal is simulated by introducing a temperature-like param-
eter and controlling it using the concept of Boltzmann’s probability distribution. The
Boltzmann’s probability distribution implies that the energy (E) of a system in thermal
equilibrium at temperatureTis distributed probabilistically according to the relation
P (E)=e−^ E/kT (13.14)
whereP (E)denotes the probability of achieving the energy levelE, andkis called the
Boltzmann’s constant. Equation (13.14) shows that at high temperatures the system has
nearly a uniform probability of being at any energy state; however, at low temperatures,
the system has a small probability of being at a high-energy state. This indicates that
when the search process is assumed to follow Boltzmann’s probability distribution, the
convergence of the simulated annealing algorithm can be controlled by controlling the
temperatureT. The method of implementing the Boltzmann’s probability distribution
in simulated thermodynamic systems, suggested by Metropolis et al. [13.37], can also
be used in the context of minimization of functions.
In the case of function minimization, let the current design point (state) beXi,
with the corresponding value of the objective function given byfi= f(Xi) Similar.
to the energy state of a thermodynamic system, the energyEiat stateXiis given by
Ei=fi= f(Xi) (13.15)
Then, according to the Metropolis criterion, the probability of the next design point
(state)Xi+ 1 depends on the difference in the energy state or function valu es at the two
design points (states) given by
E=Ei+ 1 −Ei =f=fi+ 1 −fi≡ f(Xi+ 1 ) −f(Xi) (13.16)
The new state or design pointXi+ 1 can be found using the Boltzmann’s probability
distribution:
P[Ei+ 1 ] =min
{
1 , e−^ E/kT
}
(13.17)
The Boltzmann’s constant serves as a scaling factor in simulated annealing and, as such,
can be chosen as 1 for simplicity. Note that ifE≤0, Eq. (13.17) givesP[Ei+ 1 ]= 1
and hence the pointXi+ 1 is always accepted. This is a logical choice in the context of
minimization of a function because the function value atXi+ 1 , fi+ 1 , is better (smaller)
than atXi, fi, and hence the design vectorXi+ 1 must be accepted. On the other
hand, whenE>0, the function valuefi+ 1 atXi+ 1 is worse (larger) than the one at
Xi. According to most conventional optimization procedures, the pointXi+ 1 cannot be
accepted as the next point in the iterative process. However, the probability of accepting
the pointXi+ 1 , in spite of its being worse thanXiin terms of the objective function
value, is finite (although it may be small) according to the Metropolis criterion. Note
that the probability of accepting the pointXi+ 1
P[Ei+ 1 ]=
{
e−^ E/kT
}
(13.18)
