32.5 Tabu search¶
Part 4 · Heuristic algorithms · Chapter 32 · Chapter 32: Metaheuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Metaheuristics · App: TSP: simulated annealing and tabu search
Tabu search (denoted by \(TS\)) explores the neighbourhood of the current solution completely and moves to the best neighbour, even if it is worse than the current solution. To avoid going back to the solutions just visited, it keeps a short-term memory, the tabu list: the moves that would undo the recent moves are forbidden (tabu) for a number of iterations, the tenure, unless they lead to a solution better than the best one found (aspiration criterion).
- The pseudo-code of \(TS\) for \(P\,||\,C_{\max}\), with the move neighbourhood and the lexicographic comparison of Section 32.2.1, reads as follows; the attribute \((j,h)\) forbids moving job \(j\) back to machine \(h\).
Algorithm: Tabu search for \(P\,||\,C_{\max}\)
-
Tabu search was proposed by Glover (1986); the reference book is Glover and Laguna, Tabu Search, Kluwer, 1997. Unlike \(SA\), it is deterministic: it escapes from a local optimum because it always moves, to the least bad neighbour if no neighbour is better.
-
Without memory, this rule would cycle: from a local optimum \(S\) the search moves to the best neighbour \(S'\), which is worse, and from \(S'\) the best neighbour is typically \(S\) again. The tabu list breaks the cycle by forbidding the reverse move.
-
Attributes. Storing the visited solutions and comparing every neighbour with them would be too expensive. The tabu list stores attributes of the recent moves instead: here the pair \((j,h)\) “job \(j\) has left machine \(h\)”; for the TSP, the edges just removed from the tour.
-
An attribute forbids more than the single solution just left: every solution with job \(j\) on machine \(h\) is tabu, even the ones never visited. The aspiration criterion repairs this excess of caution: a tabu move is allowed if it leads to a solution better than the best one found, which certainly has not been visited.
-
Tenure. If it is too short, the search can still cycle through longer cycles; if it is too long, too many moves are forbidden and the search is driven far from the good regions. Typical values are between \(5\) and \(20\), or proportional to \(\sqrt{n}\); drawing the tenure at random in an interval at every iteration (robust tabu search, Taillard 1991) makes cycles unlikely.
-
Stopping rule. A maximum number of iterations, or of iterations without improvement of the best solution. For \(P\,||\,C_{\max}\) we can also stop when the makespan reaches the lower bound \(\LB\): then the solution is optimal, and the search can only waste time.
-
Long-term memory. Besides the tabu list (short-term memory), \(TS\) can record how often each attribute appears in the visited solutions. Diversification penalizes the frequent attributes, to push the search toward unexplored regions; intensification restarts from the best solutions found, and fixes the attributes they share.
32.5.1 Example¶
Example 32.5: \(TS\) on the \(P\,||\,C_{\max}\) reference instance
We start from the solution computed by LPT in the chapter «Constructive heuristics», \(J_1=\{1,5,7\}\), \(J_2=\{2,6\}\), \(J_3=\{3,4\}\), with loads \((11,8,8)\), \(C_{\max}=11\) and \(\sum_h L_h^2=249\). It is a local optimum for the move neighbourhood: at the first iteration the \(14\) neighbours are
| move | \(1\to M_2\) | \(1\to M_3\) | \(2\to M_1\) | \(2\to M_3\) | \(3\to M_1\) | \(3\to M_2\) | \(4\to M_1\) |
|---|---|---|---|---|---|---|---|
| \((C_{\max},\sum_hL_h^2)\) | \((13,269)\) | \((13,269)\) | \((16,329)\) | \((13,299)\) | \((15,305)\) | \((12,281)\) | \((15,305)\) |
| move | \(4\to M_2\) | \(5\to M_2\) | \(5\to M_3\) | \(6\to M_1\) | \(6\to M_3\) | \(7\to M_2\) | \(7\to M_3\) |
| \((C_{\max},\sum_hL_h^2)\) | \((12,281)\) | \((11,249)\) | \((11,249)\) | \((14,285)\) | \((11,267)\) | \((11,249)\) | \((11,249)\) |
No neighbour has \(C_{\max}<11\), and the four best ones have \(C_{\max}=11\) and \(\sum_hL_h^2=249\), as the current solution: a local search stops here. \(TS\), with \(tenure=6\), moves instead to the best non-tabu neighbour (the first of the four, job \(5\) to \(M_2\)), and continues:
| it | move | loads | \(C_{\max}\) | \(\sum_h L_h^2\) | \(bestC\) | new tabu attribute |
|---|---|---|---|---|---|---|
| \(1\) | job \(5\): \(M_1\to M_2\) | \((8,11,8)\) | \(11\) | \(249\) | \(11\) | \((5,M_1)\) until it. \(7\) |
| \(2\) | job \(5\): \(M_2\to M_3\) | \((8,8,11)\) | \(11\) | \(249\) | \(11\) | \((5,M_2)\) until it. \(8\) |
| \(3\) | job \(6\): \(M_2\to M_1\) | \((11,5,11)\) | \(11\) | \(267\) | \(11\) | \((6,M_2)\) until it. \(9\) |
| \(4\) | job \(7\): \(M_1\to M_2\) | \((8,8,11)\) | \(11\) | \(249\) | \(11\) | \((7,M_1)\) until it. \(10\) |
| \(5\) | job \(3\): \(M_3\to M_1\) | \((12,8,7)\) | \(12\) | \(257\) | \(11\) | \((3,M_3)\) until it. \(11\) |
| \(6\) | job \(6\): \(M_1\to M_3\) | \((9,8,10)\) | \(10\) | \(245\) | \(10\) | \((6,M_1)\) until it. \(12\) |
| \(7\) | job \(4\): \(M_3\to M_2\) | \((9,12,6)\) | \(12\) | \(261\) | \(10\) | \((4,M_3)\) until it. \(13\) |
| \(8\) | job \(7\): \(M_2\to M_3\) | \((9,9,9)\) | \(9\) | \(243\) | \(9\) | \((7,M_2)\) until it. \(14\) |
-
At iteration \(2\) the best neighbour would move job \(5\) back to \(M_1\), returning to the starting solution: the move is tabu (attribute \((5,M_1)\) until iteration \(7\)), and the search moves job \(5\) to \(M_3\).
-
At iteration \(5\) the four neighbours with \(C_{\max}=11\) are all tabu, and none satisfies the aspiration criterion (\(C_{\max}<bestC=11\)): the best non-tabu move worsens the makespan to \(12\). This is how \(TS\) leaves the plateau.
-
At iteration \(6\) the makespan drops to \(10\), and at iteration \(8\) to \(9\): \(C_{\max}=\LB=9\), so the solution \(J_1=\{1,3\}\), \(J_2=\{2,4\}\), \(J_3=\{5,6,7\}\) is optimal and the search stops: \(TS(I)=9=z(I)\).
-
The figure shows the Gantt charts of the starting solution, of the solution after the worsening move of iteration \(5\) (the moved job in orange), and of the optimal solution reached at iteration \(8\).
-
With \(tenure\le 5\), \(TS\) does not reach the optimum on this instance within \(50\) iterations: the tabu list is too short to prevent the search from going back to the plateau of makespan \(11\).
32.5.2 Tabu search for the TSP, and the effect of the tenure¶
-
For the TSP with the 2-opt neighbourhood, the natural attributes are the edges: when a move removes the edges \((\sigma_i,\sigma_{i+1})\) and \((\sigma_j,\sigma_{j+1})\), these two edges may not be added back to the tour for \(tenure\) iterations, unless the move gives a tour shorter than the best one. Everything else is as in the pseudo-code of Section 32.5: at every iteration all the \(\frac{n(n-3)}{2}\) moves are evaluated in \(O(1)\) each, and the best non-tabu one is performed.
-
The tables report the result of \(TS\) on the medium instances, from the nearest neighbour tour (\(326\)) for TSP20 with \(200\) iterations, and from the LPT solution (\(73\)) for PCM15 with \(300\) iterations, for several values of the tenure; for PCM15 the table also gives the number of iterations performed (\(300\) unless the lower bound is reached).
| TSP20: \(TS\) with 2-opt, \(200\) iterations (\(z(I)=291\)) | ||||||
|---|---|---|---|---|---|---|
| \(tenure\) | \(0\) | \(1\) | \(2\) | \(5\) | \(10\) | \(20\) |
| best length | \(319\) | \(291\) | \(291\) | \(291\) | \(291\) | \(291\) |
| PCM15: \(TS\) with the move neighbourhood, at most \(300\) iterations (\(z(I)=69\)) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| \(tenure\) | \(0\) | \(1\) | \(2\) | \(3\) | \(5\) | \(7\) | \(10\) | \(15\) | \(20\) | \(30\) |
| best \(C_{\max}\) | \(73\) | \(73\) | \(73\) | \(73\) | \(73\) | \(72\) | \(71\) | \(69\) | \(70\) | \(70\) |
| iterations | \(300\) | \(300\) | \(300\) | \(300\) | \(300\) | \(300\) | \(300\) | \(231\) | \(300\) | \(300\) |
- With \(tenure=0\) there is no memory, and \(TS\) cycles: on TSP20 it never leaves the first 2-opt local optimum. On PCM15 the move neighbourhood has a large plateau, and \(TS\) needs a long tabu list to cross it; but a tabu list that is too long forbids too much, and with \(tenure\ge 20\) the optimum is lost again. The tenure must be tuned, and its best value depends on the problem and on the instance.