Genetic Algorithms – Travelling Salesman Problem

For this assignment we created a genetic algorithm to solve the travel salesman problem (TPS), we also tested how different parameters affects the performance of our GA and created a small report presenting our findings.

The TSP asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

In this TSP implementation, for debugging purposes, every city remains in the perimeter of a unit circle maintaining the same distance between the adjacent cities, because of this property we know the shortest path through all the cities will be at most 2π (perimeter of unit circle) allowing us to check the validity of our algorithm regardless the amount of cities.

We started with the standard genetic algorithm structure and used elitism, where every city is a chromosome and a set of all the chromosomes corresponds to a path starting at index 0.

The crossover works by randomly selecting 2 parents, parent A gets a random index (from 0 to list.length) from the genes list and a random length of genes (from index to list.length) that we use as base for child A respecting the positions, then we fill the rest of genes of child A using the genes of Parent B by keeping the order in which they appear at Parent B, while checking they don’t belong to the chunk of genes we took from parent A.

For the mutation step we go gene by gene checking if it should mutate, if that’s the case then we swap the gene with a random number (within the possible range) and swap the gene that had the random number with the gene that mutated (to maintain a path that visits only one city).

After doing this per every gene we go back to the beginning of the loop while doing it for n (5,000 during experiments) iterations.

Our algorithm performed as expected and was able to always find the path when inputted the correct parameters (check report for more information).

Repository on Github