__Solving the Travelling Salesman Problem using Tabu Search & Java__

In this tutorial, we will introduce how we attempted to solve the Travelling Salesman Problem (TSP) using the Tabu Search Algorithm. The code implemented here is a simple version to Tabu search, but should cover all the basics. We will provide the implementation in Java.

__Basic Tabu Search Steps__

Tabu Search is an improvement over basic local search that attempts to get over local search problems by not being stuck in a local minima.

This is accomplished by allowing the acceptance of non-improving moves, in order to not be stuck in a locally optimum solution, and in

the hope of finding the global best. Tabu search also allows us to escape from sub-optimal solutions by the use of a

is a list of possible moves that could be performed on a solution. These moves could be swap operations (as in TSP) or subtractions and

additions in case of dealing with numeric optimization problems. If a move is accepted (new best solution is found), its move is made tabu

for a certain number of iterations, i.e. we cannot perform the same move for a certain number of iterations. When a move is made tabu,

it is added to the tabu list with a certain value called the

Only when the tabu tenure of a certain move is 0, can the move be performed and accepted.

To allow a tabu move, you need to apply

for example, the move allows a new global best solution, hence the move is accepted, and its tabu tenure is renewed. Tabu search performs the

following steps:

1 - Create an initial solution ( could be created randomly), now call it the current solution.

2 - Find the best neighbor of the current solution by applying certain moves.

3 - If the best neighbor is reached my performing a non-tabu move, accept as the new current solution.

else, find another neighbor (best non-tabu neighbour).

4- If maximum number of iterations are reached (or any other stopping condition), go to 5, else go to 2.

5- Globally best solution is the best solution we found throughout the iterations.

This is accomplished by allowing the acceptance of non-improving moves, in order to not be stuck in a locally optimum solution, and in

the hope of finding the global best. Tabu search also allows us to escape from sub-optimal solutions by the use of a

*tabu list*. A tabu listis a list of possible moves that could be performed on a solution. These moves could be swap operations (as in TSP) or subtractions and

additions in case of dealing with numeric optimization problems. If a move is accepted (new best solution is found), its move is made tabu

for a certain number of iterations, i.e. we cannot perform the same move for a certain number of iterations. When a move is made tabu,

it is added to the tabu list with a certain value called the

*Tabu Tenure (tabu length).*With each iteration, the tabu tenure is decremented.Only when the tabu tenure of a certain move is 0, can the move be performed and accepted.

To allow a tabu move, you need to apply

*aspiration criteria.*Aspiration criteria allows a tabu move to be selected based on certain constraints,for example, the move allows a new global best solution, hence the move is accepted, and its tabu tenure is renewed. Tabu search performs the

following steps:

1 - Create an initial solution ( could be created randomly), now call it the current solution.

2 - Find the best neighbor of the current solution by applying certain moves.

3 - If the best neighbor is reached my performing a non-tabu move, accept as the new current solution.

else, find another neighbor (best non-tabu neighbour).

4- If maximum number of iterations are reached (or any other stopping condition), go to 5, else go to 2.

5- Globally best solution is the best solution we found throughout the iterations.

__TSP and Java implementation__

The Travelling Salesman Problem (TSP) is an NP-Hard problem. It goes as follows, given a set of cities, with paths connecting

each city with every other city, we need to find the shortest path from the starting city, to every other city and come back to the

starting city in the shortest distance

each city with every other city, we need to find the shortest path from the starting city, to every other city and come back to the

starting city in the shortest distance

**without**visiting any city along the path more than once.__Representing the problem environment__

We can represent a graph as the one above by using a 5x5 matrix, where element [0][1] contains the edge cost between cities 0 and 1.

Please note that the graph is non directional, hence the distance from city 0 to city 1 is the same as the distance from city 1 to city 0.

Please note that the graph is non directional, hence the distance from city 0 to city 1 is the same as the distance from city 1 to city 0.

*(Code below is from the TabuSearch.java file)*tspEnvironment.distances = //Distance matrix, 5x5, used to represent distances |

