Tabu Search

edited by Monaldo Mastrolilli, IDSIA

Contents

• About Tabu Search
• Readings
• Links

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

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'
  ENDIF
  k := k+1.
END WHILE

Readings

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.

Further references (bibtex format)

Links

• TS web
• Slides