Analysis of simulated annealing for optimization
- 1 December 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 779-786
- https://doi.org/10.1109/cdc.1985.268603
Abstract
Simulated annealing is a popular Monte Carlo algorithm for combinatorial optimization. The annealing algorithm simulates a nonstationary finite state Markov chain whose state space Ω is the domain of the cost function to be minimized. We analyze this chain focusing on those issues most important for optimization. In all of our results we consider an arbitrary partition optimization {I, J} of Ω; important special cases are when I is the set of minimum cost states or a set of all states with sufficiently small cost. We give a lower bound on the probability that the chain visits I at some time less than or equal to k, for k = 1,2, .... This bound may be useful even when the algorithm does not converge. We give conditions under which the chain converges to I in probability and obtain an estimate of the rate of convergence as well. We also give conditions under which the chain visits I infinitely often, visits I almost always, or does not converge to I, with probability 1.Keywords
This publication has 5 references indexed in Scilit:
- Convergence and finite-time behavior of simulated annealingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Analysis of simulated annealing for optimizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Non-negative Matrices and Markov ChainsPublished by Springer Nature ,1981
- Equation of State Calculations by Fast Computing MachinesThe Journal of Chemical Physics, 1953