5.1 Simulated Annealing

Next: 5.1.1 Solution Representation and Up: 5 Methods of Last Previous: 5 Methods of Last

## 5.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 , 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:

• a representation of possible solutions,
• a generator of random changes in solutions,
• a means of evaluating the problem functions, and
• an annealing schedule - an initial temperature and rules for lowering it as the search progresses.

Figure 17 The Structure of the Simulated Annealing Algorithm. View Figure

verena@csep1.phy.ornl.gov