This academic project was completed as the "final project" for the class of Genetic Algorithms and Evolutionary Computing at KU Leuven.
This project was written with:
- Python 3.8
The objective of this algorithm is to find the shortest possible tour for a variable number of cities. The tour_.csv files contain the distance matrix providing the distance between two given cities, and the number in _ provides the total number of cities in the tour.
My implementation of the genetic algorithm (GA) combines the fundamentals building blocks of initialization, selection, variation, mutation and elimination with heuristics such as the nearest neighbor for a portion of the initialization and a modification of the 2-opt for different stages in the algorithm.
In a nutshell, the flowchart below summarizes my implementation:
For more details, please take a look at the project report.
To compare how this implementation of the GA fares (performance results in the report), a greedy heuristic is applied for each of the tours with the results shown below:
- tour29: simple greedy heuristic 169977
- tour100: simple greedy heuristic 42655
- tour250: simple greedy heuristic 49852
- tour500: simple greedy heuristic 103736
- tour750: simple greedy heuristic 52453
- tour1000: simple greedy heuristic 235731