Introduction

Partially Mapped Crossover (PMX) is a recombination operator originally designed for problems like the Travelling Salesman Problem (TSP). It generates offspring by combining genetic material from two parent solutions while preserving order constraints.

PMX is one of the most commonly used crossover operators for permutation-encoded chromosomes. Its key principle is to maintain the relative arrangement of genes from one parent while introducing variation.

Algorithm

Here is the PMX algorithm implemented in Python (requires Python ≥ 3.5):

def pmx(parent1, parent2):
    cut1, cut2 = sorted(random.sample(range(len(parent1)+1), 2))

    offspring = [0] * len(parent1)

    # Copy the middle section from `parent1`
    offspring[cut1:cut2] = parent1[cut1:cut2]

    # Copy the rest from `parent2`, resolving conflicts
    for i in (*range(0,cut1), *range(cut2,len(parent1))):
        candidate = parent2[i]
        while candidate in parent1[cut1:cut2]:  # handle successive mappings
            candidate = parent2[parent1.index(candidate)]
        offspring[i] = candidate

    return offspring

PMX operates in several steps:

1. Selection of crossover points

   Two random crossover points divide the parents' chromosomes into three segments: left, middle, and right.

2. Copying the middle segment

   The middle segment from the first parent is copied directly into the offspring, ensuring partial inheritance.

3. Mapping relationships

   A mapping relationship is established to replace conflicting genes in the remaining segments.

4. Legalizing the offspring

   The mapping is used to resolve conflicts, ensuring a valid permutation in the final offspring.

Step-by-step example

To illustrate PMX, consider two parent chromosomes:

• Parent 1: [1, 2, 3, 4, 5, 6, 7, 8, 9]
• Parent 2: [5, 4, 6, 9, 2, 1, 7, 8, 3]
• Crossover points2 and 6

Parent1 [1, 2 | 3, 4, 5, 6 | 7, 8, 9]
Parent2 [5, 4 | 6, 9, 2, 1 | 7, 8, 3]

Offspring at step...
1. [?, ? | 3, 4, 5, 6 | ?, ?, ?] get middle section from Parent 1
2. [2, ? | 3, 4, 5, 6 | ?, ?, ?] cannot keep 5 (already in the middle section), replacing it
3. [2, 9 | 3, 4, 5, 6 | ?, ?, ?] cannot keep 4, replacing it
4. [2, 9 | 3, 4, 5, 6 | 7, ?, ?] keep 7 (not in the middle section)
5. [2, 9 | 3, 4, 5, 6 | 7, 8, ?] keep 8
6. [2, 9 | 3, 4, 5, 6 | 7, 8, 1] cannot keep 3 and cannot use 6 (which replace
                                 3); using 1 instead

For another example take a look at Wikipedia.

Comparison to traditional one-point crossover

Consider a permutation of cities {1, 2, 3, 4, 5, 6, 7, 8} representing a TSP route.

One-Point Crossover Example

Parent 1: [1, 2, 3 | 4, 5, 6, 7, 8]
Parent 2: [8, 7, 6 | 5, 4, 3, 2, 1]

Offspring: [1, 2, 3 | 5, 4, 3, 2, 1]

⚠ The result is invalid! Cities {3, 2, 1} appear twice, and {6, 7, 8} are missing. While genetic repair can address this, it may disrupt adjacency, resulting ineffective for order-sensitive problems.

PMX Crossover Example

Parent 1: [1, 2, 3 | 4, 5, 6 | 7, 8]
Parent 2: [8, 7, 6 | 5, 4, 3 | 2, 1]

Offspring: [1, 2, 6 | 5, 4, 3 | 7, 8]

All cities are included without duplicates.

Conclusion

Partially Mapped Crossover offers several advantages:

• order preservation: PMX maintains the order of genes across parents, which is crucial for problems like the Travelling Salesman Problem where sequence matters;
• exploration and exploitation: by balancing these two aspects, PMX efficiently finds good or near-optimal solutions.

Post scriptum

The PMX implementation in Ultra closely resembles the Python version but has a few differences:

• the offspring initially copies the entire first parent instead of just the middle section;
• multiple remapping checks are handled at a lower abstraction level, improving efficiency. Additionally, the algorithm assumes that elements of a permutation of length n are in the [0, n[ range. This is not a significant limitation, as any permutation can be easily mapped to the [0, n[ range using simple addition or subtraction.

D_IVECTOR pmx(const D_IVECTOR &lhs, const D_IVECTOR &rhs)
{
  Expects(std::ranges::is_permutation(lhs, rhs));

  const auto ps(lhs.size());
  const auto cut1(random::sup(ps - 1));
  const auto cut2(random::between(cut1 + 1, ps));

  auto ret(lhs);

  const std::vector<std::pair<std::size_t, std::size_t>> segments =
    {{0, cut1}, {cut2, ps}};

  for (const auto &segment : segments)
    for (auto s(segment.first); s < segment.second; ++s)
    {
      auto candidate(rhs[s]);

      auto j(cut1);
      while (j < cut2)
        if (candidate != ret[j])
          ++j;
        else
        {
          candidate = rhs[j];
          j = cut1;
        }

      ret[s] = candidate;
    }

  return ret;
}

References

• Alleles, loci, and the traveling salesman problem by David Goldberg and Rober Lingle (1985).
• Further crossover operators for permutations.