Convergence and finite-time behavior of simulated annealing
- 1 December 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 761-767
- https://doi.org/10.1109/cdc.1985.268600
Abstract
Simulated Annealing is a randomized algorithm which has been proposed for finding globally optimum least-cost configurations in large NP-complete problems with cost functions which may have many local minima. A theoretical analysis of Simulated Annealing based on its precise model, a time-inhomogeneous Markov chain, is presented. An annealing schedule is given for which the Markov chain is strongly ergodic and the algorithm converges to a global optimum. The finite-time behavior of Simulated Annealing is also analyzed and a bound obtained on the departure of the probability distribution of the state at finite time from the optimum. This bound gives an estimate of the rate of convergence and insights into the conditions on the annealing schedule which gives optimum performance.Keywords
This publication has 11 references indexed in Scilit:
- Convergence of an annealing algorithmMathematical Programming, 1986
- Convergence and finite-time behavior of simulated annealingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Nonstationary Markov chains and convergence of the annealing algorithmJournal of Statistical Physics, 1985
- The TimberWolf placement and routing packageIEEE Journal of Solid-State Circuits, 1985
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1984
- Global Wiring by Simulated AnnealingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- Optimization by Simulated AnnealingScience, 1983
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- Strongly Ergodic Behavior for Non-Stationary Markov ProcessesThe Annals of Probability, 1973
- Central Limit Theorem for Nonstationary Markov Chains. ITheory of Probability and Its Applications, 1956