10.4. Tabu Search

10.4.1. Algorithm Description

Tabu Search works like Hill Climbing, but it maintains a tabu list to avoid getting stuck in local optima. The tabu list holds recently used objects that are taboo to use for now. Moves that involve an object in the tabu list, are not accepted. The tabu list objects can be anything related to the move, such as the planning entity, planning value, move, solution, …​ Here’s an example with entity tabu for 4 queens, so the queens are put in the tabu list:

entityTabuSearch
Note

It’s called Tabu Search, not Taboo Search. There is no spelling error.

Scientific paper: Tabu Search - Part 1 and Part 2 by Fred Glover (1989 - 1990)

10.4.2. Configuration

Simplest configuration: 

  <localSearch>
    <localSearchType>TABU_SEARCH</localSearchType>
  </localSearch>

When Tabu Search takes steps it creates one or more tabus. For a number of steps, it does not accept a move if that move breaks tabu. That number of steps is the tabu size. Advanced configuration: 

  <localSearch>
    ...
    <acceptor>
      <entityTabuSize>7</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1000</acceptedCountLimit>
    </forager>
  </localSearch>
Important

A Tabu Search acceptor should be combined with a high acceptedCountLimit, such as 1000.

Planner implements several tabu types:

  • Planning entity tabu (recommended) makes the planning entities of recent steps tabu. For example, for N queens it makes the recently moved queens tabu. It’s recommended to start with this tabu type. 

        <acceptor>
      <entityTabuSize>7</entityTabuSize>
    </acceptor>

    To avoid hard coding the tabu size, configure a tabu ratio, relative to the number of entities, for example 2%: 

        <acceptor>
      <entityTabuRatio>0.02</entityTabuRatio>
    </acceptor>

  • Planning value tabu makes the planning values of recent steps tabu. For example, for N queens it makes the recently moved to rows tabu. 

        <acceptor>
      <valueTabuSize>7</valueTabuSize>
    </acceptor>

    To avoid hard coding the tabu size, configure a tabu ratio, relative to the number of values, for example 2%: 

        <acceptor>
      <valueTabuRatio>0.02</valueTabuRatio>
    </acceptor>

  • Move tabu makes recent steps tabu. It does not accept a move equal to one of those steps. 

        <acceptor>
      <moveTabuSize>7</moveTabuSize>
    </acceptor>

  • Undo move tabu makes the undo move of recent steps tabu. 

        <acceptor>
      <undoMoveTabuSize>7</undoMoveTabuSize>
    </acceptor>

  • Solution tabu makes recently visited solutions tabu. It does not accept a move that leads to one of those solutions. It requires that the Solution implements equals() and hashCode() properly. If you can spare the memory, don’t be cheap on the tabu size. 

        <acceptor>
      <solutionTabuSize>1000</solutionTabuSize>
    </acceptor>

    For non-trivial cases, solution tabu is usually useless because the search space size makes it statistically highly unlikely to reach the same solution twice. Therefore its use is not recommended, except for small datasets.

Sometimes it’s useful to combine tabu types: 

    <acceptor>
      <entityTabuSize>7</entityTabuSize>
      <valueTabuSize>3</valueTabuSize>
    </acceptor>

If the tabu size is too small, the solver can still get stuck in a local optimum. On the other hand, if the tabu size is too large, the solver can be inefficient by bouncing off the walls. Use the Benchmarker to fine tweak your configuration.