As its name implies, the Simulated Annealing (SA) exploits an analogy between the way in which a metal cools and freezes into a minimum energy crystalline structure (the annealing process) and the search for a minimum in a more general system.
The algorithm is based upon that of Metropolis et al. [46], which was originally proposed as a means of finding the equilibrium configuration of a collection of atoms at a given temperature. The connection between this algorithm and mathematical minimization was first noted by Pincus [50], but it was Kirkpatrick et al. [40] who proposed that it form the basis of an optimization technique for combinatorial (and other) problems.
SA's major
advantage over other methods is an ability to avoid becoming trapped
at local minima. The algorithm employs a random search which not
only accepts changes that decrease objective function 
, but also
some changes that increase it. The latter are accepted with a
probability
where 
is the increase in and 
is a control
parameter, which by analogy with the original application is known
as the system `temperature' irrespective of the objective function
involved.
The implementation of the SA algorithm is remarkably easy. Figure 17 shows its basic structure. The following elements must be provided:
