Why this is hard,
and why evolution helps

The Traveling Salesperson Problem is NP-hard. Informally: no algorithm is known that always finds the exact best route in time that grows sensibly with the number of cities, and most researchers believe no such algorithm exists.

The trouble is combinatorial. For n cities there are (n−1)! / 2 distinct round trips — divide by 2 because a route and its reverse have the same length, and fix the starting city because a loop has no natural beginning. That factorial is brutal:

Note what is not hard: checking a route. Given one, you add up 42 numbers. Problems where verifying is easy but finding is hard are exactly the NP class, and TSP is among the hardest of them.

Exact methods

Branch-and-bound, cutting planes, integer programming. They return the provably optimal route and a certificate that no better one exists. Modern solvers handle surprisingly large instances — but the worst case is still exponential, and you cannot bound the runtime in advance.

Heuristics

Fast, specific rules. Nearest neighbour builds a route by always driving to the closest unvisited city; 2-opt repeatedly removes crossings. Quick and often good, but they stop at the first solution they cannot improve — a local optimum.

Metaheuristics

Strategies that sit above heuristics and manage the search itself: simulated annealing, ant colony optimization, and genetic algorithms. They deliberately accept worse solutions sometimes, so they can climb out of a local optimum. That is what this project uses.

Genetic algorithms were formalised by John Holland in the 1970s. The idea is to borrow the mechanism of natural selection rather than its biology: keep a population of candidate solutions, let the better ones reproduce more often, mix their structure together, and add occasional random change.

Four pieces have to be chosen for any problem, and this project varies all of them:

• Representation — how a solution is written down. Here, a route is a permutation of city numbers.
• Fitness — a single number scoring a solution. Here, total route length, minimised.
• Selection — how parents are chosen. This controls selection pressure: how strongly the search favours what is already good.
• Variation — crossover recombines two parents, mutation perturbs one. Crossover exploits structure that already exists; mutation explores structure that does not.

Exploration versus exploitation

Every search faces the same trade-off. Exploitation means refining what already works — too much and the population collapses onto one mediocre route and stops improving, which is premature convergence. Exploration means trying genuinely new structure — too much and the search becomes a random walk that never settles.

Almost every knob in the demo is really this trade-off in disguise. High mutation rate, weak selection, and large populations push toward exploration. Elitism, tournament selection and low mutation push toward exploitation. The failure of fitness proportionate selection is a pure case: as the population converges, its selection pressure collapses toward zero and the search stops being a search.

The usual intuition for why crossover works is the building block hypothesis: short, useful fragments of a solution get combined into better solutions. The catch is that this only works if your operators actually preserve the fragments that matter.

For a route, the meaningful fragment is not "city 7 sits in position 3". It is "the van drives from city 7 to city 12" — an edge, a piece of adjacency. A good sub-path is a building block; an absolute position is almost meaningless, because rotating an entire route changes every position and leaves the length identical.

This explains the results better than any general theory about genetic algorithms. Order 1 crossover preserves relative order, so it preserves runs of adjacency. Inversion mutation reverses a contiguous run, which keeps every internal edge intact and changes only the two at the ends — geometrically, it removes a single crossing. Swap and shuffle mutation tear up four or more edges at random, which is why they lose.

It also explains why a naive crossover cannot be used at all. Cut two permutations and swap the halves and you get children that visit some cities twice and miss others entirely — not a worse route, but not a route at all. All three crossover operators exist to dodge that.

Worth saying plainly: a genetic algorithm is not the best tool for the Traveling Salesperson Problem. Specialised local search does better. The Lin–Kernighan heuristic and its descendants routinely get within a fraction of a percent on instances with millions of cities, and a plain 2-opt pass with restarts — the check I used to verify the distance data — found the true optimum on all three problems here in seconds.

That is not an argument against the method. It is the No Free Lunch theorem doing its job: averaged over all possible problems, no search algorithm beats any other. Algorithms win by exploiting structure specific to a problem, and Lin–Kernighan wins on TSP because it is built around edges and crossings.

Genetic algorithms earn their place elsewhere — where the objective is a black box you can only sample, where it is noisy or expensive, where the search space is discrete and awkward, or where you want a diverse set of good answers rather than one. Scheduling, circuit layout, hyperparameter search and engineering design all look like that.

TSP is the right problem to learn on precisely because the answer is known. You can measure exactly how far off you are — which is how a one-digit error in the input became visible at all.

• Goldberg — Genetic Algorithms in Search, Optimization and Machine Learning (1989) The standard reference, and the source of the building block framing above.
• TSPLIB The benchmark library the three problems here come from, with proven optimal lengths.
• The Traveling Salesman Problem — University of Waterloo History, record-breaking solutions, and the Concorde exact solver.