Tabu guided generalized hill climbing algorithms

Diane E. Vaughan, Sheldon Howard Jacobson

Research output: Contribution to journalReview article

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 - Dec 1 2004

Fingerprint

Hill Climbing
Search Strategy
Tabu Search
Iteration
Discrete Optimization
Stationary Distribution
Markov chain
NP-complete problem
Optimization Problem
Converge
Sufficient Conditions
Zero

Keywords

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

ASJC Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)

Cite this

Tabu guided generalized hill climbing algorithms. / Vaughan, Diane E.; Jacobson, Sheldon Howard.

In: Methodology and Computing in Applied Probability, Vol. 6, No. 3, 01.12.2004, p. 343-354.

Research output: Contribution to journalReview article

@article{fdb4f3745d884842b50e0808712edb50,
title = "Tabu guided generalized hill climbing algorithms",
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.",
keywords = "Generalized hill climbing algorithms, Local search, Markov chains, Tabu search",
author = "Vaughan, {Diane E.} and Jacobson, {Sheldon Howard}",
year = "2004",
month = "12",
day = "1",
doi = "10.1023/B:MCAP.0000026564.87435.66",
language = "English (US)",
volume = "6",
pages = "343--354",
journal = "Methodology and Computing in Applied Probability",
issn = "1387-5841",
publisher = "Springer Netherlands",
number = "3",

}

TY - JOUR

T1 - Tabu guided generalized hill climbing algorithms

AU - Vaughan, Diane E.

AU - Jacobson, Sheldon Howard

PY - 2004/12/1

Y1 - 2004/12/1

N2 - 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.

AB - 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.

KW - Generalized hill climbing algorithms

KW - Local search

KW - Markov chains

KW - Tabu search

UR - http://www.scopus.com/inward/record.url?scp=25844437116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=25844437116&partnerID=8YFLogxK

U2 - 10.1023/B:MCAP.0000026564.87435.66

DO - 10.1023/B:MCAP.0000026564.87435.66

M3 - Review article

AN - SCOPUS:25844437116

VL - 6

SP - 343

EP - 354

JO - Methodology and Computing in Applied Probability

JF - Methodology and Computing in Applied Probability

SN - 1387-5841

IS - 3

ER -