Simulated Annealing

Annealing is a technique in which a metal is heated to a high temperature, then allowed to cool slowly; this relieves internal stresses.

Simulated annealing[S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, ``Optimization by Simulated Annealing'', Science vol. 220, no. 4598 (13 May 1983), pp. 671-680.] is analogous to hill-climbing in which it is possible to make some moves that are locally non-optimal.

By analogy with statistical thermodynamics, it is assumed that the goal is to minimize the ``energy'' E of a system. If a move causes a change &Delta E ,

In simulated annealing, an evaluation function f replaces E . An artificial ``temperature'' is created, initially high enough for many moves to be accepted, and progressively reduced.

Contents    Page-10    Prev    Next    Page+10    Index