Contenus

Toggle## Taboo research

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.

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

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 ← nullfor(sCandidate in sNeighbourhood)yew( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) ) bestCandidate ← sCandidateend ifend fors ← bestCandidateyew(fitness(bestCandidate) > fitness(sBest)) sBest ← bestCandidateend iftabuList.push(bestCandidate);yew(tabuList.size > maxTabuSize) tabuList.removeFirst()end if end whilereturn 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.