Simple Implementation of Tabu Search Algorithm

Posted on Edited on Views: Word count in article: 439 Reading time ≈ 2 mins.

Basic Concept

Tabu Search (TS) is a meta-heuristic algorithm that was first proposed by Glover in 1986. The algorithm avoids repeated searches by introducing a tabu table, and pardons some good solutions or states in tabu table through amnesty rules, so as to achieve a better global optimization effect.

Steps

Tabu Search algorithm typically includes the following key steps:

  • Step 1: Generate an initial solution, create an empty tabu table, and set the tabu length.

  • Step 2: Use neighborhood operators (such as crossover and mutation operators in Genetic Aalgorithms) to generate multiple new solutions and calculate the fitness of these solutions.

  • Step 3: Seclect the solution with the best fitness value from these new solutions and compared with the historical optimal solution found by the algorithm:

    ① If it is better than the historical optimal solution, the tabu table is not considered and it is used as the solution for the next iteration. Add the selected solution to the tabu table.

    ② If it is not better than the historical optimal solution, select the solution that is not in the tabu table with the best fitness value as the solution for the next iteration. Add the selected solution to the tabu table.

  • Step 4: Repeat steps 2 and 3 until the algorithm termination condition such as the maximum number of iterations or solution time limits are met.

Example

Next, we try to solve the traveling salesman problem using Tabu Search algorithm.

Given a number of cities, as shown in the image below, find the path with the least travel cost while visiting each city exactly once and returning to the starting city.

Result

In the iterative process of the TS algorithm, the fitness value (travel cost) change process of the optimal solution found is as follows:

The optimal solution found by the algorithm is as follows:

1
2
3
city number: 20
Best Route: [18, 6, 4, 19, 11, 5, 1, 0, 10, 2, 17, 8, 16, 7, 12, 13, 14, 15, 3, 9]
Best Value: 431.30725365480686

The path finally searched by the algorithm is shown below:

Note that the green line in the graph represents the line connecting the starting and ending cities.

Code

The Python code of the TS for the above example is here: Optimization/metaheuristic_algorithms/Tabu_Search/TS.py (github.com)