Traveling Salesman Problem (TSP): Find the shortest route visiting all cities.

Problem Description

Given a list of cities with x,y coordinates, find the shortest route that visits each city exactly once and returns to the starting city.

This is an NP-hard problem that demonstrates:

• Permutation genomes: Order of cities matters
• Specialized operators: PMX crossover preserves valid permutations
• Local optima: GAs can escape local minima through crossover

Genome Representation

Permutation of city indices:

[0, 3, 1, 4, 2]  # Visit cities in order: 0 -> 3 -> 1 -> 4 -> 2 -> 0

Fitness Evaluation

Fitness = -total_distance (negative so shorter is better)

Usage

iex> Jido.Evolve.Examples.TravelingSalesman.run()
# Evolution progress shown...
# Converges to near-optimal route

Expected Results

Converges to within 5-10% of optimal in 100-300 generations, demonstrating how PMX crossover combines good route segments.