Analyzing the performance of generalized hill climbing algorithms

Sheldon H. Jacobson, Enver Yücesan

Research output: Contribution to journalArticle

Abstract

Generalized hill climbing algorithms provide a framework to describe and analyze metaheuristics for addressing intractable discrete optimization problems. The performance of such algorithms can be assessed asymptotically, either through convergence results or by comparison to other algorithms. This paper presents necessary and sufficient convergence conditions for generalized hill climbing algorithms. These conditions are shown to be equivalent to necessary and sufficient convergence conditions for simulated annealing when the generalized hill climbing algorithm is restricted to simulated annealing. Performance measures are also introduced that permit generalized hill climbing algorithms to be compared using random restart local search. These results identify a solution landscape parameter based on the basins of attraction for local optima that determines whether simulated annealing or random restart local search is more effective in visiting a global optimum. The implications and limitations of these results are discussed.

Original languageEnglish (US)
Pages (from-to)387-405
Number of pages19
JournalJournal of Heuristics
Volume10
Issue number4
DOIs
StatePublished - Jul 1 2004

Keywords

  • Convergence
  • Meia-heuristics
  • Performance evaluation
  • Simulated annealing

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications
  • Control and Optimization
  • Management Science and Operations Research
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Analyzing the performance of generalized hill climbing algorithms'. Together they form a unique fingerprint.

  • Cite this