What is Simulated Annealling?

Simulated annealling techniques have been applied to a wide variety of optimization problems, including the clustering problem and the job scheduling problem.

Annealing techniques simulate the physical annealling process in which metals are heated and then slowly cooled, with the result being a solid having a state of lower energy than the original solid. In an annealling process a solid is heated until liquefied, and slowly cooled sifficientlt slowly that the system is, at any time, approximately at thermodynamic equilibrium. As cooling proceeds, the system becomes more ordered and approaches a state of lowest energy. Systems that are slowly cooled (annealled) may reach a global minimum in energy, as opposed to becoming solidified in a local minima because the process of slow cooling allows the constituent molecules time to reorder themselves in states of progressively less energy.

Metropolis et al. [Metropolis 1953] introduced a simulated annealling technique known as Metropolis Monte Carlo simulation. In this scheme, the problem is described in terms of a thermodynamic system at energy E and temperature T. With a constant T, the initial configuration is perturbed and the change in energy dE is computed. If the change in energy is negative the new configuration is accepted. If the change in energy is positive it is accepted with a probability given by the Boltzmann factor. This process is iterated until sufficient sampling statistics for the current temperature T are achieved. T is then decremented and the process of perturbation is repeated until T=0. Methods based on the technique as Metropolis et al. proposed it have been successfully developed for application to a wide range of problems including protein structure optimization, image segmentation, and the travelling salesman problem.

Further Information About Simulated Annealling

• An introduction to simulated annealling

Simulated Annealling Implemented in GAUL

A general simulated annealling algorithm is implemented in GAUL. This is demonstrated in pingpong_sa.c. Several similar examples are available. These may be used to compare a simple GA search procedure against some of the other search heuristics provided within GAUL.

The following section of the tutorial discusses an algorithm known as differential evolution. The practicalities of using simulated annealling and differential Evolution are very similar, and are discussed in greater detail there.

References

• Metropolis, N. and Rosenbluth, A. and Rosenbluth, R. and Teller, A. and Teller, E. (1953) Equation of state calculations by fast computing machines J. Chem. Phys. 21:1087-1092