Simulated annealing. (English) Zbl 0764.60073

Bertsimas, Dimitris; Tsitsiklis, John

Probability and algorithms, 17-29 (1992).

Summary: [For the entire collection see Zbl 0755.00002.]
Simulated annealing is a probabilistic method proposed by S. Kirkpatrick, C. D. Gelett and M. P. Vecchi [Science 220, 621-630 (1983)] and V. Černý [J. Optimization Theory Appl. 45, 41-51 (1985; Zbl 0534.90091)] for finding the global minimum of a cost function that may possess several local minima. It works by emulating the physical process whereby a solid is slowly cooled so that when eventually its structure is “frozen”, it happens at a minimum energy configuration. We restrict ourselves to the case of a cost function defined on a finite set. Extensions of simulated annealing to the case of functions defined on continuous sets have also been introduced in the literature. Our goal in this review is to describe the method, its convergence, and its behavior in applications.

MSC:

60J20

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

Keywords:

simulated annealing; local minima; minimum energy configuration

Citations:

Zbl 0554.90097; Zbl 0755.00002; Zbl 0534.90091