Travelling Salesman Solver
The inspiration for this project was the famous travelling salesman problem, where you
try to find the shortest route between a number of locations, visiting each location only once.
I wanted to see if a simple evolutionary algorithm could be used to obtain decent solutions, and to experiment with different mutations to see which gave the best results.
The project is open source and can be found on GitHub
Run it yourself
To run this program yourself on Windows, download and unzip the file and double-click on "TravellingSalesman.exe" inside the folder.
TravellingSalesman_v3 (zip)
Results
The algorithm
A basic hill-climber is used, the tour is copied, mutated and the shortest version is kept. There are 5 differnt mutations that can be applied.
- Move a random stop to a random location
- Move some random stops to random locations
- Take a random subsection of the tour and reverse the order of stops
- Take a random subsection of the tour and move it to the end
- Swap the position of two stops
Individually these mutations often get stuck in clearly sub-optimal solutions, however together they cover each other's weaknesses and give great results very quickly.
Solution
This shows the solution for the above image, over 22.5 million mutations have been applied, but the best solution found was at mutation 4.6 million. It is hard to prove this is the most optimum solution, and it
likely isn't, the evolutionary landscape that this particular problem exists on has many local optima that my algorithm may not be able to escape easily, and even if it can, the nature of random mutations means that it could
take a very long time to find further improvements.
250 Stops Example
The more stops that are added, the longer it takes to settle on a good solution. There is a "high contrast" mode to make routes with hundreds of stops easier to view. In this example the "Reverse Section"
mutation is selected to quickly hone in on a good solution, then the other mutations are enabled, allowing a small number of improvements that would not have otherwise been possible.