Convergence of an annealing algorithm |
| |
Authors: | M Lundy A Mees |
| |
Institution: | (1) Department of Pure Mathematics and Mathematical Statistics, Cambridge University, 16 Mill Lane, CB2 1SB Cambridge, UK;(2) Department of Mathematics, University of Western Australia, 6009 Nedlands, Western, Australia |
| |
Abstract: | 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. |
| |
Keywords: | Global Optimization Stochastic Optimization Annealing Metropolis Method NP Hill Climbing Local Improvement |
本文献已被 SpringerLink 等数据库收录! |
|