Watch it run

• The map, left. Each dot is a city; the line is the best route found so far. The faint line behind it is the route it just beat, so improvements show up as movement.
• The curve, right. The length of the best route in each generation. The dashed amber line is the shortest route that is mathematically possible for this problem — the curve should fall toward it and flatten out short of it.
• Above target. How far the current best route is from that proven optimum, as a percentage. Getting under 2% is good going for a method this simple.

Things worth trying

• Set selection to fitness proportionate and watch the curve stall. Once every route is a similar length, picking parents in proportion to their length is barely different from picking at random.
• Set mutation to shuffle or swap. Inversion is the only mutation whose effect on a map is geometric — reversing a run of stops removes exactly one crossing.
• Tick elitism. The curve stops going back up, because the best routes are copied into the next generation untouched.
• Switch the distance table to as stored, on swiss42. The route length drops below the optimum line, which should be impossible — that is the bug.

The map has no real coordinates behind it. These benchmark problems ship as tables of distances between cities, with no positions, so the layout is reconstructed from the distances alone using classical multidimensional scaling. It is faithful in relative distance, but free to come out rotated or mirrored against the real map.