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 means 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 changes in energy define the minimum temperature scale. These temperature scales indicate where to begin and end an annealing schedule. The 'size' of a class of moves 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 they 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.