Adisorn Owatsiriwong, D.Eng. The Traveling Salesman Problem (TSP) is a standard combinatorial problem to test an optimization algorithm (https://analyticsindiamag.com/10-real-life-applications-of-genetic-optimization/). The solver must search for the shortest path to visit the cities ‘1’ to ‘n’ and return to city ‘1’ again without visiting any city twice. In this example, we will use Genetic Algorithm we have developed to test such TSP problem. The problem has (n-1)!/2 combinations. Some possible routes are
[1 3 7 5 6 4 2 1] (total distance = 66)
[1 2 3 4 5 6 7 1] (total distance = 69)
[1 7 6 5 3 4 2 1] (total distance = 65)
However, all the above solutions are not the best solution. In this example, we will implement Genetic Algorithm to find the best solution of this example.
For comparison, the nearest neighbor search's (Best first search) solution is [1 3 5 6 7 4 2 1], giving a total distance of 70. This is quite far from the optimum value, but it's the quickest way to get a solution. To solve this problem by GA, it is helpful to define a so-called 'Distance Matrix'. A coefficient of the distance matrix D(I,j) indicates the distance from node i to node j. It's noted that the diagonal value of the distance matrix is always zero.
Another example is taken from Google's OR-Tools webpage. (https://developers.google.com/optimization/routing/tsp)
Problem Statement:
A salesman is traveling through the USA. He starts in New York and travels to each city before returning to NY again. The distance matrix is updated based on Google's map data and then solved using GA. Maximum generation is now increased to 200 with the number of distinct populations = 100. The probability of crossover (pc) is zero, while the probability of mutation and elitism is set to 0.5 and 0.2, respectively.
The best solution is [1, 8, 3, 4, 5, 13, 7, 9, 2, 12, 11, 6, 10, 1 ] with a total distance = 7,293 miles
This is identical to the solution obtained by Google's OR-Tools as shown below. Please note that the index in Python starts from 0 while MATLAB starts from 1.
Other several test runs have been made, but I can find the next best solution as shown below.
Solution = [1, 3, 10, 6, 11, 12, 2, 9, 7, 13, 5, 4, 8, 1] with a total distance = 7,310 miles (1% error)
As a nature of stochastic algorithms, different runs usually return different optimal solutions. Moreover, the global minimum is not guaranteed. The solution might be trapped at some local minima if the exploitation degree is insufficient.