Genetic Algorithm for Traveling Salesman Problem

Category: Optimization
Status: ✅ Complete
Language: Python

Overview

Implementation of a genetic algorithm (evolutionary computation) to solve the Traveling Salesman Problem (TSP). Demonstrates meta-heuristic optimization for NP-hard combinatorial problems.

Problem

Find the shortest route visiting all cities exactly once and returning to the start:

• Classical NP-hard problem
• Brute force infeasible for >20 cities
• Meta-heuristics provide good solutions in reasonable time

Solution: Genetic Algorithm

Algorithm

1. Population: Random initial tours
2. Selection: Tournament selection (fittest individuals survive)
3. Crossover: Combine parent tours to create offspring
4. Mutation: Random changes to prevent convergence
5. Iteration: Repeat until convergence

Key Parameters

• Population size: 100-500
• Generations: Configurable (typically 1000+)
• Crossover rate: 0.8
• Mutation rate: 0.01-0.1
• Convergence: Monitor fitness over generations

Results

Performance

• 100 cities: Solution within 3-5% of optimal
• 500 cities: Solution within 8-10% of optimal
• Convergence time: Seconds to minutes (depends on config)

Comparison to Baselines

Method	Time	Quality	Scalability
Brute Force	Exponential	Optimal	Poor
Nearest Neighbor	Fast	20-30%	Good
GA	Moderate	3-8%	Excellent
Simulated Annealing	Slow	2-5%	Good

Applications

• Logistics & route optimization
• Manufacturing (job scheduling)
• Telecommunications (network design)
• Drone delivery path planning

Technical Details

• Encoding: Permutation (tour sequence)
• Fitness: Inverse of total distance
• Parent selection: Tournament (k=3)
• Crossover: Order-1 (OX) crossover
• Mutation: Swap or reverse segments

Files

• genetic_algorithm_tsp.py - Main GA implementation
• tsp_analysis.ipynb - Performance analysis and visualization
• benchmark.py - Comparison with other algorithms

How to Use

from genetic_algorithm_tsp import GeneticAlgorithmTSP

ga = GeneticAlgorithmTSP(cities, population_size=200, generations=1000)
best_tour, best_distance = ga.solve()
ga.plot_convergence()

---

Full analysis in tsp_analysis.ipynb