A pedestrian review of the theory and application of the simulated annealing algorithm

Simulated annealing is a combinatorial optimization method based on randomization techniques. The method originates from the analogy between the annealing of solids, as described by the theory of statistical physics, and the optimization of large combinatorial problems. Here we review the basic theory of simulated annealing and recite a number of applications of the method. The theoretical review includes concepts of the theory of homogeneous and inhomogeneous Markov chains, an analysis of the asymptotic convergence of the algorithm, and a discussion of the finite-time behaviour. Furthermore, a section is devoted to the relation between statistical physics and the optimization of combinatorial problems. General aspects related to the application of the algorithm are briefly discussed. The list of applications includes combinatorial optimization problems related to VLSI design, image processing, code design and neural networks