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

Simulated annealing
Bayesian Approach
Simulated Annealing
Markov chain
Markov processes
Posterior distribution
Unknown Parameters
Random experiment
Bayes' Formula
Probabilistic Algorithms
Prior distribution
Combinatorial Optimization Problem
Cost Function
Combinatorial optimization
Probability Distribution
Numerical Experiment
Cost functions
Probability distributions
Predict
Configuration

Cite this

Laarhoven van, P.J.M. ; Boender, C.G.E. ; Aarts, E.H.L. ; Rinnooy Kan, A.H.G. / A Bayesian approach to simulated annealing. In: Probability in the Engineering and Informational Sciences. 1989 ; Vol. 3, No. 4. pp. 453-475.
@article{37d16a89a8494c4aaa5043ade061346e,
title = "A Bayesian approach to simulated annealing",
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.",
author = "{Laarhoven van}, P.J.M. and C.G.E. Boender and E.H.L. Aarts and {Rinnooy Kan}, A.H.G.",
year = "1989",
doi = "10.1017/S0269964800001327",
language = "English",
volume = "3",
pages = "453--475",
journal = "Probability in the Engineering and Informational Sciences",
issn = "0269-9648",
publisher = "Cambridge University Press",
number = "4",

}

A Bayesian approach to simulated annealing. / Laarhoven van, P.J.M.; Boender, C.G.E.; Aarts, E.H.L.; Rinnooy Kan, A.H.G.

In: Probability in the Engineering and Informational Sciences, Vol. 3, No. 4, 1989, p. 453-475.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - A Bayesian approach to simulated annealing

AU - Laarhoven van, P.J.M.

AU - Boender, C.G.E.

AU - Aarts, E.H.L.

AU - Rinnooy Kan, A.H.G.

PY - 1989

Y1 - 1989

N2 - 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.

AB - 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.

U2 - 10.1017/S0269964800001327

DO - 10.1017/S0269964800001327

M3 - Article

VL - 3

SP - 453

EP - 475

JO - Probability in the Engineering and Informational Sciences

JF - Probability in the Engineering and Informational Sciences

SN - 0269-9648

IS - 4

ER -