Abstract
Generalized hill climbing (GHC) algorithms provide a general local search strategy to address intractable discrete optimization problems. GHC algorithms include as special cases stochastic local search algorithms such as simulated annealing and the noising method, among others. In this paper, a proof of convergence of GHC algorithms is presented, that relaxes the sufficient conditions for the most general convergence proof for stochastic local search algorithms in the literature. Note that classical convergence proofs for stochastic local search algorithms require either that an exponential distribution be used to model the acceptance of candidate solutions along a search trajectory, or that the Markov chain model of the algorithm must be reversible. The proof in this paper removes these limitations, by introducing a new path concept between global and local optima. Convergence is based on the asymptotic behavior of path probabilities between local and global optima. Examples are given to illustrate the convergence conditions. Implications of this result are also discussed.
Original language | English (US) |
---|---|
Pages (from-to) | 37-57 |
Number of pages | 21 |
Journal | Discrete Applied Mathematics |
Volume | 119 |
Issue number | 1-2 |
DOIs | |
State | Published - Jun 15 2002 |
Keywords
- Convergence
- Discrete optimization
- Hill climbing algorithms
- Local search
- Simulated annealing
- Threshold accepting
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics