A demo python implementation of genetic algorithms used in order to solve the Travelling Salesman Problem. This notebook was created in order to provide a solution for the following problem statement as part of my CS department's Artificial Intelligence course:
Problem statement - Use genetic algorithms to solve the Traveling Salesperson Problem (TSP) on a large fully connected graph (about 50 nodes)
The program is divided into the following sections -
- Input generation : Euclidean distances between points are generated by creating unique co-ordinates having values ranging from 1 to 1000 (both x and y) via the random library. This method is used in order to meet triangle inequality standards.
- Population creation : A member of the population is defined as a random sampling of all the city indices present, i.e a randomly generated route from city 0, traversing through all the cities, and returning to the city of origin itself.
- Fitness function : The fitness function is defined as the inverse of the total distance covered by a route.
- Crossover section : The random roulette method is used for selection of input. We perform ordered crossovers in the following manner -
- We select a random subset from the first array.
- We select all the elements not present in the subset and place them in the order stored in the second array.
- Main function : Runs the simulation as per input parameters.
For further details on implementation, refer the notebook.
Open the attached notebook in Google Colab, and press Ctrl + F9 to run all code snippets. The main function (last snippet) shall request the following details :
| Input parameter | Description |
|---|---|
| numCities | The number of vertices required |
| numPop | The count of initial population |
| numGen | The number of generations the algorithm should run for |
| probMutation | The probability of mutation (default taken as 0.05) |
The program will provide input details, a randomly generated input graph along with the best fitness values (along with the respective best path and generation of occurence) and time taken to run the program. It also plots down the best fitness values per generation as shown below:
Note : This is a basic demonstration for a course project and not tested for production purposes. Contact me for corrections, feedback or suggestions!