Tabu search

Tabu search is a combinatorial optimization problem whereby it tries to look for the best possible solution to a problem such as travelling salesman problem.

When a best move is found it is added into a tabu. List of tabu is used to ensure search path / node is not traverse again. Tabu is remove with each iteration and only when it reaches zero, then search moves forward.

This is to prevent search process to get stuck locally.

For example, please take a look at diagram below. We have 5 location labeled (0, 1, 2, 3, 4) and each has an associated cost. Tabu search is able to tell us minimum cost associated with our chosen path.

We use a 5x5 (2d) matrix to keep track of the cost associated with a edge / path / link.

C# code for this TSP tabu search can be download here. Also included in the code is hill climbing algorithm for solving tsp problem.

The output looks like this

Search done! 
Best Solution cost found = 9
Best Solution :
0 1 2 4 3 0