Tabu Search

Contents :	About Tabu Search
	Applications
	Tutorials
	References (bibtex format)
	Slides

About Tabu Search

Local search employs the idea that a given solution S may be improved by making small changes. Those solutions obtained by modifying solution S are called neighbors of S. The local search algorithm starts with some initial solution and moves from neighbor to neighbor as long as possible while decreasing the objective function value. The main problem with this strategy is to escape from local minima where the search cannot find any further neighborhood solution that decreases the objective function value. Different strategies have been proposed to solve this problem. One of the most efficient strategies is tabu search. Tabu search allows the search to explore solutions that do not decrease the objective function value only in those cases where these solutions are not forbidden. This is usually obtained by keeping track of the last solutions in term of the action used to transform one solution to the next. When an action is performed it is considered tabu for the next T iterations, where T is the tabu status length. A solution is forbidden if it is obtained by applying a tabu action to the current solution. The Tabu Search metaheuristic has been defined by Fred Glover (see Glover, F. “Future paths for integer programming and links to artificial intelligence”, Comp. Oper. Res., Vol. 13, pp. 533-549, 1986). The basic ideas of TS have also been sketched by P. Hansen (Hansen, P. “The steepest ascent mildest descent heuristic for combinatorial programming”, Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy, 1986).

Basic Tabu Search Algorithm

k := 1.
generate initial solution
WHILE the stopping condition is not met DO
    Identify N(s). (Neighbourhood set)
    Identify T(s,k). (Tabu set)
    Identify A(s,k). (Aspirant set)
    Choose the best s’ Î N(s,k) = {N(s) - T(s,k)}+A(s,k).
    Memorize s’ if it improves the previous best known solution
    s := s’.
    k := k+1.
END WHILE

Applications

There is a great variety of real-world problems that can be solved by Tabu Search. Representative areas include, but are not limited to:

Scheduling,
Quadratic assignment,
Frequency assignment,
Car pooling,
Capacitated p-median,
Resource constrained project scheduling (RCPSP),
Vehicle routing problems,
Graph coloring,
Retrieval Layout Problem,
Maximum Clique Problem,
Traveling Salesman Problems,
Database systems,
Nurse Rostering Problem,
Neural Nets,
Grammatical inference,
Knapsack problems,
SAT, Constraint Satisfaction Problems
Telecomunication Network,
Network design,
Global Optimization.

Tutorials
Glover, F., (1989): Tabu search - Part I, ORSA Journal on Computing 1, 190-206.
Glover, F., (1990): Tabu search - Part II, ORSA Journal on Computing 2, 4-32.
Glover, Taillard, Laguna, De Werra (eds.) (1993). Tabu search, Annals of Operations Research 41, Baltzer, Basel.
Glover and Laguna (1997). Tabu Search, Kluwer Academic Publishers.

Last update: June 8, 2001