Capitals Tour

Chapter 9 of The Nature of Code, Genetic Algorithms, evolves solutions through selection, crossover, and mutation. The task here is the traveling salesman problem: find the shortest closed tour that visits each city once.

I cast the genetic algorithm as a traveling salesman tour of world capitals, with fitness equal to total great-circle distance on the real globe.

The genome is a visiting order over 22 world capitals, fitness is total great-circle distance, and reproduction uses ordered crossover and swap mutation. On the map, orange is the best tour found so far, faint blue routes are other candidates in the current generation, and a marker walks the best loop so the visit order stays readable. Pacific edges are split at the date line so a short hop across the ocean does not draw a line across Eurasia. The coordinates are a curated static list (not a live countries API).

The traveling salesman problem minimizes closed-tour length \(L(\pi) = \sum_{i=1}^{n} d\!\left(c_{\pi(i)}, c_{\pi(i+1)}\right)\) over permutations \(\pi\) (with \(\pi(n+1) = \pi(1)\)), and is NP-hard: the search space has \((n-1)!/2\) distinct tours. Distances use the haversine formula,

\[ d = 2R\,\arcsin\sqrt{\sin^2\tfrac{\Delta\varphi}{2} + \cos\varphi_1\cos\varphi_2\,\sin^2\tfrac{\Delta\lambda}{2}}. \]

The genetic algorithm applies ordered crossover to the permutation (a segment from one parent, remaining cities filled from the other), swap mutation, and elitist selection across a fixed population.

Data source: Curated capital coordinates
Endpoint: No live API; curated capital coordinates in data.json.
Access: Public, no key. Loaded from an hourly server-side refresh when possible, with a bundled snapshot fallback, and a live browser fetch only when the API allows CORS. Data window: Curated capital coordinates (static list; pulled Aug 6, 2026 UTC)