Convergence of an annealing algorithm
Tóm tắt
The annealing algorithm is a stochastic optimization method which has attracted attention because of its success with certain difficult problems, including NP-hard combinatorial problems such as the travelling salesman, Steiner trees and others. There is an appealing physical analogy for its operation, but a more formal model seems desirable. In this paper we present such a model and prove that the algorithm converges with probability arbitrarily close to 1. We also show that there are cases where convergence takes exponentially long—that is, it is no better than a deterministic method. We study how the convergence rate is affected by the form of the problem. Finally we describe a version of the algorithm that terminates in polynomial time and allows a good deal of ‘practical’ confidence in the solution.
Tài liệu tham khảo
citation_title=Non-negative matrices in the mathematical sciences; citation_publication_date=1979; citation_id=CR1; citation_author=A. Berman; citation_author=R.J. Plemmons; citation_publisher=Academic Press
V. Cerny, “A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm”,Journal of Optimization Theory and Applications (1984), to appear.
A.W.F. Edwards, “Minimal evolution” (Unpublished, 1966).
citation_title=Cluster analysis; citation_publication_date=1977; citation_id=CR4; citation_author=B. Everitt; citation_publisher=Heineman Educational Books
citation_title=Computers and intractability: A guide to the theory of NP-completeness; citation_publication_date=1979; citation_id=CR5; citation_author=M.R. Garey; citation_author=D.S. Johnson; citation_publisher=W.H. Freeman
citation_journal_title=IEEE Transactions PAMI; citation_title=Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images; citation_author=S. Geman, D. Geman; citation_volume=6; citation_issue=6; citation_publication_date=1984; citation_pages=721-741; citation_id=CR6
citation_title=Stochastic models in operations research, Volume 1: Stochastic processes and operating characteristics; citation_publication_date=1982; citation_id=CR7; citation_author=D.P. Heyman; citation_author=M.J. Sobel; citation_publisher=McGraw-Hill Inc.
D.S. Johnson, private communication, 1984.
citation_title=Reversibility and stochastic networks; citation_publication_date=1979; citation_id=CR9; citation_author=F.P. Kelly; citation_publisher=Wiley
citation_title=“Optimization by simulated annealing”, Research Report RC 9355; citation_publication_date=1982; citation_id=CR10; citation_author=S. Kirkpatrick; citation_author=C.D. Gelatt; citation_author=M.P. Vecchi; citation_publisher=IBM
citation_journal_title=Biometrika; citation_title=Applications of the annealing algorithm to combinatorial problems in statistics; citation_author=M. Lundy; citation_volume=72; citation_issue=1; citation_publication_date=1985; citation_pages=191-198; citation_id=CR11
citation_title=The annealing algorithm; citation_publication_date=1984; citation_id=CR12; citation_author=M. Lundy; citation_publisher=University of Cambridge
citation_journal_title=Journal of Chemical Physics; citation_title=Equation of state calculation by fast computing machines; citation_author=N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller; citation_volume=21; citation_publication_date=1953; citation_pages=1087-1092; citation_id=CR13
citation_title=“Probabilistic hill-climbing algorithms: Properties and applications”, Memorandum No. UCB/ERL M84/34; citation_publication_date=1984; citation_id=CR14; citation_author=F. Romeo; citation_author=A. Sangiovanni-Vincentelli; citation_publisher=University of California
B.M. Schwarzschild, “ Statistical mechanics algorithm for Monte Carlo optimization“, Physics Today (May 1982) 17–19.
citation_title=Non-negative matrices and Markov chains; citation_publication_date=1981; citation_id=CR16; citation_author=E. Seneta; citation_publisher=Springer-Verlag
citation_journal_title=Annals of Human Genetics; citation_title=The method of minimum evolution; citation_author=E.A. Thompson; citation_volume=26; citation_publication_date=1973; citation_pages=333-340; citation_id=CR17
citation_journal_title=Operations Research Letters; citation_title=On the number of iterations of local improvement algorithms; citation_author=C. Tovey; citation_volume=2; citation_issue=5; citation_publication_date=1983; citation_pages=231-238; citation_id=CR18