A Bayesian approach to simulated annealing

P.J.M. Laarhoven van, C.G.E. Boender, E.H.L. Aarts, A.H.G. Rinnooy Kan

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Simulated annealing is a probabilistic algorithm for approximately solving large combinatorial optimization problems. The algorithm can mathematically be described as the generation of a series of Markov chainst in which each Markov chain can be viewed as the outcome of a random experiment with unknown parameters (the probability of sampling a cost function value). Assuming a probability distribution on the vaJues of the unknown parameters (the prior distribution) and given the sequence of configurations resulting from the generation of a Markov chain, we use Bayes's theorem to derive the posterior distribution on the values of the parameters. Numerical experiments are described whicb show that the posterior distribution can he used to predict accurately the behavior of tbe algorithm eorresponding to the next Markov chain. This information is also used to derive optimal rules for choosing same of the parameters governing the convergence of the algorithm.
Original languageEnglish
Pages (from-to)453-475
Number of pages23
JournalProbability in the Engineering and Informational Sciences
Volume3
Issue number4
DOIs
Publication statusPublished - 1989
Externally publishedYes

    Fingerprint

Cite this