Edge recombination operator
Encyclopedia
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 non-repeating gene sequences is needed such as for the travelling salesman problem
.
, 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 matrix
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 matrix
, 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:
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}.
Note that the only edge introduced in ABDFCE is AE.
, 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 severely inhibit an otherwise good solution. The optimal route in the examples is ABDFEC, but swapping A for F turns 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 the indirect representation spends 150 generations on. Partially mapped crossover (PMX) ranks between ERO and indirect one-point crossover, with 80 generations for this particular target.
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
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
Crossover (genetic algorithm)
In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. It is analogous to reproduction and biological crossover, upon which genetic algorithms are based...
in genetic algorithms when a genotype with non-repeating gene sequences is needed such as for the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
.
Algorithm
ERO is based on an adjacency matrixAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
, 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 matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
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
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
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 matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
, 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:
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.
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 crossoverCrossover (genetic algorithm)
In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. It is analogous to reproduction and biological crossover, upon which genetic algorithms are based...
, 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 severely inhibit an otherwise good solution. The optimal route in the examples is ABDFEC, but swapping A for F turns 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 the indirect representation spends 150 generations on. Partially mapped crossover (PMX) ranks between ERO and indirect one-point crossover, with 80 generations for this particular target.
Implementations
- "Edge Recombination Operator" (Python)