Tabu Search:all you need to know about

Article Details


Completion Time: 30 min
Difficulty: Intermediate
Subject: Optimization Methods and Algorithms


Tabu Search 300x122 Tabu Search:all you need to know about


This article is about the Tabu Search. We will first learn what is the Tabu Search. we will see some background knowledge on the Tabu Search , principal elements of the Tabu Search and finally the structure of the Tabu Search Algorithm.


1. What is the Tabu Search ?

The Tabu Search is a metaheuristic search method to resolve combinatorial optimization problem. It was created by Fred W. Glover in 1986.

Intuitive Idea behind the Tabu Search

So what’s the idea behind the Tabu Search ?

Search a solution using the intuition that there is no point in accepting a new (poor) solution unless it is to avoid a path already investigated

In this way new regions of the search space will be investigated to avoid the local minima.

Basic version of the Tabu search

The Tabu Search moves in the search space avoiding to go back to the previously solution. For this purpose, the Tabu Searh has a short-term memory system. The short-term memory system store previously visited solution and have a set of rules to prevent the reversal of recent moves and sometimes allow non improving solution.
To really understand the Tabu Search, we need to review some background knowledge.


2. Background Knowledge on Tabu Search

Let’s review some important concepts:

  1. HeuristicsHeuristics are approximate solution techniques we use to resolve Hard combinatorial problem.
  2. Metaheuristics
    Metaheuristics are techniques who improve heuristics to efficiently explore the search space in order to find near–optimal solutions. They use a general strategy for guiding and controlling “inner”heuristics specifically tailored to the problems at hand.
  3. Local search methodsLocal search methods are algorithms that go from a potential solution and check in the neighborhood of that solution looking for an improving solution. The algorithm stops with a stop condition or if there’s no more improving solution.
    The big limitation of these technique is the local-optima problem(When a solution are not improved in the local region and the algorithm is on status quo).

Now let’s go back to the Tabu Search analyzing its principal element.


3. Principal elements of the Tabu Search

Search space and Neighborhood structure

  1. Search spaceThe set of all possible solution that can be considered during the search. Define the search space is an important step when implementing the Tabu Search.
  2. Neighborhood structureHow we define a Neighborhood ? what are the local transformations (moves) we can make to continue the search ? We have to answer this question because it will impact on the the quality of results of the Tabu Search.

The Tabu List

The Tabu List represents the short-term memory structure of the Tabu Search. It consist of a list of previous solutions that must be avoid or the list of moves that are forbidden.
The Tabu List can have a dynamic or static structure.

The Tabu List Structure
  1. The Tabu List lengthThe max length of Tabu List determines how long a moves/solution point will be forbidden.
  2. The Tabu List elements attributesThe elements of the Tabu List have generally more than one attribute. How we define the Tabu List elements attributes. This depends on the problem we are solving.

The Aspiration Criteria

The aspiration Criterion in an exception for the Tabu List rule. It allow to accept Tabu List elements if they satisfy some condition.
Some examples:

  1. Accepting the more improving solution
  2. Accepting the solution that changes the search region

The Stop Criterion

When do we stop the search ? Here we have the list of general Stop criteria that can be used on The Tabu Search:

  1. After a precised amount of time T
  2. After a precised number of iterations I
  3. After a precised number of consecutive iterations without improvement

The next elements are not present in the Simple/basic version of the Tabu Search.

Extension Elements: Intensification and Diversification

These elements are all about monitoring and dynamically update some of the previous elements with some goals.

  1. Intensification

    Intensification represents the intermediate-term memory of the Tabu Search. Here we intensify the research in promising regions of the search space.

  2. Diversification

    Intensification represents the long-term memory of the Tabu Search. Here we force the search in previous unexplored regions of the search space.


4. Structure of the Tabu Search Algorithm

  1. Initialization

    Choose (create) an initial solution.

  2. Search
    1. While Stop Criteria not satisfied do
    2. Choose the best feasible solution from the neighborhood of the actual solution

      best feasible solution is not in Tabu List.
      Or best feasible solution is in Tabu List and satisfy the Aspiration criteria.

    3. Update the Tabu list

      Include the actual move in Tabu List.
      Remove the oldest move if necessary.


5. Links and Literature

  1. Wikipedia article
  2. soldano, alessandro [Bachehor Degree Thesis] L’algoritmo “Tabu Search” per l’ottimizzazione, teoria ed applicazioni. (2012)
  3. Lecture Notes from NORTH CAROLINA STATE UNIVERSITY – Overview of Tabu Search

6. Thank you

Support my challenge, support my blog. Please Share this article if you found it useful. Thank you.


 Tabu Search:all you need to know about Tabu Search:all you need to know about

Precedente Who else want to know Travelling Salesman Problem ? Successivo Eclipse: create a Java project from ".java" and ".jar" files

Un commento su “Tabu Search:all you need to know about

  1. Thank you for this wonderfull tutorial about tabu search.I spend a lot of search to reach here.But iam glad.Thank you so much for your time.Plz update more post regarding taboo search.

Lascia un commento

This site uses Akismet to reduce spam. Learn how your comment data is processed.