edited by Monaldo Mastrolilli, IDSIA
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
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,
|Basic Tabu Search
k := 1.
s := GenerateInitialSolution()
s* := s;
WHILE the termination criteria not met DO
Identify N(s). (Neighbourhood set)
Identify T(s,k). (Tabu set)
Identify A(s,k). (Aspirant set)
Choose best s' from N(s,k) = N(s)-T(s,k)+A(s,k).
s := s'
IF f(s') < f(s*) THEN
s* := s'
k := k+1.
Glover, F., (1989): Tabu search - Part I, ORSA Journal on Computing 1,
Glover, F., (1990): Tabu search - Part II, ORSA Journal on Computing
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.
Further references (bibtex format)