# Tabu Search

## Overview

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

Global Optimization Survey - Main Page

Sandia National Laboratories

This page maintained by wehart@cs.sandia.gov
Last modified: March 10, 1997