The loop
Start with a population of random routes. Then repeat, a few hundred times: pick parents, favouring short routes; combine each pair into two children; occasionally mutate a child; let the children replace the parents entirely.
With elitism switched on, the best few routes are copied into the next generation untouched, so the best-ever route can never get worse. Without it, a good route can be lost to bad luck — which is why the convergence curve in the demo sometimes ticks back up.
Storing and scoring a route
A route is a list of city numbers in visiting order — [2, 3, 1, 5, 4] means start at city 2 and end at city 4, then drive back to 2 to close the loop. Its score is simply the total distance of that closed loop, so lower is better.
The sum is written so that index -1 wraps around to the last city, which picks up the drive home without a special case:
fitness = 0
for i in range(len(self.representation)):
fitness += distance_matrix[self.representation[i - 1]][self.representation[i]]Here is the constraint that makes this problem interesting. Every route must contain every city exactly once. The textbook way of combining two solutions — cut both in half and swap the halves — breaks that immediately: you get children that visit some cities twice and others never. Every operator below exists to work around it.
Combining two routes
Three ways to merge two parent routes into a child that is still a valid route. In each diagram, solid teal is kept from parent 1 and dashed is brought in from parent 2.
Cycle crossover
Follow the loop that positions form between the two parents — here positions 1, 2, 3, 4 and 8 — and take those from one parent. Every remaining position comes from the other. Each city keeps a position it held in one of its parents.
Partially mapped crossover (PMX)
Copy a slice from one parent, place the displaced cities where the parent-to-parent mapping says they belong, and fill what is left from the second parent. Preserves absolute position more than order.
Order 1 crossover
Keep a slice from one parent and fill the gaps with the remaining cities in the order the other parent lists them. Preserves relative order, which is what actually matters in a route.
Mutation
Swap exchanges two cities. Inversion reverses a run, which on a map undoes exactly one crossing. Shuffle randomises a run. All three keep the route valid; only inversion reliably helps.
Every sequence above was produced by running this repository's own crossover.py and mutation.py with the cut points pinned — these are the operators' real outputs, not illustrations of them.
Choosing parents
- Tournament
- Pick 10 routes at random and keep the shortest. Simple, and the strongest of the three in every test here — it only cares which route is shorter, never by how much.
- Ranking
- Sort the population and give each route a chance proportional to its rank. Also immune to how close the lengths are, but weaker in practice than tournament.
- Fitness proportionate
- Give each route a chance proportional to how short it is. Sounds like the obvious choice and performs the worst — once the population converges, every route is a similar length, so every route gets a similar chance and the selection pressure quietly vanishes.