Kirkpatrik Et Al: Optimization by Simulated Annealing

by Carson Reynolds

Kirkpatrick presents a method for combinatorial optimization that draws from statistical mechanics models for n-body systems. A brief description of the algorithm would be that after a state-description is arrived at, one system state is randomly generated. Following this, the system’s “temperature” is raised until the system “melts” allowing for alterations to parameters that make large contributions towards the target of the system’s objective function or “ground state.” The system is then allowed to cool according to schedule so that it does not settle into local minima or “degenerate ground states.” During this phase smaller, more local adjustments are made. One could metaphorically think of a system “blurring” so that only large-scale features are visible and then sharpening on the neighborhood of the “blurred” minimum.

Kirkpatrick and his co-authors apply the technique to various computer design problems such as circuit placement, wiring network design, and chip placement. Lastly, the authors use the algorithm to find approximate solutions to the traveling salesman problem with large N inputs.

One might think of simulated annealing as a gradient decent method for non-linear optimization problems. It would likely be used on the same class of problems to which genetic algorithms are typically applied. The advantages to using simulated annealing seem to be that with a slow enough cooling schedule it guarantees approximate optimality. However some have noted that evolutionary algorithms can be shown to have a greater probability of success than simulated annealing. Empirical evidence, however suggests that simulated annealing may be more computationally efficient than genetic algorithms.

Advertisements