Edge recombination operator

General Description

The edge recombination operator (ERO) is an operator that creates a path that is similar to a set of existing paths (parents) by looking at the edges rather than the vertices. The main application of this is for crossover in genetic algorithms when a genotype with ordered genes is needed such as for the travelling salesman problem.

Algorithm

ERO is based on an edge map, which lists the neighbors of each node in any parent.

ERO crossover

For example, in a travelling salesman problem such as the one depicted, the node map for the parents CABDEF and ABCEFD (see illustration) would look like this:

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

Then, to create a path K, the following algorithm is employed:

Let K be the empty list
Let N be the first node of a random parent.

While Length(K) < Length(Parent):
    K := K, N   (append N to K)
    Remove N from all neighbor lists

    If N's neighbor list is non-empty
       then let N* be the neighbor of N with the fewest neighbors in its list (or a random one, should there be multiple)
       else let N* be a randomly chosen node that is not in K

    N := N*

To step through the example, we randomly select a node from the parent starting points, {A, C}.

• () -> A. We remove A from all the neighbor sets, and find that the smallest of B, C and D is B={C,D}.