Analyzing the performance of local search algorithms using generalized hill climbing algorithms

Research output: Contribution to journalArticlepeer-review

Abstract

Generalized hill climbing algorithms provide a well-defined framework to model how local search algorithms address intractable discrete optimization problems. Monte Carlo search, simulated annealing, threshold accepting, and tabu search, among others, can all be formulated as particular generalized hill climbing algorithms. Moreover, generalized hill climbing algorithms provide a structure for classifying and studying a large body of stochastic and deterministic local search algorithms. In particular, the generalized hill climbing algorithm framework can be used to develop a general Markov chain model for the application of local search algorithms to intractable discrete optimization problems. Moreover, the generalized hill climbing algorithm framework has been used to evaluate the finite-time performance of local search algorithms. This analysis is of particular interest to practitioners for whom traditional convergence results are often of limited interest and value. This paper presents a survey of recent results on how the generalized hill climbing algorithm framework has been used to model and gain insight into the performance of local search algorithms. Many of these results provide tools for comparing and evaluating different types of local search algorithms using common performance measures.

Original languageEnglish (US)
Pages (from-to)441-467
Number of pages27
JournalOperations Research/ Computer Science Interfaces Series
Volume15
DOIs
StatePublished - Dec 1 2002

ASJC Scopus subject areas

  • Computer Science(all)
  • Management Science and Operations Research

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

Cite this