liveBook · Manning

Partially mapped crossover

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A permutation crossover operator that combines parent segments while mapping displaced elements to preserve feasible offspring permutations.

Partially mapped crossover (PMX) combines two permutation chromosomes while preserving feasible offspring without duplicate elements. It is useful for permutation-based genetic algorithms, including an 8-city traveling-salesperson example. section 8.3.1

Algorithm 8.1 Partially mapped crossover (PMX)
Input: two parents P1 and P2
Output: two children C1 and C2
1. Initialize: Choose two random crossover points and copy the segment between these two points from parent P1 to child C1 and from the second parent P2 to the second child C2.
2. For each element in the copied segment of C1:
3.   Find the corresponding element in P2's segment. 
4.   If the corresponding element is not already in C1:
5.      Replace the element in C1 at the same position as in P2 with the 
        corresponding element from P2.
6. Fill the remaining positions in the offspring with the elements from the other parent, ensuring that no duplicates are introduced.
7. Repeat steps 2-6 for the second offspring, using P1's segment as the reference.
8. Return C1 and C2.

Follow the PMX procedure: choose crossover points, copy parent segments, resolve displaced elements through positional mappings, fill remaining positions, and repeat for the second child. section 8.3.1

Eight-city permutation

Copy a segment from parent P1 into child C1. For each copied city, find its corresponding city in P2; if that city is absent from C1, place it where the mapped city occurs in P2. Complete the remaining positions from P2 without duplicates. section 8.3.1

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Defines the mapping procedure, illustrates it on eight cities, and provides Python implementation guidance.
Examples
Uses an eight-city TSP mapping example, PMX diagrams, and a Python function that generates two offspring.
What it assumes
Assumes familiarity with permutation-based genetic algorithms and parent chromosomes.
What you can do after
Build it from scratch by implementing segment copying, positional mapping, duplicate resolution, and offspring completion.
How it connects
Connects permutation representation with genetic algorithms, crossover methods, and the traveling salesperson problem.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Also explained in

Compare how 2 books explain partially mapped crossover →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.