Author
Keywords
Tabu search
Review Status
Unreviewed
The algorithm
Most heuristics differ from classical methods by introducing an element of chance (e.g., by randomly picking neighbour solutions). Tabu Search (TS), at least in its standard form, is an exception as it is deterministic for a given starting value. (There exist, however, variants which include random elements.) TS is described in Glover [1] and detailed in the Algorithm below. TS was designed for discrete search spaces; its strategy to overcome local minima is to keep a ‘memory’ of recently visited solutions. These are forbidden (‘tabu’) as long as they stay in the algorithm's memory. Thus, a TS can manage to walk away from a local minimum as it is temporarily not allowed to revisit this solution.
Remarks
As can be seen in line 4 of the pseudocode, TS searches its neighbourhood ‘greedily’ for the best solution. Thus, given an initial solution, TS is not a stochastic method. If the neighbourhood is very large, though, finding the best neighbour may be very time consuming. Hence, at this point, other selection procedures (e.g., choosing the best solution only from a randomly chosen subset of neighbours), may be implemented.
Internal Links
Concepts 
Tutorials 
Tips 
Related Articles 
External links
References 
1. Glover, F.W. and M. Laguna (1997). Tabu search. Kluwer.

Weblinks 