Tabu Guided Generalized Hill Climbing Algorithms

Diane E. Vaughan () and Sheldon H. Jacobson ()
Additional contact information
Diane E. Vaughan: Los Alamos National Laboratory
Sheldon H. Jacobson: University of Illinois

Methodology and Computing in Applied Probability, 2004, vol. 6, issue 3, 343-354

Abstract: 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 (TG2HC) algorithms, uses a tabu release parameter that probabilistically accepts solutions currently on the tabu list. TG2HC 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 problem-specific 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.

Keywords: tabu search; local search; generalized hill climbing algorithms; Markov chains (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/B:MCAP.0000026564.87435.66 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:6:y:2004:i:3:d:10.1023_b:mcap.0000026564.87435.66

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1023/B:MCAP.0000026564.87435.66

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().