Tabu search

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.

The basic idea of the taboo list is to memorize the configurations or regions visited and introduce mechanisms to prohibit the search to return too quickly to these configurations. These mechanisms are temporary prohibitions of certain movements (tabu movements).
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

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

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

tabusearch

tabu

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.

tsp1

 

Publicités