new int[][]{{0, 1, 3, 4, 5}, |

{1, 0, 1, 4, 8}, |

{3, 1, 0, 5, 1}, |

{4, 4, 5, 0, 2}, |

{5, 8, 1, 2, 0}}; |

__Tabu List__

The tabu list is also represented as a 5x5 matrix, where each cell represents the tabu tenure of a swap operation. If 2 cities are swapped,

for example, city 1 and city 2, the move will be made tabu in the matrix in both [1][2] and [2][1]. This is to prevent the algorithm to go back

on a move before exploring a little bit.

for example, city 1 and city 2, the move will be made tabu in the matrix in both [1][2] and [2][1]. This is to prevent the algorithm to go back

on a move before exploring a little bit.

__Solution Array__

The solution to the problem will be represented as an array of integers. For example, the path

{0, 1, 2, 3, 4, 0} will be represented as follows in Java:

{0, 1, 2, 3, 4, 0} will be represented as follows in Java:

int[] currSolution = new int[]{0, 1, 2, 3, 4, 0}; //initial solution |

We are going to use the swap operator to find a neighboring solution. Note that the 0's in the array that represent the starting city "0", cannot

change place or be swapped with any other city.

change place or be swapped with any other city.

__Performance__

The code starts from the top level class "TabuSearch.java". The class contains the main method that initializes the problem data, and

performs the tabu search.

performs the tabu search.

public static void main(String[] args) { |

TSPEnvironment tspEnvironment = new TSPEnvironment(); |

tspEnvironment.distances = //Distance matrix, 5x5, used to represent distances |

new int[][]{{0, 1, 3, 4, 5}, |

{1, 0, 1, 4, 8}, |

{3, 1, 0, 5, 1}, |

{4, 4, 5, 0, 2}, |

{5, 8, 1, 2, 0}}; |

//Between cities. 0,1 represents distance between cities 0 and 1, and so on. |

int[] currSolution = new int[]{0, 1, 2, 3, 4, 0}; //initial solution |

//city numbers start from 0 |

// the first and last cities' positions do not change |

int numberOfIterations = 100; |

int tabuLength = 10; |

TabuList tabuList = new TabuList(tabuLength); |

int[] bestSol = new int[currSolution.length]; //this is the best Solution So Far |

System.arraycopy(currSolution, 0, bestSol, 0, bestSol.length); |

int bestCost = tspEnvironment.getObjectiveFunctionValue(bestSol); |

for (int i = 0; i < numberOfIterations; i++) { //perform iterations here |

currSolution = TabuSearch.getBestNeighbour(tabuList, tspEnvironment, currSolution); |

//printSolution(currSolution); |

int currCost = tspEnvironment.getObjectiveFunctionValue(currSolution); |

//System.out.println("Current best cost = " + tspEnvironment.getObjectiveFunctionValue(currSolution)); |

if (currCost < bestCost) { |

System.arraycopy(currSolution, 0, bestSol, 0, bestSol.length); |

bestCost = currCost; |

} |

} |

System.out.println("\n\nSearch done! \nBest Solution cost found = " + bestCost + "\nBest Solution :"); |

printSolution(bestSol); |

} |

The algorithm tries to find the best neighboring solution at each iteration that doesn't involve a tabu move. The solution is always accepted.

Each iteration starts from the solution in the previous iteration. During the iterations we keep track of each generated solution, and store

the best solution we achieved so far. When the predefined number of iterations are over, we print the best solution we found during the tabu search.

When running the program, the algorithm managed to find the optimum solution to the TSP graph above which has a cost of 9.

Each iteration starts from the solution in the previous iteration. During the iterations we keep track of each generated solution, and store

the best solution we achieved so far. When the predefined number of iterations are over, we print the best solution we found during the tabu search.

When running the program, the algorithm managed to find the optimum solution to the TSP graph above which has a cost of 9.

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

You can download the complete source code from here

tsptabu.zip | |

File Size: | 17 kb |

File Type: | zip |