The world’s leading publication for data science, AI, and ML professionals.

What is Tabu Search?

An intuitive explanation of the Tabu Search optimization algorithm and how to apply it to the traveling salesman problem

Photo by Clint Adair on Unsplash
Photo by Clint Adair on Unsplash

Background

In one of my previous posts, we discussed the meta-heuristic Optimization algorithm Simulated Annealing. This is a stochastic search algorithm that is used to try to find the _global optimum in combinatorial optimization problems such as the famous traveling salesman problem (TSP) and knapsack problem._

There is another similar algorithm named the _Tabu Search,_ which can be considered as a generalization of the Simulated Annealing algorithm. In this article, I want to discuss and explain the Tabu Search, recap TSP, and then implement Tabu Search to solve the TSP in Python.

Tabu Search

Overview

Tabu Search is a meta-heuristic optimization algorithm conceived by Fred Glover in the late 1980s. Similarly to Simulated Annealing, Tabu Search uses local search but can accept a worse solution to avoid getting stuck in local minima. Its other main key ingredient is that it prevents the algorithm from visiting previously observed solutions using memory structures to wider explore the search space. In other words, it has a ‘TABU’ list!

The Tabu Search algorithm can be used to solve a wide range of problems:

Therefore, it is worthwhile learning and understanding it as it can be used in multi-faceted situations.

Memory Structures, Tenure & Tabu List

As mentioned above, Tabu Search keeps a track of previously visited solutions, this is known as the Tabu List and holds them in memory for a specific time, Tenure, to prevent the recycling of solutions and better explore the search space.

In general, there are two types of memory structures that Tabu Search uses:

  • Short Term: This is normally a certain number of previously visited solutions that we should not go back to.
  • Long Term: This is to aid in instances where the search is getting stuck and help broaden the search.

In reality, there is no requirement to have one or either, or even both. The main idea is that we keep track of what the algorithm is doing and help it explore a wider range of possible solutions.

Algorithm Outline & Aspiration Criteria

The general flow of the Tabu Search goes as follows:

  • Generate an initial valid solution.
  • Get the set of possible neighborhood solutions using a local search from the current solution.
  • From these neighborhood solutions, get the best candidate that is not on the Tabu List.
  • Compare this best candidate to the best solution found so far and assign as appropriate.
  • Update the tabu list with the value of the best candidate.
  • Repeat steps 2–5 using the best candidate to generate the new neighborhood until meeting some stopping conditions.

An additional rule is that if we find a solution that is on the Tabu List but has a better objective function than the current best solution, we accept that solution anyway. This is known as the aspiration criterion.

That’s it! If you are still unsure about this process, keep reading as we will implement this in Python to make this theory more concrete.

Travelling Salesman Problem

Before we solve the traveling salesman problem (TSP) using Tabu Search, it’s worth quickly discussing what TSP is.

TSP is probably the most famous and easiest-to-understand combinatorial optimization problem. The problem is simple: ‘Given a set of cities, what is the shortest route that visits each city once and returns to the original city?’

The reason this problem is difficult to solve is that it is NP-hard and the number of possible routes is subject to a _combinatorial explosion_ as we increase the number of cities we need to visit. As an example, exploring every solution by brute force for 20 cities would take ~2000 years!

The number of possible routes scales as (n-1)!/2

Due to the intractability of the TSP for a certain number of cities, we need to resort to heuristics, such as Tabu Search and Simulated Annealing, to provide sufficient solutions in a reasonable amount of time.

Tabu Search for TSP in Python

Algorithm Design

Let’s first list out some pseudo-code on how we will implement the Tabu Search for the TSP:

  • Generate an initial route and update the tabu list with this initial route
  • From this initial route, generate the neighborhood by swapping adjacent cities in the current route
  • Get the best neighborhood route, the shortest, from this neighborhood that is not on the tabu list
  • Compare this best neighborhood route with the best overall found route and update as required
  • Repeat steps 1–3 using the current best neighborhood route to produce a new neighborhood

This is quite a rudimentary Tabu Search algorithm as it only contains short-term memory structures.

Python Code

Below is a general class implementing the above algorithm. The class simply needs an initial_solution , which is a list of the cities in a certain order, and a dictionary cities that maps the cities to their coordinates.

Let’s now run this class for some synthetically generated dataset:

Plot generated by author in Python.
Plot generated by author in Python.
Plot generated by author in Python.
Plot generated by author in Python.

The best found solution looks like a pretty reasonable result and didn’t take us thousands of years to compute!

Summary and Further Thoughts

In this post, we have explained the meta-heuristic Tabu Search algorithm. This optimization algorithm uses local search techniques, but can still escape local minima by accepting worse solutions. It also makes use of the Tabu List which stops it from transitioning to previously visited solutions and greater explore the search space. This algorithm gave great results when applied to the traveling salesman problem.

The full code can be found on my GitHub here:

Medium-Articles/Optimisation/tabu-search at main · egorhowell/Medium-Articles

Another Thing!

I have a free newsletter, Dishing the Data, where I share weekly tips for becoming a better Data Scientist. There is no "fluff" or "clickbait," just pure actionable insights from a practicing Data Scientist.

Dishing The Data | Egor Howell | Substack

Connect With Me!

References and Further Reading


Related Articles