Simulated Annealing

E. H. L. Aarts and H. M. M. Ten Eikelder

ABSTRACT

Simulated annealing is a powerful randomized local search technique for finding optimal or nearly optimal solutions of combinatorial optimization problems. The method has its origin in the annealing process in condensed matter physics. Simulated annealing presupposes the definition of a neighborhood. The algorithm simulates a walk through the solution space that is obtained by repeatedly moving from a solution to a neighboring one. Steps that give rise to improvements are always accepted, while deteriorating steps are only accepted with a certain probability. This acceptance probability is controlled by a parameter and usually tends to zero during the search process. In this article we describe theoretical convergence results as well as some practical aspects of simulated annealing.