Article Details
Completion Time: 30 min
Difficulty: Intermediate
Subject: Optimization Methods and Algorithms
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:
- HeuristicsHeuristics are approximate solution techniques we use to resolve Hard combinatorial problem.
- 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. - 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
- 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.
- 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
- The Tabu List lengthThe max length of Tabu List determines how long a moves/solution point will be forbidden.
- 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:
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:
- After a precised amount of time T
- After a precised number of iterations I
- 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.
- Intensification
Intensification represents the intermediate-term memory of the Tabu Search. Here we intensify the research in promising regions of the search space.
- 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
- Initialization
Choose (create) an initial solution.
- Search
- While Stop Criteria not satisfied do
- 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. - Update the Tabu list
Include the actual move in Tabu List.
Remove the oldest move if necessary.
5. Links and Literature
- Wikipedia article
- soldano, alessandro [Bachehor Degree Thesis] L’algoritmo “Tabu Search” per l’ottimizzazione, teoria ed applicazioni. (2012)
- 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.
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.