This project aims to solve the Traveling Salesman Problem (TSP) using a Genetic Algorithm (GA). The TSP is a well-known optimization problem where the goal is to find the shortest possible route that visits each city exactly once and returns to the starting city. Genetic algorithms are a type of evolutionary algorithm that can approximate solutions to optimization and search problems, making them well-suited for solving TSP.
The Genetic Algorithm for TSP includes the following main steps:
- Initialization: Generate an initial population of possible routes.
- Selection: Select the fittest individuals (routes) from the population.
- Crossover: Combine pairs of routes to produce new offspring routes.
- Mutation: Randomly modify some routes to maintain diversity.
- Replacement: Replace the least fit routes with new offspring.
- Termination: The algorithm stops when a set number of generations is reached or a satisfactory solution is found.
To run this project, you'll need Python and the following libraries:
numpymatplotlib
You can install the dependencies with:
pip install -r requirements.txt