TY - JOUR
T1 - Tabu guided generalized hill climbing algorithms
AU - Vaughan, Diane E.
AU - Jacobson, Sheldon H.
N1 - Funding Information:
This work is s upported in part by the Air Force Office of Scientific Res earch (FA9550-04-1-0110, F49620-01-1-0007, F49620-98-1-0111, F49620-98-1-0432). The authors would also like to thank an anonymous referee for comments and suggestions that have resulted in a significantly improved manuscript.
PY - 2004
Y1 - 2004
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
SN - 1387-5841
VL - 6
SP - 343
EP - 354
JO - Methodology and Computing in Applied Probability
JF - Methodology and Computing in Applied Probability
IS - 3
ER -