Tabu search

Enrico Schumann

Tabu search

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