Tabu guided generalized hill climbing algorithms

Diane E. Vaughan, Sheldon H. Jacobson

Research output: Contribution to journalReview articlepeer-review

Abstract

This paper formulates tabu search strategies that guide generalized hill climbing (GHC) algorithms for addressing NP-hard discrete optimization problems. The resulting framework, termed tabu guided generalized hill climbing (TG 2HC) algorithms, uses a tabu release parameter that probabilistically accepts solutions currently on the tabu list. TG 2HC algorithms are modeled as a set of stationary Markov chains, where the tabu list is fixed for each outer loop iteration. This framework provides practitioners with guidelines for developing tabu search strategies to use in conjunction with GHC algorithms that preserve some of the algorithms' known performance properties. In particular, sufficient conditions are obtained that indicate how to design iterations of problemspecific tabu search strategies, where the stationary distributions associated with each of these iterations converge to the distribution with zero weight on all non-optimal solutions.

Original languageEnglish (US)
Pages (from-to)343-354
Number of pages12
JournalMethodology and Computing in Applied Probability
Volume6
Issue number3
DOIs
StatePublished - 2004

Keywords

  • Generalized hill climbing algorithms
  • Local search
  • Markov chains
  • Tabu search

ASJC Scopus subject areas

  • Statistics and Probability
  • General Mathematics

Fingerprint

Dive into the research topics of 'Tabu guided generalized hill climbing algorithms'. Together they form a unique fingerprint.

Cite this