Concepts of scale in simulated annealing

Abstract

Simulated annealing is a powerful technique for finding near‐optimal solutions to NP‐complete combinatorial optimization problems. In this technique, the states of a physical system are generalized to states of a system being optimized, the physical energy is generalized to the function being minimized, and the temperature is generalized to a control parameter for the optimization process. Wire length minimization in circuit placement is used as an example to show how ideas from statistical physics can elucidate the annealing process. The mean of the distribution of states in energy is a maximum energy scale of the system, its standard deviation defines the maximum temperature scale, and the minimum change in energy defines the minimum temperature scale. These temperature scales tell us where to begin and end an annealing schedule. The ‘‘size’’ of a class of moves within the state space of the system is defined as the average change in the energy induced by moves of that class. These move scales are related to the characteristic temperature scales of a system, and show that a move class should be used when it gives an average change in energy on the order of the temperature. This, in turn, helps improve the performance of the algorithm.