Taboo research

Contents

Taboo research was proposed by Fred Glover in 1986 (the diagrams of which you will find in the flow 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 certain types of problem, the prohibition of an attribute can eliminate useful configurations to escape a local optimum. A mechanism, called the aspiration criterion, allows the ban to be relaxed under certain conditions. It is important to note that a bad criterion of aspiration 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.

Sequence of the algorithm

 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

Example of application

We will take the example of the commercial traveler (TSP). Consider 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 course 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 endless.