Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 36 ยท Crossover and Mutation

Crossover for Permutations: OX, PMX, Cycle and Edge

Learn permutation crossover operators that always produce valid tours: order crossover (OX), partially mapped (PMX), cycle (CX) and edge recombination, with tested Python code.

Permutation encoding showed that cutting two tours and swapping tails produces duplicates and missing cities. The fix is a family of crossover operators designed so that every child is a valid permutation. Each one preserves a different aspect of its parents: relative order, absolute position, or adjacency. Choosing the right one means knowing what your problem cares about.

This lesson implements four classics: order crossover (OX), partially mapped crossover (PMX), cycle crossover (CX) and edge recombination (ER). All are tested for validity below.

Order crossover (OX)

OX preserves the relative order of cities, which suits scheduling and the TSP.

  1. Pick two cut points in parent 1 and copy the segment between them to the child, in place.
  2. Starting just after the second cut, walk through parent 2 (wrapping around) and fill the remaining child slots with the cities not yet used, in the order they appear in parent 2.

A simpler variant, used in the code below, drops the remaining cities in parent-2 order left to right after the segment is removed. Both preserve the segment and parent 2's relative order.

Partially mapped crossover (PMX)

PMX preserves absolute positions as far as possible, which suits assignment problems.

  1. Copy a segment from parent 1 into the child.
  2. For each city in the same segment of parent 2 that is not already in the child, follow the mapping (the pair "parent 1 city at this position, parent 2 city at this position") until you find a free position outside the segment, and place the city there.
  3. Fill any remaining slots directly from parent 2.

Cycle crossover (CX)

CX preserves the absolute position of every city from one of the parents: each city in the child sits at the same index it had in one of the parents. It decomposes the permutation into cycles (a position in parent 1, the city at that position in parent 2, the position where parent 1 holds that city, and so on). Alternate cycles come from alternate parents.

Edge recombination (ER)

ER preserves adjacency, which is exactly what matters in the TSP. It builds an edge table: for each city, the set of cities adjacent to it in either parent. Then it builds the child by repeatedly moving to the neighbor that has the fewest remaining neighbors (a heuristic that avoids stranding cities), breaking ties randomly. It inherits about 95 % of its edges from the parents.

Python OX, PMX, CX and edge recombination

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.

Each child is a valid permutation, including the random stress tests. The four operators produce visibly different children from the same parents, which is expected because they preserve different properties.

Which operator preserves what?

Operator Preserves Typical problems
OX Relative order TSP, scheduling, sequencing
PMX Absolute positions (mostly) Assignment, scheduling with slot constraints
CX Exact positions from one parent per cycle Position-sensitive problems; can copy a parent
Edge recombination Adjacency (edges) TSP, routing
Position-based, order-based Some positions/order from a mask Scheduling

CX has a quirk: if the permutations form a single cycle, the child is a copy of one parent. It needs diverse parents.

Comparing the operators on a TSP

The experiment below runs the same GA with three operators on a random 25-city tour. Only the crossover changes. Shorter final tours are better.

Python TSP: OX versus PMX versus edge recombination

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.

In this run edge recombination wins clearly (about 400 against 416 to 479 for the others), because the TSP rewards good edges and ER is the only operator that inherits edges deliberately. OX and PMX land in the same range, with high variance between runs. Your numbers will differ with other seeds and budgets, so repeat such comparisons many times before drawing conclusions.

Practical advice

  • Start with OX plus an inversion mutation for TSP-like problems. It is simple and strong.
  • Try edge recombination if tours matter and you can afford a slower crossover.
  • Use PMX or CX for assignment-type problems where where an item sits is the point.
  • For routing with capacity constraints, crossover usually runs on a giant tour that is split by a decoder; see repair and decoders.
  • Always unit test your operators: generate thousands of random parents and assert each child is valid, like the stress test above. A subtle bug that sometimes yields a duplicate corrupts a whole run.

Match the operator to the problem

Order matters OX for sequences
Neighbors matter Edge recombination for tours
Slots matter PMX or cycle for assignment

Test every operator with a validity stress test.

1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does order crossover (OX) mainly preserve?

    OX copies a segment from one parent and fills the rest in the order cities appear in the other parent, so relative order is inherited.
  2. 2. Which operator is built around an edge table?

    Edge recombination records which cities are adjacent in either parent and builds a child from those edges, which suits the TSP.
  3. 3. Why does cycle crossover sometimes copy a parent?

    Cycle crossover alternates cycles between parents, so one big cycle means one parent is copied entirely.
  4. 4. How can you make sure your own permutation crossover is correct?

    A rare duplicate or missing city silently corrupts the search, so automated validity tests are cheap protection.

Summary

  • Permutation crossover must keep each item exactly once.
  • OX preserves relative order, PMX and CX preserve positions, edge recombination preserves adjacency.
  • Match the operator to what your problem rewards: order, positions or neighbors.
  • OX with inversion mutation is a strong default for TSP-style problems.
  • Validate operators with randomized tests.

Next: Mutation Operators