A custom Genetic Algorithm (GA) built from scratch in Python to solve the 3D Traveling Salesman Problem. The solver combines greedy initialization, adaptive crossover strategies, roulette-wheel selection, and an explicit diversity guard to escape local optima and converge on near-optimal routes.
The GA pipeline runs through these stages each generation:
| Stage | Function | Details |
|---|---|---|
| Initialization | generate_population + Greedy_Heuristic_for_nearest_city |
Mix of random paths and a greedy nearest-neighbor seed for strong starting diversity |
| Fitness | rank_population |
Inverse of total Euclidean path distance — shorter paths score higher |
| Selection | select_parent |
Roulette-wheel selection — fitter individuals have proportionally higher pick probability |
| Crossover | crossover |
Adaptive: Ordered Crossover (OX) for small city counts; Partially Mapped Crossover (PMX) for large ones |
| Mutation | mutate |
Random swap/shuffle with configurable rate to introduce variation |
| Diversity Guard | maintain_diversity_in_Genetic_Algorithm |
Monitors population diversity ratio — reinjects random paths below threshold to prevent premature convergence |
- Memoized distance cache: Stores computed Euclidean distances between city pairs — avoids redundant calculations across generations
- Adaptive crossover: OX preserves relative order in small search spaces; PMX handles larger inputs without creating duplicate cities
- Diversity maintenance: Explicit guard prevents the population collapsing to near-identical paths — a common GA failure mode
- 3D coordinates: Works with full 3D Euclidean space, not just 2D maps
input.txt → line 1: number of cities
lines 2–N: x y z coordinates of each city
output.txt → line 1: total optimal path distance
line 2: ordered sequence of city visit indices
- Language: Python 3
- Libraries: NumPy (distance computation),
random(GA operations) - Algorithm: Genetic Algorithm — selection, crossover, mutation, diversity management