next up previous

4.1 Simulated Annealing

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 f, but also some changes that increase it. The latter are accepted with a probability

where is the increase in f and T is a control parameter, which by analogy with the original application is known as the system `temperature' irrespective of the objective function involved.