Catalogue of Artificial Intelligence Techniques
Author(s): W.F. Clocksin, Geoffrey Sampson
Simulated annealing is a technique for solving combinatorial optimisation problems by means of the metropolis algorithm. Optimisation requires the use of an objective function (or evaluation function), which represents a quantitative measure of the `goodness' of a proposed solution. A conventional technique for iterative improvement considers local changes to a proposed solution, accepting just those changes that improve the solution. On realistic problems, this can lead to a local optimum at which all subsequent changes do not improve the solution, even though better solutions are available some distance away. By contrast, in an annealing system, the acceptance of a proposed change depends on a function of both the goodness of the change and a Gaussian noise source. The standard deviation of the noise begins high and is gradually reduced according to a predetermined `annealing schedule' until no further changes occur. The term `annealing' is suggested by the formal connection between statistical thermodynamics and combinatorial optimisation. Simulated annealing is being applied in perception and learning research, and in computer-aided design.
- Kirkparick, S., Gelatt, C.D. and Vecchi, M.P., Optimisation by simulated annealing Science 220 (1983), 671--680.