Tabu Search is a meta-heuristic that guides a local heuristic search procedure to explore the solution space beyond local optimality [1].

A very impressive introduction of Tabu search (and other discrete optimization methods) are provided by Prof. Pascal Van Hentenryck.

The basic idea of tabu search is to maintain a tabu (forbidden) list to avoid circulating around local minima by putting the previous steps in the tabu list. In tabu search, each solution \(x\) has an associated neighborhood \(N(x)\sub X\) , and each solution \(x'\in N(x)\) is reached from \(x\) by an operation called a move.

One major problem is that sometime it is too costly to maintain all the visiting history hence a improvement is to maintain a short-term memory and only keep recent visits. While sometimes it is still not efficient to keep the whole configuration (the whole \(x\)), then we can only keep the abstraction of the previous configurations. For example, we can only keep the swap operations in the when \(x\) is a sequence.

Key Points

  • Cost function \(f(x)\)
  • Initialization
  • Short-Term Memory
    • The solutions that have been searched

  • Long-Term Memory

    • Intensification: Store high-quality solutions and return to them periodically
    • Diversification: When the search is not producing improvement, make a big change of the current state.
    • Strategic oscillation: change the precentage of time spent in the feasible and infeasible regions.

  • Aspiration

    • Sometimes one configuration is so good that even it is in the tabu list but we still want to accept it, we can use a technique called “aspiration” to take some extremely good configuration outside the tabu list.

Ref

[1] Glover, F., & Martí, R. (1986). Tabu Search. Tabu Search, 1–16.