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 journalArticleAcademicpeer-review

    3 Citations (Scopus)
    1 Downloads (Pure)

    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
    JournalProbability in the Engineering and Informational Sciences
    Volume3
    Issue number4
    DOIs
    Publication statusPublished - 1989

    Fingerprint

    Dive into the research topics of 'A Bayesian approach to simulated annealing'. Together they form a unique fingerprint.

    Cite this