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:

- A method of generating new points
- An
*annealing schedule*dictating how to reduce**T**as the algorithm progresses.

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.

Fri Mar 28 14:12:50 GMT 1997