The Traveling Salesman Problem

This weekend I was looking at one of the most famous problems in computer science, the Traveling Salesman Problem (TSP). If you have a map of cities, and the distances between them, the goal is to start at one city, and then visit each city exactly once covering the shortest distance possible. The problem is NP-complete, meaning there is no way to find the best solution without trying all possible solutions. And the number of possible solutions is huge for even a small number of cities. For example if there are 5 cities, numbered 0 through 4, then one possible solution would be {0, 4, 3, 1, 2} (where I haven’t specified the distances between cities). There would be a total of 5! = 120 total possible solutions here, not taking into account duplicates. The possible solution {4, 3, 1, 2, 0} would be equivalent to {0, 4, 3, 1, 2}, and in general each solution has n equivalent solutions, so the total number of distinct possible solutions for the Traveling Salesman Problem is (n-1)! which is still gigantic. If there are just 40 cities, there are 39! = 20,397,882,081,197,443,358,640,281,739,902,897,356,800,000,000 possible solutions. Anyway, I have been experimenting with a Simulated Bee Colony algorithm to try and solve some TSP sets. The idea is to mimic the behavior of a colony of bees to find a very good but not necessarily optimal solution. I haven’t been too successful so far. For one standard TSP benchmark problem set with 51 cities (problem “eil51.tsp”), the optimal shortest path solution is known to be 426 arbitrary units of distance long. My current version of a Simulated Bee Colony Algorithm is stalling out with a best solution / shortest distance found of about 720. See screenshot below. But I’m going to keep at it. I suspect that my Simulated Bee Colony algorithm, like many related meta-heuristic algorithms including Genetic Algorithms, Ant Colony Optimization, and Simulated Annealing Algorithms, is prematurely converging. So, I’m writing some analysis code to see if I can gain some insights into what’s going on.
This entry was posted in Machine Learning, Software Test Automation. Bookmark the permalink.