Edge crossover

Q: How deeply does Optimization Algorithms: AI techniques for design, planning, and control problems cover edge crossover?

Explains edge tables, initialization, shared-edge preference, shortest-edge-list selection, and completion, without providing implementation code.

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

A permutation crossover operator that constructs offspring by preserving adjacency and connectivity information from parent permutations.

Edge crossover (EC) is a permutation crossover operator that builds offspring by preserving connectivity and adjacency information from two parent chromosomes. It is useful when relationships between neighboring elements matter, such as city sequences in a travelling-salesperson problem. section 8.3.1

A practical EC procedure is:

Construct an edge table or adjacency list by recording neighboring elements in both parents. section 8.3.1
Start the offspring with an arbitrary element from one parent. section 8.3.1
Prefer a shared edge; otherwise select from the parent with the shortest current edge list, avoiding elements already used. section 8.3.1
Repeat the selection until the offspring permutation is complete. section 8.3.1

Eight-city example

For P1 = [1,2,3,4,5,6,7,8] and P2 = [1,6,7,8,5,2,4,3], the edge table records each city’s neighbors and marks common edges. EC uses those shared connections first, then applies the shortest-edge-list heuristic to complete the child. section 8.3.1

Algorithm 8.2 Edge crossover (EC)

Input: two parent P1 and P2
Output: offspring C
1. Construct an edge table.
2. Start by selecting an arbitrary element from one of the parents as the starting point for the offspring.
3. For the current element in the offspring, compare its edges.
4. If an edge is common in both parents, choose that as the next element in the offspring.
5. If there is no common edge or the common edge is already in the offspring, choose the next element from the parent with the shortest edge list.
6. Repeat until the offspring is complete.
7. Return C

Browse the stepwise edge-crossover algorithm. section 8.3.1

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

Cover of Optimization Algorithms: AI techniques for design, planning, and control problems

liveBook manning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

adjacency listuses · An adjacency list is a graph representation that associates each vertex with a collection of its neighboring vertices or incident edges.
crossoverkind of · Crossover is an evolutionary recombination technique that combines material from parent candidate solutions to produce one or more offspring.
evolutionary computationused by · Evolutionary computation is a family of search and optimization methods that iteratively improve candidate solutions through variation and selection inspired by biological evolution.
order crossoveralternative to · Order crossover is a permutation-preserving genetic operator that combines parent sequences while retaining each required element exactly once and preserving selected relative order.

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.