Edge Recombination Crossover - Genetic Algorithms
This is a crossover techniques for permutation (ordered) chromosomes. It strives to introduce the fewest paths possible. In problems such as the traveling salesman, introducing a stray edge between two nodes is usually very bad for a chromosome's fitness. The idea here is to use as many existing edges, or node-connections, as possible to generate children. Edge Recombination typically out performs PMX and Ordered crossover, but usually takes longer to compute.

The Algorithm:

Parent 1: A B F E D G C
Parent 2: G F A B C D E

Generate Neighbor List:

A: B C F
B: A F C
C: A G B D
D: E G C E
E: F D G
F: B E G A
G: D C E F

CHILD = Empty Chromosome

1. X = the first node from a random parent.
2. While the CHILD chromo isn't full, Loop:
   - Append X to CHILD
   - Remove X from Neighbor Lists

   if X's neighbor list is empty:
      - Z = random node not already in CHILD
   else
      - Determine neighbor of X that has fewest neighbors
      - If there is a tie, randomly choose 1
      - Z = chosen node
   X = Z

Parent 1: A B F E D G C
Parent 2: G F A B C D E

First, we randomly select the first node of a parent.

CHILD: A

Next, after crossing A out from all neighbor lists, we see that B is the least full list. So,

CHILD: A B

Next, after crossing B out from all neighbor lists, F and C both have only 2 neighbors, so we randomly choose between the two:

CHILD: A B F

Next, after crossing F out from all neighbor lists, E is the neighbor of F that has the fewest neighbors.

CHILD: A B F E

Next, after crossing E out from all neighbor lists, D and G both have only 2 neighbors, so we randomly choose between the two:

CHILD: A B F E G

Next, after crossing G out from all neighbor lists, D and C both have only 1 neighbor, so we randomly choose between the two:

CHILD: A B F E G C

Next, after crossing C out from all neighbor lists, C has only one neighbor and it has no neighbors left, so we randomly choose between the nodes that aren't yet included in CHILD. In this case, D is the only one left, so we're done:

CHILD: A B F E G C D