The Traveling Salesman Problem (TSP) is one of the most famous problems in computer science. TSP is basically attempting to find the shortest complete tour through a series of points (cities), starting and ending at the same point. Finding the shortest route that visits a set of locations is an exponentially difficult problem. An brute-force search of all possible paths would be guaranteed to find the shortest, but is computationally intractable for all but small sets of locations. For larger problems, optimization techniques, such as GA, are needed to intelligently search the solution space and find near-optimal solutions. Mathematically, traveling salesman problem can be represented as a graph, where the locations are the nodes and the edges (or arcs) represent direct routes between the nodes. The weight of each edge is the distance between the nodes. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. The goal is to find the path with the shortest sum of weights. Below, we see a simple five-node graph:
In reality, and for this probelm specifically, the nodes can be many-many more:
And using this implementation we are able to find the optimal path for this set of nodes.
For this implementation the Optimal parameters were:
For the Population Size parameter, it was decided that 50 was the optimal number in regards to a result to time ratio.
This is a graph displaying the distance metric (y-axis) against the number of iterations (x-axis)
Below are the results obtained for every type of mutation strategy implemented and tested
It was determined that the best results were obtained with a crossover probability of 0.5-0.7
It was determined that the best results were obtained with a mutation probability of 0.7-0.8
During development, at some point the algorithm came up with a harmonograph as an optimal solution which I thought was very interesting.
