Article: Linking Search Space Structure, Run-Time Dynamics, and Problem Difficulty: A Step Toward Demystifying Tabu Search
jai...@ptolemy.arc.nasa.gov
Watson, J.P., Whitley, L.D. and Howe, A.E. (2005)
"Linking Search Space Structure, Run-Time Dynamics, and Problem Difficulty: A Step Toward Demystifying Tabu Search",
Volume 24, pages 221-261.
For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/watson05a.html
Abstract:
Tabu search is one of the most effective heuristics for locating
high-quality solutions to a diverse array of NP-hard combinatorial
optimization problems. Despite the widespread success of tabu search,
researchers have a poor understanding of many key theoretical aspects
of this algorithm, including models of the high-level run-time dynamics
and identification of those search space features that influence problem
difficulty. We consider these questions in the context of the job-shop
scheduling problem (JSP), a domain where tabu search algorithms have
been shown to be remarkably effective. Previously, we demonstrated
that the mean distance between random local optima and the nearest
optimal solution is highly correlated with problem difficulty for a
well-known tabu search algorithm for the JSP introduced by Taillard.
In this paper, we discuss various shortcomings of this measure and
develop a new model of problem difficulty that corrects these
deficiencies. We show that Taillard's algorithm can be modeled
with high fidelity as a simple variant of a straightforward random
walk. The random walk model accounts for nearly all of the variability
in the cost required to locate both optimal and sub-optimal solutions
to random JSPs, and provides an explanation for differences in the
difficulty of random versus structured JSPs. Finally, we discuss and
empirically substantiate two novel predictions regarding tabu search
algorithm behavior. First, the method for constructing the initial solution is
highly unlikely to impact the performance of tabu search. Second, tabu
tenure should be selected to be as small as possible while simultaneously
avoiding search stagnation; values larger than necessary lead to
significant degradations in performance.
The article is available via:
-- comp.ai.jair.papers (also see comp.ai.jair.announce)
-- World Wide Web: The URL for our World Wide Web server is
http://www.jair.org/
For direct access to this article and related files try:
http://www.jair.org/abstracts/watson05a.html
-- Anonymous FTP from Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume24/watson05a.ps
The compressed PostScript file is named watson05a.ps.Z
For more information about JAIR, visit our WWW or FTP sites, or
contact jai...@isi.edu
--
Steven Minton
JAIR Managing Editor