ISSN:
1436-4646
Keywords:
Global Optimization
;
Stochastic Optimization
;
Annealing
;
Metropolis Method
;
NP
;
Hill Climbing
;
Local Improvement
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582166
Permalink