Tabu Search (TS) in MATLAB

Tabu Search (TS) is a local search metaheuristic proposed by Fred W. Glover in 1986. It is based on the definition of a neighborhood and on the actions that convert a solution into its neighboring solutions. The algorithm starts with a single solution and looks for better ones by applying actions and moving between neighbors.

A set of rules manages which actions are accepted, applicable and available. One of the most important rules is this: after an action is performed, it becomes unavailable (tabu) until a certain number of other actions have been performed. For more information, see the Tabu Search article on Wikipedia (opens in a new tab).

How Tabu Search works

In every iteration, TS looks at all the neighbors of the current solution that can be reached by an action that is not tabu, and moves to the best of them. It makes this move even when the best neighbor is worse than the current solution. This is how TS climbs out of a local minimum, where a plain local search would stop.

The tabu rule keeps the search from going straight back. Without it, the search would often undo its last move in the next iteration and cycle between the same few solutions. The main ideas are:

• Tabu list and tabu tenure. A performed action is stored in the tabu list for a fixed number of iterations, called the tabu tenure. A short tenure gives a more local search, and a long tenure forces the search to explore further.
• Aspiration criterion. Many versions of TS allow a tabu action when it leads to a solution better than the best one found so far. This rule is called the aspiration criterion.
• Best solution. The best solution found so far is stored separately, so a worse move never loses it.

About this implementation

This post shares an open-source, structured implementation of Tabu Search in MATLAB for combinatorial optimization problems. The source code solves two well-known problems:

• Traveling Salesman Problem (TSP (opens in a new tab))
• $n$-Queens Problem (a general case of the Eight Queens puzzle (opens in a new tab))

In both problems, a solution is a permutation. In the TSP, it is the order in which the cities are visited, and the cost is the length of the closed tour. The sample model in CreateModel.m has 18 cities. In the $n$-Queens Problem, the $i$th value of the permutation gives the column of the queen in row $i$, so no two queens share a row or a column. The cost in MyCost.m is the number of queen pairs on the same diagonal, and a cost of 0 means the puzzle is solved.

Actions and the tabu list in the code

CreatePermActionList.m lists every action on a permutation of length $n$: swap two positions, reverse a part of the permutation, or move one element to another position. Each action has a tabu counter. In every iteration, the code tries all actions with a counter of 0, moves to the best new solution, sets the counter of the chosen action to the tabu tenure TL, and reduces all other counters by 1. This code does not use an aspiration criterion. The search stops after MaxIt iterations, or as soon as the best cost reaches 0.

Here nAction is the number of actions in the list.

How to run it

The download has two folders, 01 Tabu Search for TSP and 02 Tabu Search for n-Queens. Open one of them in MATLAB and run main.m, which calls ts.m. The program prints the best cost in every iteration, draws the best solution as it improves, and plots the best cost against the iteration at the end. The $n$-Queens project also prints the position of every queen.

If you know MATLAB, you should find the code easy to use in your research and projects. As an example, the final solution of an $n$-Queens puzzle with $n = 50$ is shown below.

Check the result

For the n-Queens example, a cost of 0 means no diagonal conflicts remain because the permutation already prevents row and column conflicts. Verify that the returned positions form a valid permutation. For the TSP, check the full closed-tour length rather than looking for a zero cost. The code has no aspiration override, so changing tabu tenure can restrict which improving moves are available.

Related posts

• Simulated Annealing in MATLAB solves the same 18 city TSP with the same three moves.

Mostapha Kalami Heris, Tabu Search (TS) in MATLAB (YPEA116), Yarpiz, 2015. https://yarpiz.com/tabu-search-ypea116

@misc{yarpiz-ypea116,
  author = {{Mostapha Kalami Heris}},
  title = {{Tabu Search (TS) in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA116},
  url = {https://yarpiz.com/tabu-search-ypea116}
}