Genetic Algorithm — Traveling Salesman Problem Solver

A metaheuristic optimization engine that uses a Genetic Algorithm (GA) to find near-optimal solutions to the Traveling Salesman Problem. Built in C# on .NET Core 3.1.

How It Works

The algorithm evolves a population of candidate routes over many generations. Each generation applies selection pressure, recombination, and mutation to produce progressively shorter tours through a set of cities.

Initialize random population
    │
    ▼
┌─────────────────────────┐
│  Evaluate fitness       │ ◄── Euclidean or Geographic distance
│  Select parents         │ ◄── Tournament selection
│  Crossover              │ ◄── Order crossover (OX)
│  Mutate                 │ ◄── Swap / Inverse mutation
│  Form next generation   │
└────────┬────────────────┘
         │ repeat for N generations
         ▼
   Best route found

Operators

Stage	Method	Description
Selection	Tournament	Picks k random individuals, keeps the fittest
Crossover	Order (OX)	Preserves a subsequence from one parent, fills remaining positions from the other while maintaining order
Mutation	Swap	Randomly swaps two cities in a route
Mutation	Inverse	Reverses a segment of the route
Baseline	Greedy	Nearest-neighbor heuristic starting from each city — used as a comparison

Distance Metrics

• EUC_2D — standard Euclidean distance between 2D coordinates
• GEO — geographic (great-circle) distance using latitude/longitude

Benchmark Datasets

Includes instances from the Augerat CVRP benchmark set in TSPLIB format:

Instance	Cities	Vehicle Capacity
A-n32-k5	31	varies
A-n37-k5	36	varies
A-n39-k5	38	varies
A-n45-k6	44	varies
A-n54-k7	53	varies
A-n60-k9	59	varies

Configuration

All parameters are set in GA/Parameters/parameters.txt:

PopSize:100          # Population size
Pm:0,1               # Mutation probability
Px:0,7               # Crossover probability
Tour:5               # Tournament size
SelectionA:0         # 0 = Tournament
CrossingA:0          # 0 = Ordered (OX)
MutationA:0          # 0 = Swap, 1 = Inverse
GenNum:100           # Number of generations
isGreedy:true        # true = Greedy baseline, false = Genetic Algorithm

Running

dotnet run --project GA/GA.csproj

The console app loads all benchmark instances from EA_DATA/, lets you pick one, then runs the configured algorithm.

Project Structure

GA/
├── Models/
│   ├── Algorithms/
│   │   ├── Genetic.cs         # GA implementation (selection → crossover → mutation loop)
│   │   └── Greedy.cs          # Nearest-neighbor heuristic
│   ├── Crossings/
│   │   └── Ordered.cs         # Order crossover (OX)
│   ├── Mutations/
│   │   ├── Swap.cs            # Swap mutation
│   │   └── Inverse.cs         # Inverse mutation
│   ├── Selections/
│   │   └── Tournament.cs      # Tournament selection
│   ├── Agglomeration.cs       # City collection (parsed from TSPLIB files)
│   ├── Town.cs                # Single city with coordinates and demand
│   ├── Population.cs          # Population initialization and shuffling
│   └── Parameters.cs          # Algorithm configuration model
├── Services/
│   ├── AlgorithmCourse.cs     # Orchestrates evaluation pipeline
│   ├── EvaluationFunction.cs  # Fitness: total tour distance (EUC_2D / GEO)
│   ├── FileService.cs         # TSPLIB parser and parameter loader
│   └── Extensions.cs          # Shuffle, swap, splice utilities
├── EA_DATA/                   # TSPLIB benchmark instances
└── Parameters/
    └── parameters.txt         # Runtime configuration

Tech

• C# / .NET Core 3.1
• Console application
• No external dependencies