Title

Simulated Annealing on NP-Complete Problems

Authors

Russell W. Howell, Westmont CollegeFollow

Document Type

Conference Proceeding

Publication Date

6-2-1989

Abstract

The Random House Dictionary defines anneal as " ... to free (glass, metals, etc.) from internal stress by heating and gradually cooling." In the physical world, impurities are annealed out of a substance by heating it to a high temperature. As it is cooled, its molecular structure gradually settles into a stable "low-energy" configuration. It is important to cool the substance slowly, especially at lower temperatures, so that impurities do not get "frozen" into place. With careful cooling, a low-energy state can eventually be reached. This state may not be the one with the lowest potential energy, where the spins of the electrons are uniformly aligned, but it is usually one where there are very few domainseach one containing electrons with approximately aligned spins.

There is a surprising analogy between the process described above and an algorithm that has proven to be successful in large classes of combinatorial optimization problems. The algorithm was formally introduced in its present form in 1983 by Kirkpatrick, Gelatt and Vecchi [5], although slightly different versions were used as early as 1953 by Metropolis et al. [9]. Because the algorithm searches for "optimized states" of certain combinatorial problems, and because it is guided by a control parameter (temperature) which is initially large and gradually becomes small, the algorithm has been given the name simulated annealing.

Recommended Citation

Howell, Russell W., "Simulated Annealing on NP-Complete Problems" (1989). ACMS Conference Proceedings 1989. 4.
https://pillars.taylor.edu/acms-1989/4