A convergence analysis of generalized hill climbing algorithms

Kelly A. Sullivan, Sheldon H. Jacobson

Research output: Contribution to journalArticle

Abstract

Generalized hill climbing (GHC) algorithms provide a well-defined framework for describing the performance of local search algorithms for discrete optimization problems. Necessary and sufficient convergence conditions for GHC algorithms are presented. These convergence conditions are derived using a new iteration classification scheme for GHC algorithms. The implications of the necessary and the sufficient convergence conditions for GHC algorithms with respect to existing convergence theory for simulated annealing are also discussed.

Original languageEnglish (US)
Pages (from-to)1288-1293
Number of pages6
JournalIEEE Transactions on Automatic Control
Volume46
Issue number8
DOIs
StatePublished - Aug 1 2001

    Fingerprint

Keywords

  • Convergence
  • Discrete optimization
  • Hill climbing algorithms
  • Local search
  • Markov chain
  • Metaheuristics
  • Simulated annealing

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this