Genetic Algorithm for the Traveling Salesman Problem (TSP)

A from-scratch genetic algorithm that evolves a population of tours to minimize the total distance of a round trip visiting every city exactly once. The GA engine, crossover operators, and 2-opt / 3-opt local-search mutations are all implemented by hand — no external TSP solver.

About

A school project from my third year of BUT Informatique (semester S5, 2025–2026) at IUT A, Université de Toulouse, for the course Modélisations mathématiques (R5A12/R5B10). The assignment was to implement a genetic algorithm for the Traveling Salesman Problem, including the optional 250-city challenge.

Grades: 17/20 on the written report, 19/20 on the oral defense.

Document
Assignment brief	dossier_algo_genetiques.pdf
Written report (17/20)	Modèlisation mathématiques.pdf
Defense slides (19/20)	Algorithmes Génétiques et TSP.pdf

The report and slides are written in French.

Requirements

pip install -r requirements.txt

• Python 3.10+ (uses structural pattern matching, match/case)
• numpy, matplotlib, pillow (for GIF export)

Project layout

File	Role
individual.py	A single candidate tour (Individual.route). Computes distance and fitness (1 / distance); hosts the mutation operators: 2-opt (three variants) and 3-opt.
population.py	The Population class and the engine: city generation, tournament selection, six crossover operators, the crossover() reproduction step, and all plotting/animation.
util.py	Generates spreadsheet-style city names (A, B, ... Z, AA, AB, ...).
main.py	Run for a fixed duration, print the best tour, plot the result and the fitness curve.
main_gif.py	Same as main.py but renders an evolution GIF.
problem_250.py	Loads the 250-city benchmark instance from data/defi250.csv.
benchmark_methods.py	Compares the six crossover operators on identical seeded input; plots fitness vs. time.
compare_mutations.py	Head-to-head comparison of two configurations.
data/defi250.csv	Benchmark instance: 250 cities as x;y per line.
outputs/	Generated GIFs and PNGs land here (git-ignored).

How it works

1. Initialization — cities are placed at random in [0,1]² (or on a circle, whose optimum is known, for testing). The initial population holds l random tours sharing a fixed start city.
2. Selection — tournament: draw k individuals at random, keep the fittest.
3. Crossover — pick two distinct parents, produce two children. Available operators: PMX, CX, ERX, OX, HX, and HX-extended (the HX variants are distance-aware).
4. Mutation — with probability mutation_rate, apply a 2-opt or 3-opt local search to a child (memetic: the mutation improves the tour rather than just perturbing it).
5. Replacement — add the unique children, then trim the worst back down to population size l (steady-state, elitist).

Usage

python main.py              # run + static plots
python main_gif.py          # run + evolution GIF
python problem_250.py       # 250-city benchmark instance
python benchmark_methods.py # compare crossover operators
python compare_mutations.py # compare two configurations

Key parameters

Defined at the top of the runnable scripts:

• cities — number of cities.
• population_size — number of individuals (defaults to cities * 5).
• tournament_size — number drawn for tournament selection (defaults to population_size // 10).
• mutation_rate — probability of mutating each child.
• method — crossover operator ('pmx', 'cx', 'erx', 'ox', 'hx', 'hx extended').
• mutation — mutation operator ('2-opt', '2-opt alt', '2-opt extended', '3-opt').

Generated artifacts

The scripts write GIFs (evolution_tsp.gif) and PNGs (benchmark_fitness.png) into the outputs/ folder. Its contents are git-ignored (the folder itself is kept via outputs/.gitkeep).