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.
Application Domain
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.
Software
Reactive Tabu Search R. Battiti, C source for Reactive Tabu Search
Demo
References
R. Battiti, "Reactive search: Toward self-tuning heuristics",
In V. J. Rayward-Smith, editor, Modern Heuristic Search Methods, chapter
4, pages 61--83. John Wiley and
Sons Ltd, 1996.
R. Battiti and G. Tecchiolli, "Simulated annealing and tabu search in the long
run: a comparison on qap tasks",
Computer Math. Applic., 28(6):1--8, 1994.
A M. Dell'Amico , A M. Trubian, "Applying Tabu Search to the Job-shop Scheduling
Problem",
J Annals of Ops. Res., 41, 1993
Glover F.," Future paths for Integer Programming and Links to Artificial
Intelligence",
Computers and Operations Research, 5:533-549, 1986.
Glover F., "Tabu Search: A Tutorial", Interfaces, 20(4):74-94,1990.
Glover, F. and D. de Werra,Tabu Search, Baltzer Science Publishers, 199
Glover F., and Laguna M., Tabu Search, in Modern Heuristic Techniques for
Combinatorial Problems, C.R. Reeves, editor, John Wiley & Sons, Inc, 1993
A Hertz, "Finding a Feasible Course Schedule Using Tabu Search", Discrete Applied
Mathematics
and Combinatorial Operations Research and Computer Science, 35, 1992
A M. Laguna, A J. W. Barnes, A F. Glover, "Tabu Search Methodology for a Single
Machine
Scheduling Problem", J. of Int. Manufacturing, 2, 63-74, 1991
A M. Laguna, A J. L. Gonzalez-Velarde, "A Search Heuristic for Just-in-time
Scheduling in
Parallel Machines", J. of Int. Manu., 2, 253-260, 1991
A S. C. S. Porto, A C.C. Ribeiro , "Parallel Tabu Search Message-Passing
Synchronous
Strategies for Task Scheduling under Precedence Constraints", Journal of
Heuristics, V 1, 1995
A S. C. S. Porto, A C.C. Ribeiro, "A Tabu Search Approach to Task Scheduling on
Heterogeneous Processors under Precedence Constraints", International Journal of
High-Speed Computing,
7(2), 1995
A M. Widmer, "The Job-shop Scheduling with Tooling Constraints: A Tabu Search
Approach", J. Opt. Res. S,
42, 75-82, 1991
A M. Widmer, A A. Hertz, "A New Heuristic Method for the Flow Shop Sequencing
Problem", Euro. J. Opt. Res.,
41, 186-193, 1989
Miscellaneous Links
Reactive Tabu Search R. Battiti, Reactive Tabu Search papers