Edge recombination operator

From Wikipedia, the free encyclopedia

Contents 1 General Description 2 Algorithm 3 Comparison with other operators 4 References

[edit] 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.

[edit] Algorithm

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

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}.
• AB. The smallest sets of C and D are C={E,F} and D={E,F}. We randomly select D.
• ABD. Smallest are E={C,F}, F={C,E}. We pick F.
• ABDF. C={E}, E={C}. We pick C.
• ABDFC. The smallest set is E={}.
• ABDFCE. The length of the child is now the same as the parent, so we are done.

Note that the only edge introduced in ABDFCE is AE.

[edit] Comparison with other operators

If one were to use an indirect representation for these parents (where each number in turn indexes and removes an element from an initially sorted set of nodes) and cross them with simple one-point crossover, one would get the following:

The parents:
31|1111 (CABDEF)
11|1211 (ABCEFD)

The children:
11|1111 (ABCDEF)
31|1211 (ABEDFC)

Both children introduce the edges CD and FA.

The reason why frequent edge introduction is a bad thing in these kinds of problem is that very few of the edges tend to be usable and many of them will severely inhibit an otherwise good solution. The optimal route in the examples is ABDFEC, but swapping A for F will turn it from optimal to far below an average random guess.

The difference between ERO and the indirect one-point crossover can be seen in the diagram. It takes ERO 25 generations of 500 individuals to reach 80% of the optimal path in a 29 point data set, something on which the indirect representation spends 150 generations. Partially mapped crossover (PMX) ranks between ERO and indirect one-point crossover, with 80 generations for this particular target.

[edit] References

Whitley, Darrell; Thimothy Starkweather, D'Ann Fuquay (1989). "Scheduling problems and traveling salesman". Scheduling problems and traveling salesman: The genetic edge recombination operator: 133-140.