This project presents a Python implementation of a genetic algorithm applied to the Traveling Salesman Problem (TSP), a classical combinatorial optimization problem.
The focus of the project is on demonstrating how evolutionary techniques can be used to efficiently explore large solution spaces where exact algorithms become impractical.
The Traveling Salesman Problem requires finding the shortest possible route that visits each city exactly once and returns to the starting city.
Despite its simple formulation, the problem is computationally demanding due to the factorial growth of the number of possible routes.
In this implementation, candidate solutions are represented as permutations of cities.
The quality of each solution is evaluated using a fitness function defined as the total length of the route, including the return to the starting city.
Through successive generations, the population evolves toward shorter and more efficient routes.
The genetic algorithm employs tournament selection, the OX1 (Order Crossover) operator, swap mutation, and elitism to preserve the best solutions across generations.
These operators are well suited for permutation-based problems such as TSP and help maintain solution validity throughout the evolutionary process.
The algorithm is implemented in Python and allows simple adjustment of key parameters, making it suitable for experimentation and analysis of genetic algorithm behavior.
This repository was created as part of a university project for the course Data Structures, with the aim of combining theoretical concepts and practical implementation.
Install the required dependencies:
pip install -r requirements.txtRun the program:
python tsp.pyAfter execution, the program outputs the best route found and its total cost, and displays a visualization of the algorithm's convergence as well as a two-dimensional representation of the best route.
tsp.py– Implementation of the genetic algorithm and example usagerequirements.txt– Required Python packages.gitignore– Ignored files and folders