Tabu Search

Introduction

Tabu search introduced by Glover [1] extends the local search with a list of already visited states. Returning to these states is forbidden for a certain number of iterations known as tabu tenure. This gives the algorithm exploration ability: after reaching a local optimum it is forced to move out of it.

Although the tabu list can in principle explicitly store already visited solutions, it is usually implemented as a list or an array of forbidden elements along with the corresponding tenures. When performing a move, the elements affected by that move are first added to the tabu list.

It may be desirable to select a move that leads to a very good but forbidden solution. The conditions under which such exceptions are allowed are known as the aspiration criterion. A generally used criterion allows a forbidden move if the resulting solution is better than the best one found so far.

Like the best improvement local search, tabu search evaluates all moves at each iteration and therefore can scale poorly with problem size.

The impact of tenure

The tenure plays a role similar to the temperature in the simulated annealing algorithm, controlling the scale of the search, or the exploration-exploitation tradeoff. Higher values result in broader search at the expense of average solution quality.

Using a constant value for the tenure is not recommended, as it can lead to the search being caught in a cycle, returning to the same solutions again and again as the tenure expires. This issue can be resolved by using a randomized tenure. Geometric distribution is a natural choice since by maximum entropy principle it is the most "random" distribution on the [1, +∞) interval among all the distributions with the same mean.

The geometric distribution has another unique property that allows to reformulate the tabu search as a memoryless process - paradoxal considering that it relies on memory of previous states. Instead of storing the tenures, we can instead store binary flags (tabu or not) that have a fixed chance of decaying into the non-tabu state. Just like with radioactive decay, this mechanism gives rise to exponentially distributed lifetimes. Had the decay chance instead increased with time according to a power law, we'd have a Weibull distribution

Like the simulated annealing, tabu search benefits from a "cooling" schedule - a gradual decrease of the mean tenure. In my tests on the travelling salesman problem, such schedule outperformed the optimal tenure with a fixed mean. Among the tested schedules, quadratic one (T = (t √T₁ + (1 - t) √T₀)²) worked best. The linear one spent too much time at high tenure values, and the exponential one at low values.

A decreasing tenure is also recommended because it is easier to select a decent tenure range than to select a single optimal value, although the process still requires some experimentation. The initial tenure should produce scores close to random local optima on average. The final tenure should be set to the lowest value that still results in nontrivial dynamics (score is not a flat line). I recommend making a test run with conservative initial guesses and then selecting the final values based on the score plot.

In general, efficient schedules can be obtained via the constant thermodynamic speed condition employed in simulated annealing. Even though the thermodynamics is not directly applicable, the condition in its general form is still adequate. The following model was found to fit the TSP data well:
σ(T) = c T^p
E(T) = a + b T^q,
where T is the mean tenure, E is the mean score, σ is the score standard deviation.

The constant thermodynamic speed condition is equivalent to (δE / δt) / σ = const, or T' = α T^{1 - q + p}, which yields a schedule T = (t T1^r + (1 - t) T0^r)^{1 / r}, r = q - p.

Cooperative tabu search

Ascension features an original population-based tabu search variant called cooperative tabu search. The idea is to have multiple search processes with fixed mean tenures running in parallel and sharing good solutions. It can be considered a dual of the regular tabu search with mean tenure varying across the population instead of decreasing with time (normalized time is replaced by normalized individual index). When an individual discovers a new personal best solution, it shares it with its lower tenure neighbour for further refinement. The neighbour then decides whether to accept the shared solution depending on its own personal best and current score. If the solution is accepted, it may become a new personal best, again leading to sharing. Possible acceptance criteria are:

Accept if the shared solution is better than personal best
Accept if the shared solution is better than the current one
Accept unconditionally

The last two options seem to have the best performance.

Cooperative tabu search has several advantages:

It is an anytime algorithm
Naturally lends itself to a parallel implementation
May better scale with the number of iterations

The advantages come at the expense of an extra parameter, population size. During the tests on the travelling salesman problem, the optimal values were in the [6 .. 9] range.

References

Fred Glover, Manuel Laguna. Tabu Search. Kluwer Academic Publishers, 1997.

API

Data types

TMove
TMoveUndo
TTabuList

Routines

// Make a MoveList for Solution for use in Tabu Search
procedure MakeTSMoveList(
   var   MoveList :  TMoveList;
   const Solution :  TSolution);
   
// Apply a Move to the Solution
procedure PerformMove(
   var   Solution :  TSolution;
   const Move     :  TMove);
         overload;
		 
// Apply a Move to the Solution, save Undo
procedure PerformMove(
   var   Solution :  TSolution;
   var   Undo     :  TMoveUndo;
   const Move     :  TMove);
         overload;
		 
// Undo the last move applied to the Solution
procedure UndoMove(
   var   Solution :  TSolution;
   const Undo     :  TMoveUndo);

// Copy the tabu list from ListFrom to ListTo
procedure AssignTabuList(
   var   ListTo   :  TTabuList;
   const ListFrom :  TTabuList);
   
// Initialize the TabuList
procedure InitTabuList(
   var   TabuList :  TTabuList);
   
// Decrease the tenures in TabuList by 1
procedure AgeTabuList(
   var   TabuList :  TTabuList);
   
// Add a Move that will be applied to Sol to the TabuList with Tenure
procedure AddToTabuList(
   var   TabuList :  TTabuList;
   const Move     :  TMove;
         Tenure   :  Integer;
   const Sol      :  TSolution);
   
// Return whether a Move is in the Solution's TabuList
function IsMoveTabu(
   const Move     :  TMove;
   const Solution :  TSolution;
   const TabuList :  TTabuList
         )        :  Boolean;
		 
// Return a tabu tenure. t is the normalized time.
function TabuTenure(
         t  :  Real		// [0 .. 1]
         )  :  Integer;

Research

Other