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.
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
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.