Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 36 ยท Applications and Tuning

A Genetic Algorithm for the Traveling Salesman Problem

Solve the traveling salesman problem with a genetic algorithm in Python. Permutation encoding, order crossover, swap and inversion mutation, and a 2-opt memetic upgrade.

The traveling salesman problem (TSP) asks: given a list of cities, what is the shortest round trip that visits each city exactly once? With 20 cities there are about 10^17 possible tours. It is the poster child of combinatorial optimization, and a classic application of genetic algorithms. The representation is a permutation: the chromosome [3, 0, 4, 1, 2] means "visit city 3, then 0, then 4, then 1, then 2, then return to 3".

Permutations need special operators. If you cut two permutations in the middle and swap the tails (one-point crossover), the children contain duplicate cities and miss others. This lesson introduces permutation-safe operators and builds a working TSP solver.

Permutation crossover: order crossover (OX)

Order crossover keeps a slice from the first parent and fills the rest in the order that cities appear in the second parent.

  1. Choose two cut points. Copy the slice between them from parent 1 into the child at the same positions.
  2. Starting after the second cut in parent 2, go around the list and write each city that is not yet in the child into the free positions, wrapping around.
TEXT
parent 1:  [0 1 | 2 3 4 | 5 6 7]      slice = [2 3 4]
parent 2:  [3 7 1 0 6 2 5 4]         (order after the cut: 2 5 4 3 7 1 0 6)
child   :  [? ? 2 3 4 ? ? ?]          fill remaining in that order: 5 7 1 0 6
        ->  [0 6 2 3 4 5 7 1]  (the free slots 5, 6, 7, 0, 1 receive 5, 7, 1, 0, 6)

Other permutation crossovers exist: PMX (partially mapped), cycle crossover and edge recombination, which preserves edges (neighbouring pairs), the thing that actually matters for a tour.

Permutation mutation

  • Swap: exchange two random cities.
  • Insertion: remove a city and insert it elsewhere.
  • Inversion (2-opt move): reverse a random segment. This is the most useful for TSP because it changes only two edges.
  • Scramble: shuffle a random segment.
Python A TSP genetic algorithm with OX and inversion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will see the best length drop fast in the first 50 generations and then slowly. A pure GA gets close to the optimum but often leaves a few crossing edges (two edges that cross can always be shortened). That suggests a hybrid.

The memetic upgrade: GA plus 2-opt

2-opt local search repeatedly looks for two edges that can be replaced by two shorter ones (by reversing the segment between them), and stops when no such move helps. Applying 2-opt to every child turns the GA into a memetic algorithm. The population then consists only of 2-opt local optima, and the GA's job is to combine and perturb them. For TSP this usually matches or beats the plain GA with far fewer evaluations.

Python Add a 2-opt local search to every child

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With only 20 individuals and 25 generations, the memetic version typically matches or beats the plain GA that used 80 individuals and 150 generations, using far fewer evaluations. Local search is a big part of every state-of-the-art TSP heuristic.

Beyond the basic TSP

  • Asymmetric TSP: distances differ by direction. Use a full matrix; nothing else changes.
  • Vehicle routing (VRP): several vehicles with capacities. Encode a permutation and split it into routes with a decoder (see Repair and Decoders).
  • Time windows: add penalties for late arrival (penalty methods).
  • Large instances (thousands of cities): specialized methods like Lin-Kernighan and Concorde are far stronger, but a memetic GA with edge-recombination crossover remains a good general framework.

Common mistakes

  • Using one-point crossover on permutations, which creates invalid tours.
  • Ignoring symmetry. A tour and its reverse, or any rotation of it, are the same. This is harmless but good to remember when counting unique solutions.
  • Slow distance calculation. Precompute the distance matrix once.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can't you use ordinary one-point crossover on tour permutations?

    Swapping tails of two permutations does not preserve 'each city exactly once'.
  2. 2. In order crossover (OX), how are the remaining positions of the child filled?

    OX preserves the relative order of cities from the second parent.
  3. 3. What does a 2-opt move do?

    It is the standard tour-improvement move that removes edge crossings.
  4. 4. Why does adding 2-opt to every child (a memetic GA) help so much?

    Global recombination plus local refinement is more powerful than either alone.

Summary

  • TSP chromosomes are permutations of the cities.
  • Use permutation-safe operators: OX (or PMX, edge recombination) and inversion, swap or insertion mutation.
  • Plain GAs get close; adding 2-opt local search (a memetic GA) gets much closer with far fewer evaluations.
  • Variants such as VRP and time windows reuse the same machinery with decoders and penalties.
  • Precompute the distance matrix and always validate that tours are legal.

Next: Project: Knapsack Optimizer