Tabu search

Author

Enrico Schumann

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.

(1)
\begin{eqnarray} &&{\scriptscriptstyle 1:\quad} \mbox{generate current solution } x^{\mathrm{c}} \mathrm{\ and\ initialise\ tabu\ list\ } T=\emptyset\\[-0.5ex] &&{\scriptscriptstyle 2:\quad} \mathbf{while} \mbox{ stopping criteria not met } \mathbf{do}\nonumber \\[-0.5ex] &&{\scriptscriptstyle 3:\quad} \quad \mbox{compute } V = \{x | x \in \mathcal{N}(x^{\mathrm{c}})\} \backslash T\\[-0.5ex] &&{\scriptscriptstyle 4:\quad} \quad \mbox{select } x^{\mathrm{n}} = \min (V)\\[-0.5ex] &&{\scriptscriptstyle 5:\quad} \quad x^{\mathrm{c}} = x^{\mathrm{n}} \mbox{ and } T = T\cup x^{\mathrm{n}}\\[-0.5ex] &&{\scriptscriptstyle 6:\quad} \quad \mbox{update memory}\\[-0.5ex] &&{\scriptscriptstyle 7:\quad} \mathbf{end\ while}\\[-0.5ex] \end{eqnarray}

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License