# Optimization by Simulated Annealing

@article{Kirkpatrick1983OptimizationBS, title={Optimization by Simulated Annealing}, author={Scott Kirkpatrick and Charles D. Gelatt and Michelle Vecchi}, journal={Science}, year={1983}, volume={220}, pages={671 - 680} }

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and… Expand

#### Topics from this paper

#### 39,178 Citations

Modelling of Complex Systems by Simulated Annealing

- Computer Science
- 1991

Just as Nature manages to cool a macroscopic system into or very close to its ground state in a short period of time even though its number of degrees of freedom is of the order of Avogadro’s number, so does simulated annealing rapidly find a good guess of the solution of the posed problem. Expand

Configuration Space Analysis for Optimization Problems

- Computer Science
- 1986

Simulated annealing (a stochastic algorithm based on the Monte Carlo method) is used to find approximate solutions to complex optimization problems involving frustrated disordered systems. Expand

Stochastic Models of Parallel Systems for Global Optimization

- Computer Science
- 1987

The objective of this paper is to consider an interacting particle system model of a many searcher system and to reformulate some simple ideas from statistical physics in this context. Expand

A Monte carlo simulated annealing approach to optimization over continuous variables

- Computer Science
- 1984

Numerical optimization methods based on thermodynamic concepts are extended to the case of continuous multidimensional parameter spaces, and a self-regulatory mechanism for choosing the random step distribution is described. Expand

Natural and simulated annealing

- Computer Science
- Computing in Science & Engineering
- 2001

Simulated annealing is an optimization procedure based on the behavior of condensed matter at low temperatures that mirrors the annealing process that takes place in nature. The procedure employs… Expand

Parallel simulated annealing for shape detection

- Computer Science
- 1992

The analogy between this problem and a combinatorial optimization problem was observed in [2] and [13]. Expand

Optimal ensemble size for parallel implementations of simulated annealing

- Mathematics
- 1990

Abstract We determine the optimal ensemble size for a simulated annealing problem based on assumptions about scaling properties of the system dynamics and of the density of states in the low energy… Expand

Application of statistical mechanics to NP-complete problems in combinatorial optimisation

- Mathematics
- 1986

Recently developed techniques of the statistical mechanics of random systems are applied to the graph partitioning problem. The averaged cost function is calculated and agrees well with numerical… Expand

Statistical Mechanics: a General Approach to Combinatorial Optimization

- Computer Science
- 1986

The aim of this work was to investigate the possibility of using statistical mechanics as an alternative framework to study complex combinatorial optimization problems by proposing a selecting procedure which favours the choice of neighbouring trial solutions. Expand

Statistical Physics and Optimization: Binary Sequences with Small Autocorrelations

- Computer Science
- 1988

For long sequences, the energy minima found with the simulated annealing procedure differ by about a factor of 2 from the conjectured “true” minimum, indicating that the lowest-energy configurations are extremely isolated in configuration space. Expand

#### References

SHOWING 1-10 OF 70 REFERENCES

Equation of state calculations by fast computing machines

- Physics
- 1953

A general method, suitable for fast computing machines, for investigating such properties as equations of state for substances consisting of interacting individual molecules is described. The method… Expand

Solvable Model of a Spin-Glass

- Physics
- 1975

We consider an Ising model in which the spins are coupled by infinite-ranged random interactions independently distributed with a Gaussian probability density. Both "spinglass" and ferromagnetic… Expand

The Design and Analysis of Computer Algorithms

- Computer Science
- 1974

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs. Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand

An Effective Heuristic Algorithm for the Traveling-Salesman Problem

- Mathematics, Computer Science
- Oper. Res.
- 1973

This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem. The procedure is based on a general… Expand

Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality

- Mathematics
- 1980

We report the solution to optimality of ten large-scale symmetric travelling salesman problems. The travelling salesman problem (TSP) is one of the standard problems of the Operations… Expand

Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

- Mathematics, Computer Science
- Math. Oper. Res.
- 1977

This work considers partitioning algorithms for the approximate solution of large instances of the traveling-salesman problem in the plane, in which partitioning is used in conjunction with existing heuristic algorithms. Expand

"J."

- 1890

however (for it was the literal soul of the life of the Redeemer, John xv. io), is the peculiar token of fellowship with the Redeemer. That love to God (what is meant here is not God’s love to men)… Expand

Computers and Intractability: A Guide to the Theory of NPCompleteness (Freeman

- San Francisco,
- 1979