📄 tabu search.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0043)http://www.cs.sandia.gov/opt/survey/ts.html -->
<HTML><HEAD><TITLE>Tabu Search</TITLE>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1"><LINK
rev=made href="mailto:wehart@cs.sandia.gov">
<META content="MSHTML 6.00.2900.3199" name=GENERATOR></HEAD>
<BODY bgColor=#ffffff>
<CENTER>
<H1>Tabu Search</H1></CENTER>
<HR>
<FONT color=#111aa0>
<H2>Overview</H2></FONT>The basic concept of Tabu Search as described by Glover
(1986) is "a meta-heuristic superimposed on another heuristic. The overall
approach is to avoid entrainment in cycles by forbidding or penalizing moves
which take the solution, in the next iteration, to points in the solution space
previously visited ( hence "tabu"). The Tabu search is fairly new, Glover
attributes it's origin to about 1977 (see Glover, 1977). The method is still
actively researched, and is continuing to evolve and improve. The Tabu method
was partly motivated by the observation that human behavior appears to operate
with a random element that leads to inconsistent behavior given similar
circumstances. As Glover points out, the resulting tendency to deviate from a
charted course, might be regretted as a source of error but can also prove to be
source of gain. The Tabu method operates in this way with the exception that new
courses are not chosen randomly. Instead the Tabu search proceeds according to
the supposition that there is no point in accepting a new (poor) solution unless
it is to avoid a path already investigated. This insures new regions of a
problems solution space will be investigated in with the goal of avoiding local
minima and ultimately finding the desired solution.
<P>The Tabu search begins by marching to a local minima. To avoid retracing the
steps used, the method records recent moves in one or more Tabu lists. The
original intent of the list was not to prevent a previous move from being
repeated, but rather to insure it was not reversed. The Tabu lists are
historical in nature and form the Tabu search memory. The role of the memory can
change as the algorithm proceeds. At initialization the goal is make a coarse
examination of the solution space, known as 'diversification', but as candidate
locations are identified the search is more focused to produce local optimal
solutions in a process of 'intensification'. In many cases the differences
between the various implementations of the Tabu method have to do with the size,
variability, and adaptability of the Tabu memory to a particular problem domain.
<FONT color=#111aa0>
<H2>Application Domain</H2></FONT>The Tabu search has traditionally been used on
combinatorial optimization problems. The technique is straightforwardly applied
to continuous functions by choosing a discrete encoding of the problem. Many of
the applications in the literature involve integer programming problems,
scheduling, routing, traveling salesman and related problems. <FONT
color=#111aa0>
<H2>Software</H2></FONT><A title="Reactive Tabu Search"
href="http://www.cacr.caltech.edu/~battiti/archive/code/rts_qap/README.html"><EM>Reactive
Tabu Search</EM></A> R. Battiti, C source for Reactive Tabu Search
<P><A href="http://www.cs.sandia.gov/opt/survey/demos.html"><FONT
size=+1>Demo</FONT></A> <FONT color=#111aa0>
<H2>References</H2></FONT>R. Battiti, "Reactive search: Toward self-tuning
heuristics", In V. J. Rayward-Smith, editor, <EM>Modern Heuristic Search
Methods</EM>, chapter 4, pages 61--83. John Wiley and Sons Ltd, 1996. <BR><BR>R.
Battiti and G. Tecchiolli, "Simulated annealing and tabu search in the long run:
a comparison on qap tasks", <EM>Computer Math. Applic.</EM>, 28(6):1--8, 1994.
<BR><BR>A M. Dell'Amico , A M. Trubian, "Applying Tabu Search to the Job-shop
Scheduling Problem", <EM>J Annals of Ops. Res.</EM>, 41, 1993 <BR><BR>Glover
F.," Future paths for Integer Programming and Links to Artificial Intelligence",
<EM>Computers and Operations Research</EM>, 5:533-549, 1986. <BR><BR>Glover F.,
"Tabu Search: A Tutorial", <EM>Interfaces</EM>, 20(4):74-94,1990.
<BR><BR>Glover, F. and D. de Werra,<A title="Tabu Search"
href="http://www.baltzer.nl/anor/anor41.html"><EM>Tabu Search</EM></A>, Baltzer
Science Publishers, 199 <BR><BR>Glover F., and Laguna M., Tabu Search, in
<EM>Modern Heuristic Techniques for Combinatorial Problems</EM>, C.R. Reeves,
editor, John Wiley & Sons, Inc, 1993 <BR><BR>A Hertz, "Finding a Feasible
Course Schedule Using Tabu Search", <EM>Discrete Applied Mathematics and
Combinatorial Operations Research and Computer Science</EM>, 35, 1992 <BR><BR>A
M. Laguna, A J. W. Barnes, A F. Glover, "Tabu Search Methodology for a Single
Machine Scheduling Problem", <EM>J. of Int. Manufacturing</EM>, 2, 63-74, 1991
<BR><BR>A M. Laguna, A J. L. Gonzalez-Velarde, "A Search Heuristic for
Just-in-time Scheduling in Parallel Machines", <EM>J. of Int. Manu.</EM>, 2,
253-260, 1991 <BR><BR>A S. C. S. Porto, A C.C. Ribeiro , "Parallel Tabu Search
Message-Passing Synchronous Strategies for Task Scheduling under Precedence
Constraints", <EM>Journal of Heuristics</EM>, V 1, 1995 <BR><BR>A S. C. S.
Porto, A C.C. Ribeiro, "A Tabu Search Approach to Task Scheduling on
Heterogeneous Processors under Precedence Constraints", <EM>International
Journal of High-Speed Computing</EM>, 7(2), 1995 <BR><BR>A M. Widmer, "The
Job-shop Scheduling with Tooling Constraints: A Tabu Search Approach", <EM>J.
Opt. Res. S</EM>, 42, 75-82, 1991 <BR><BR>A M. Widmer, A A. Hertz, "A New
Heuristic Method for the Flow Shop Sequencing Problem", <EM>Euro. J. Opt.
Res.</EM>, 41, 186-193, 1989 <BR><BR><FONT color=#111aa0>
<H2>Miscellaneous Links</H2></FONT><A title="Reactive Tabu Search"
href="http://www.cacr.caltech.edu/~battiti/reactive.html"><EM>Reactive Tabu
Search</EM></A> R. Battiti, Reactive Tabu Search papers
<P>
<HR>
<ADDRESS><A href="http://www.cs.sandia.gov/opt/survey/main.html">Global
Optimization Survey - Main Page</A><BR><A href="http://www.sandia.gov/">Sandia
National Laboratories</A><BR><BR>This page maintained by <A
href="mailto:wehart@cs.sandia.gov">wehart@cs.sandia.gov</A> </ADDRESS>Last
modified: March 10, 1997 </BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -