Global optimization performance measures for generalized hill climbing algorithms

Sheldon H. Jacobson, Enver Yücesan

Research output: Contribution to journalArticlepeer-review


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
Issue number2
StatePublished - Jun 2004


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

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics
  • Business, Management and Accounting (miscellaneous)
  • Computer Science Applications
  • Management Science and Operations Research


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

Cite this