Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Simulated Annealing

Categories: Vision

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.



Add Comment

No comments.