Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1225.90162
Kirkpatrick, S.; Gelatt, C.D. jun.; Vecchi, M.P.
Optimization by simulated annealing. (English)
[J] Science 220, No. 4598, 671-680 (1983). ISSN 0036-8075

From the introduction: We briefly review the central constructs in combinatorial optimization and in statistical mechanics and then develop the similarities between the two fields. We show how the Metropolis algorithm for approximate numerical simulation of the behavior of a many-body system at a finite temperature provides a natural tool for bringing the techniques of statistical mechanics to bear on optimization.\par We apply this point of view to a number of problems arising in optimal design of computers. Applications to partitioning, component placement, and wiring of electronic systems are described in this article. In each context, we introduce the problem and discuss the improvements available from optimization.\par Of classic optimization problems, the traveling salesman problem has received the most intensive study. To test the power of simulated annealing, we use the algorithm on traveling salesman problems with as many as several thousand cities. This work is described in a final section, followed by our conclusions.

MSC 2000:: *90C59 Approximation methods and heuristics
90C27 Combinatorial programming
82C80 Numerical methods of time-dependent statistical mechanics

Cited in: Zbl 1249.60166 Zbl 1195.65084 Zbl 0946.90070 Zbl 0713.90063 Zbl 0633.94025 Zbl 0593.90054

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]