Simulated annealing methods with general acceptance probabilities
- 1 September 1987
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 24 (3) , 657-667
- https://doi.org/10.2307/3214097
Abstract
Heuristic solution methods for combinatorial optimization problems are often based on local neighborhood searches. These tend to get trapped in a local optimum and the final result is often heavily dependent on the starting solution. Simulated annealing methods attempt to avoid these problems by randomizing the procedure so as to allow for occasional changes that worsen the solution. In this paper we provide probabilistic analyses of different designs of these methods.Keywords
This publication has 13 references indexed in Scilit:
- Convergence of an annealing algorithmMathematical Programming, 1986
- Nonstationary Markov chains and convergence of the annealing algorithmJournal of Statistical Physics, 1985
- Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithmJournal of Optimization Theory and Applications, 1985
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Optimization by Simulated AnnealingScience, 1983
- The Condition of a Finite Markov Chain and Perturbation Bounds for the Limiting ProbabilitiesSIAM Journal on Algebraic Discrete Methods, 1980
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsManagement Science, 1977
- The rate of convergence of certain nonhomogeneous Markov chainsProbability Theory and Related Fields, 1976
- Monte Carlo sampling methods using Markov chains and their applicationsBiometrika, 1970
- Central Limit Theorem for Nonstationary Markov Chains. IITheory of Probability and Its Applications, 1956