Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-26T16:39:56.391Z Has data issue: false hasContentIssue false
  • English
  • Français

A Bayesian Approach to Simulated Annealing

Published online by Cambridge University Press:  27 July 2009

P.J.M. Van Laarhoven ,
C.G.E. Boender ,
E.H.L. Aarts  and
A. H. G. Rinnooy Kan
P.J.M. Van Laarhoven
Affiliation:
Philips Research Laboratories Eindhoven, the Netherlands
C.G.E. Boender
Affiliation:
Erasmus University, Rotterdam, the Netherlands
E.H.L. Aarts
Affiliation:
Philips Research Laboratories Eindhoven, the Netherlands andEindhoven University of Technology Eindhoven, the Netherlands
A. H. G. Rinnooy Kan
Affiliation:
Erasmus University, Rotterdam, the Netherlands
Get access Rights & Permissions [Opens in a new window]

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 chains, 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 values 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 which show that the posterior distribution can be used to predict accurately the behavior of the algorithm corresponding to the next Markov chain. This information is also used to derive optimal rules for choosing some of the parameters governing the convergence of the algorithm.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 3 , Issue 4 , October 1989 , pp. 453 - 475
Copyright
Copyright © Cambridge University Press 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aarts, E.H.L., Korst, J.H.M., & Laarhoven, P.J.M. Van (1988). Solving travelling salesman problems by simulated annealing: a quantitative analysis. Journal of Statistical Physics 50: 187–206.CrossRefGoogle Scholar
Aarts, E.H.L., & Laarhoven, P.J.M. Van (1985). Statistical cooling: a general approach to comrn binatorial optimization problems. Philips Journal of Research 40: 193–226.Google Scholar
Aarts, E.H.L. & Laarhoven, P.J.M. Van (1989). Simulated annealing: an introduction. Statistica Neerlandica 43.Google Scholar
Bayes, Th.R. (1763). An essay towards solving a problem in the doctrine of chances. Philosophical Transactions of the Royal Society London 370–418; reprinted in 1958Google Scholar
in:Biometrika 45: 293–315.Google Scholar
Černy, V. (1985). Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications 45: 41–51.Google Scholar
Feller, W. (1950). An introduction to probability theory and applications, Vol. 1. New York: Wiley.Google Scholar
Grötschel, M. (1977). Polyedrische Charakierisierungen kombinatorischer Optimierungsprobfeme (in German). Meisenheim am Glan: Ham.Google Scholar
Kirkpatrick, S., Gelatt, C.D. Jr, & Vecchi, M.P. (1983). Optimization by simulated annealing. Science 220: 671–680.CrossRefGoogle ScholarPubMed
Laarhoven, P.J.M. Van (1988). Theoretical and computational aspects of simulated annealing. CWI Tract No. 51, Amsterdam: Centre for Mathematics and Informatics.Google Scholar
Laarhoven, P.J.M. Van & Aarts, E.H.L. (1987). Simulated annealing: theory and applications. Dordrecht: Reidel.CrossRefGoogle Scholar
Laarhoven, P.J.M. Van & Kalker, A.A.C.M. (1988). On the computation of Lauricella functions of the fourth kind. Journal of Computational and Applied Mathematics 21: 369–375.Google Scholar
Lauricella, G. (1893). Sulle funzioni ipergeometriche a piu variabili. Rendiconti del Circolo Illaematico di Palermo 7: 111–113.CrossRefGoogle Scholar
Lawler, E.L. (1976). Combinatorial optimization: networks and matroids. New York: Holt, Rinehart and Winston.Google Scholar
Lawler, E.L., Lenstra, J.K., Rinnooy, Kan A.H.G., & Shmoys, D.B. (eds.) (1985). The traveling ralesman problem: a guided tour of combinatorial optimization. Chichester: Wiley.Google Scholar
Lindley, D.V. (1978). Bayesian statistics, A review. Philadelphia: SIAM.Google Scholar
Papadimitriou, C.H. & Steiglitz, K. (1982). Combinatorial optimization: algorithms and complexity. New York: Prentice-Hall.Google Scholar
Riordan, J. (1978). An introduction to combinatorial analysis. Princeton: Princeton University Press.Google Scholar
Silver, E.A. (1965). Bayesian determination of the reorder point of a slow moving item. Operations Research 13: 989–997.CrossRefGoogle Scholar
Wilks, S.S. (1962). Mathematical statistics. New York: Wiley.Google Scholar