Artificial Intelligence Travelling Salesman Validated

Travelling Salesman

Finding the shortest route through all cities

Statistics

Generation: 0
Best: -
NN Baseline: -
Confidence: -

Convergence

Controls

Options

Algorithm
Cities
Count
Population
Mutation
Speed
Adaptive
Labels

Travelling Salesman Problem

Find the shortest route visiting all cities exactly once and returning to the starting point. This is an NP-hard combinatorial optimization problem.

Genetic Algorithm Approach:

Encoding: Permutation of city indices (each gene is a city order)
Selection: Tournament selection with 3 candidates
Crossover: Order Crossover (OX) preserves relative city order
Mutation: Swap (exchange two cities) + 2-opt (reverse segment)
Elitism: Top 5 individuals preserved each generation

Adaptive Mutation: When enabled, mutation rate increases when progress stalls (escaping local optima) and decreases when rapidly improving (fine-tuning good solutions).

Nearest Neighbor Baseline: A greedy heuristic that always visits the closest unvisited city. Provides a baseline to measure GA performance.

_claude

Travelling Salesman Problem (TSP)

Interactive demonstration of solving TSP using a genetic algorithm.

Features

City Types: Random, circle, clusters, or manual placement
Top N Routes: Visualize multiple candidate solutions
Convergence Graph: Track distance improvement over generations
Adaptive Mutation: Automatic rate adjustment based on progress
NN Baseline: Compare with nearest neighbor heuristic
Speed Control: Adjust generations per frame
City Labels: Toggle numbered city display

Technical Details

Population: 100 individuals (configurable)
Selection: Tournament (3 candidates)
Crossover: Order Crossover (OX) - 90% rate
Mutation: Swap + 2-opt - 15% rate (configurable)
Elitism: Top 5 preserved

Keyboard Shortcuts

Space: Start/Pause
R: Reset