Global optimization performance measures for generalized hill climbing algorithms

Sheldon H. Jacobson, Enver Yücesan

Research output: Contribution to journalArticlepeer-review

Abstract

Generalized hill climbing algorithms provide a framework for modeling several local search algorithms for hard discrete optimization problems. This paper introduces and analyzes generalized hill climbing algorithm performance measures that reflect how effectively an algorithm has performed to date in visiting a global optimum and how effectively an algorithm may perform in the future in visiting such a solution. These measures are also used to obtain a necessary asymptotic convergence (in probability) condition to a global optimum, which is then used to show that a common formulation of threshold accepting does not converge. These measures assume particularly simple forms when applied to specific search strategies such as Monte Carlo search and threshold accepting.

Original languageEnglish (US)
Pages (from-to)173-190
Number of pages18
JournalJournal of Global Optimization
Volume29
Issue number2
DOIs
StatePublished - Jun 1 2004

Keywords

  • Convergence
  • Finite-time performance
  • Hill climbing
  • Local search algorithms

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

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

Cite this