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 language | English (US) |
---|---|
Pages (from-to) | 343-354 |
Number of pages | 12 |
Journal | Methodology and Computing in Applied Probability |
Volume | 6 |
Issue number | 3 |
DOIs | |
State | Published - 2004 |
Keywords
- Generalized hill climbing algorithms
- Local search
- Markov chains
- Tabu search
ASJC Scopus subject areas
- Statistics and Probability
- General Mathematics