On the convergence of generalized hill climbing algorithms

A. W. Johnson, S. H. Jacobson

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)37-57
Number of pages21
JournalDiscrete Applied Mathematics
Volume119
Issue number1-2
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'On the convergence of generalized hill climbing algorithms'. Together they form a unique fingerprint.

Cite this