next up previous contents
Next: Genetic Algorithms Up: Global Optimization Previous: Simplex Algorithm

Simulated Annealing

Simulated annealing methods are based on an analogy with thermodynamics and the way that liquids freeze and crystallize. At high temperatures the molecules of a liquid move about freely. If the liquid is cooled slowly they gradually lose mobility and often form a pure crystal that is completely ordered - the (global) minimum energy state for the system. If, however, the system is cooled rapidly it falls into a polycrystalline or amorphous state, a local minimum with higher energy than the pure crystal state. The important thing is the slow cooling, allowing the atoms to sort themselves out gradually.

The various local minimizers above are analogous to rapid cooling regimes; they go straight for the nearest minima, going downhill as fast as they can, and never going uphill.

Simulated annealing algorithms allow occasional uphill jumps, allowing them to hop out of local minima and giving them a better chance of finding the global minimum. Schemes which allow such uphill jumps are known as Metropolis algorithms, after the person who first popularized them.

Typically they make use of the Boltzmann probability distribution

which indicates that at a given temperature T a system can be in a range of possible energy states - the higher the temperature the more likely it is to be in a high energy state. Even at low temperatures there is a (small) chance of a high energy state.

The Metropolis algorithm moves from a point a to with probability (where means certainty).

Two other things are required for the algorithm:

Unfortunately both of these are problem specific, the annealing schedule particularly so. Press et al [6] believe that generating new points randomly is inefficient and give an algorithm based on the Simplex method. The choice of annealing schedule will depend on the expected range of function values and the shape of the function surface. Usually experimentation is required to obtain a method that works well for a particular problem.

Simulated Annealing has proved to be particularly useful for combinatoric type problems of discrete variables (eg the travelling salesman problem) where there may not even be an implicit ordering in the allowed values of the variables.

See also [16] [17].



next up previous contents
Next: Genetic Algorithms Up: Global Optimization Previous: Simplex Algorithm



Bob Fisher
Fri Mar 28 14:12:50 GMT 1997