Tabu Search

Steepest descent search will arrive at a local optimum. To escape, we need to allow some “bad” (not improving) moves. Tabu search seeks to control which “bad” moves are allowable and which are not. To escape from a local optimum, we need to move out of its “basin of attraction”.

Associated with any local optimum is a set of points which if we run steepest descent starting from any of these points, it’ll end up in that local optimum. This set is called the basin of attraction. The search space is partitioned by basins of attraction. We need to allow sufficient “bad moves” to go from a local optimum to a neighbouring basin.

To try to get this to happen, Tabu Search allows reversing moves (at least for a while) in the hope that this will move the search further away. For a search space of binary strings with Hamming-1 neighbourhood, this means keeping a list of bits that have been flipped and making sure that we don’t flip them for a while. The amount of time that a move is banned is called the tabu tenure.

Algorithm #

1. Pick a random x ∈ X
2. Let tabu list = {}
3. Generate neighbourhood of x
4. Let y be the best neighbour that was not generated by a tabu move
5. Place the inverse of the operator that produced y on the tabu list
6. If any tabu operators have been on the tabu list more than the tabu tenure, remove them
7. x = y
8. Go to 3

Setting the tenure #

For binary strings of length n, the tenure should deb at least 1 and less than n. In practice, there is usually some optimal length which we find by trial and error.

Aspiration Criteria #

Sometimes good moves get disallowed because they are tabu. Several mechanisms have been proposed to allow them. These are called aspiration criteria. The most common aspiration criteria is to accept a tabu move if it is better than anything seen so far.

Structure of basins of attraction #

Tabu search should work quite well if local optima are near each other because there is a good chance of making the transition from one basin to another.
If they are apart, then random restarts should be better. Jean Paul Watson showed that the problems where tabu search works have local optima close to each other in “big valley” structure.