Edge recombination operator

Algorithm

ERO is based on an adjacency lists, 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) is generated by taking the first parent, say, 'ABCEFD' and recording its immediate neighbors, including those that roll around the end of the string.

Therefore;

... -> [A] <-> [B] <-> [C] <-> [E] <-> [F] <-> [D] <- ...

...is converted into the following adjacency list by taking each node in turn, and listing its connected neighbors;

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

With the same operation performed on the second parent (CABDEF), the following is produced:

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

Followed by making a union of these two lists, and ignoring any duplicates. This is as simple as taking the elements of each list and appending them to generate a list of unique link end points. In our example, generating this;

A: B C D = {B,D} ∪ {C,B} B: A C D = {A,C} ∪ {A,D} C: A B E F = {B,E} ∪ {F,A} D: A B E F = {F,A} ∪ {B,E} E: C D F = {C,F} ∪ {D,F} F: C D E = {E,D} ∪ {E,C}

The result is another adjacency list, which stores the links for a network described by all the links in the parents. Note that more than two parents can be employed here to give more diverse links. However, this approach may result in sub-optimal paths.

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

<b id="mwKg">algorithm</b> ero <b id="mwKw">is</b> let <i id="mwLA">K</i> be the empty list let <i id="mwLQ">N</i> be the first node of a random parent. <b id="mwLg">while</b> length(<i id="mwLw">K</i>) < length(Parent) <b id="mwMA">do</b> <i id="mwMQ">K</i> := <i id="mwMg">K</i>, <i id="mwMw">N</i> (append <i id="mwNA">N</i> to <i id="mwNQ">K</i>) Remove <i id="mwNg">N</i> from all neighbor lists <b id="mwNw">if'<i id="mwOA"> </i>N</b>s neighbor list is non-empty <b id="mwOQ">then</b> let <i id="mwOg">N</i>* be the neighbor of <i id="mwOw">N</i> with the fewest neighbors in its list (or a random one, should there be multiple) <b id="mwPA">else</b> let <i id="mwPQ">N</i>* be a randomly chosen node that is not in <i id="mwPg">K</i> <i id="mwPw">N</i> := <i id="mwQA">N</i>*

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.