The Tabu search was proposed by Fred Glover in 1986 (of which you will find the diagrams in the course of the algorithm). The method uses a memory (or multiple memories) that is updated and exploited during the search.
At each iteration, the tabu algorithm chooses the best neighbor not in the tabu list, even if it degrades the cost function. For this reason, tabu research is said to be an aggressive method.
Tabu list
For some types of problem, banning an attribute can eliminate useful configurations to escape a local optimum. A mechanism, called the aspiration criterion, makes it possible to relax the ban under certain conditions. It is important to note that a bad aspiration criterion create a loop over a solution cycle.
Whether the choice of prohibition or the aspiration criterion, these two mechanisms must be adapted case by case to the problems encountered.
Algorithm
s ← s0 sBest ← s tabuList ← [] while (not stoppingCondition()) candidateList ← [] bestCandidate ← null for (sCandidate in sNeighborhood) if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) ) bestCandidate ← sCandidate end if end for s ← bestCandidate if (fitness(bestCandidate) > fitness(sBest)) sBest ← bestCandidate end if tabuList.push(bestCandidate); if (tabuList.size > maxTabuSize) tabuList.removeFirst() end if end while return sBes
Example
We will take the example of the travelling salesman problem (TSP). Taking a set of cities, we know the distance between all pairs of cities. The goal is to visit each city, one after the other until returning to the start city, while minimizing the total traveled distance.
The path is represented by a set of edges, vertices are cities. An initial configuration consists of choosing a Hamiltonian cycle (a cycle that passes once and only once by each vertex) arbitrary, as for example to take the next city in the list.
The neighborhood is built by movement. A move consists of removing two arcs for « crossing them ». For example the pair of arcs <(a, c), (e, b)> becomes <(a, e), (c, b)>. The Hamiltonian cycle is preserved. We then have « removed » arcs and « added » arcs.
In order not to repeat the same movement, we introduce two tabu lists: IN containing the deleted arcs (a,c) and (e,b); OUT containing the added arcs (a,e) and (c,b). At each iteration the forbidden movements are: to introduce an arc of IN and to withdraw an arc of OUT. Here the prohibition is infinite.