Taboo search

Contents

Taboo research

Taboo research was proposed by Fred Glover in 1986 (the schematics of which you will find in the unfolding of the algorithm). The method uses a memory (or several memories) which is updated and exploited during the search.

The basic idea of the taboo list is to memorize the configurations or regions visited and to introduce mechanisms to prevent research from returning too quickly to these configurations. These mechanisms are temporary bans on certain movements (taboo movements).
TO each iteration, the taboo algorithm chooses the best non-taboo neighbor, even if this degrades the cost function. For this reason, taboo research is said to be an aggressive method.

Taboo list

The tabu list contains forbidden attributes or movements. The latter are taboo during a determined number of iterations of the algorithm (infinite or finite). Once the taboo period is over, the attribute or movement is again available in the local search. This list is a diversification strategy.

For some types of problem, disallowing an attribute can eliminate useful configurations for escaping a local optimum. A mechanism, called the aspiration criterion, allows the prohibition to be relaxed under certain conditions. It is important to note that a bad aspiration criterion to make loop the algorithm on a cycle of solutions.

Whether it is the choice of prohibition or the aspiration criterion, these two mechanisms must be adapted on a case-by-case basis in relation to the problems encountered.

Algorithm flow

 s ← s0
sBest ← s
tabuList ← []
while (not stoppingCondition())
   candidateList ← []
   bestCandidate ← null
   for (sCandidate in sNeighbourhood)
      yew ( (not tabuList.contains(sCandidate)) 
      and (fitness(sCandidate) > fitness(bestCandidate)) )
         bestCandidate ← sCandidate
      end if
   end for
   s ← bestCandidate
   yew (fitness(bestCandidate) > fitness(sBest))
      sBest ← bestCandidate
   end if
   tabuList.push(bestCandidate);
   yew (tabuList.size > maxTabuSize)
      tabuList.removeFirst()
   end if
end while
return sBes

Application example

We will take the example of the traveling salesman (TSP). Given a set of cities, we know the distance between all pairs of cities. The objective is to visit each city, one after the other until returning to the first city, while minimizing the total distance traveled.

The route is represented by a set of arcs, the vertices being the towns. An initial configuration consists of choosing a cycle Hamiltonian (a cycle that passes once and only once by each vertex) arbitrary, such as taking the next city in the list.

The neighborhood is built by movement. One movement consists of removing two arcs to "cross" them. For example the pair of arcs <(a, c), (e, b)> bECOMES <(a, e), (c, b)>. Thus the Hamiltonian cycle is preserved. We then have "removed" arcs and "added" arcs.

In order not to repeat the same movement, we introduce two taboo lists: IN containing deleted arcs (a, c) and (e, b); OUT containing the added arcs (a, e) and (c, b). TO each iteration the prohibited movements are: introduce an arc of IN and remove a bow from OUT. Here the prohibition is infinite.