A tutorial survey of theory and applications of simulated annealing

The basic theory of simulated annealing is reviewed, its recent applications are surveyed, and the theoretical approaches that have been used to study the technique are surveyed.

Abstract

Annealing is the process of slowly cooling a physical system in order to obtain states with globally minimum energy. By simulating such a process, near globally-minimum-cost solutions can be found for very large optimization problems. The purpose of this paper is to review the basic theory of simulated annealing, to survey its recent applications, and to survey the theoretical approaches that have been used to study the technique. The applications include image restoration, combinatorial optimization (eg VLSI routing and placement), code design for communication systems and certain aspects of artificial intelligence. The theoretical tools for analysis include the theory of nonstationary Markov chains, statistical physics analysis techniques, large deviation theory and singular perturbation theory.