Edge Recombination Crossover Operator Tutorial

Crossover Operators

Mutation Operators

Crossover Technique: Edge Recombination

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

Edge Recombination Example
Given our parents:

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

Edge Recombination Discussion
The child that we produced introduced only one new edge: A to D. This algorithm makes excellent use of existing edges and is much less likely to introduce stray edges during crossover.

        'This one is slow, very slow. By generation it performs very well, but is about 200 times slower than single point
        Public Sub Permutation_EdgeRecombination(ByRef Child1 As PChromo, ByRef parent1 As PChromo, ByRef parent2 As PChromo)

            'Setup Neighbor List
            Dim NeighborList(AlleleCount) As Hashtable
            For j As Integer = 0 To AlleleCount - 1
                NeighborList(j) = New Hashtable
            Next

            'Add entries for first and last elements of parent1:
            NeighborList(parent1.Alleles(0)).Add(parent1.Alleles(1), Nothing)
            NeighborList(parent1.Alleles(0)).Add(parent1.Alleles(AlleleCount - 1), Nothing)
            NeighborList(parent1.Alleles(AlleleCount - 1)).Add(parent1.Alleles(0), Nothing)
            NeighborList(parent1.Alleles(AlleleCount - 1)).Add(parent1.Alleles(AlleleCount - 2), Nothing)

            'Add entries for first and last elements of parent2:
            If Not NeighborList(parent2.Alleles(0)).Contains(parent2.Alleles(1)) Then NeighborList(parent2.Alleles(0)).Add(parent2.Alleles(1), Nothing)
            If Not NeighborList(parent2.Alleles(0)).Contains(parent2.Alleles(AlleleCount - 1)) Then NeighborList(parent2.Alleles(0)).Add(parent2.Alleles(AlleleCount - 1), Nothing)
            If Not NeighborList(parent2.Alleles(AlleleCount - 1)).Contains(parent2.Alleles(0)) Then NeighborList(parent2.Alleles(AlleleCount - 1)).Add(parent2.Alleles(0), Nothing)
            If Not NeighborList(parent2.Alleles(AlleleCount - 1)).Contains(parent2.Alleles(AlleleCount - 2)) Then NeighborList(parent2.Alleles(AlleleCount - 1)).Add(parent2.Alleles(AlleleCount - 2), Nothing)

            'Add entries for the rest of parent1 and parent2:
            For j As Integer = 1 To AlleleCount - 2
                If Not NeighborList(parent1.Alleles(j)).Contains(parent1.Alleles(j - 1)) Then NeighborList(parent1.Alleles(j)).Add(parent1.Alleles(j - 1), Nothing)
                If Not NeighborList(parent1.Alleles(j)).Contains(parent1.Alleles(j + 1)) Then NeighborList(parent1.Alleles(j)).Add(parent1.Alleles(j + 1), Nothing)
                If Not NeighborList(parent2.Alleles(j)).Contains(parent2.Alleles(j - 1)) Then NeighborList(parent2.Alleles(j)).Add(parent2.Alleles(j - 1), Nothing)
                If Not NeighborList(parent2.Alleles(j)).Contains(parent2.Alleles(j + 1)) Then NeighborList(parent2.Alleles(j)).Add(parent2.Alleles(j + 1), Nothing)
            Next

            'ValuesLeft starts full of all the nodes, and as nodes are added to the child, they are removed from this. It's a way of tracking which ones are available for the child
            Dim ValuesLeft As New Collection
            For j As Integer = 0 To AlleleCount - 1
                ValuesLeft.Add(parent1.Alleles(j), parent1.Alleles(j))
            Next

            'Typically you would select the first value of a random parent, but i changed it to do the first parent always.
            'This way, we can crossover parents1 & 2, then parents 2 & 1 to get 2 diff children (usually)
            Dim ChildIndex As Integer = 0
            Dim N As Integer
            N = parent1.Alleles(0)

            Dim X As String = N
            ValuesLeft.Remove(X)

            'Until the child is full:
            While True
                Child1.Alleles(ChildIndex) = N : ChildIndex += 1
                If ChildIndex = AlleleCount Then Exit While

                'remove N from all neighbor lists
                For j As Integer = 0 To AlleleCount - 1
                    NeighborList(j).Remove(N)
                Next

                'Determine which of N's neighbors has fewest children
                Dim Temp As New Collection
                Dim DE As DictionaryEntry
                Dim Min As Integer = 9999
                For Each DE In NeighborList(N)
                    If NeighborList(DE.Key).Count < Min Then Min = NeighborList(DE.Key).Count
                Next

                'Determine how many neighbors of N have this minimum number of neighbors
                Dim Count As Integer = 0
                For Each DE In NeighborList(N)
                    If NeighborList(DE.Key).Count = Min Then
                        Count += 1
                    End If
                Next

                'If there is none, pick a random one from the values that are left
                Dim WasThere As Boolean = False
                If Count = 0 Then
                    WasThere = True
                    Dim Pick As Integer = RAND.Next(0, ValuesLeft.Count)
                    N = ValuesLeft.Item(Pick + 1)
                    ValuesLeft.Remove(Pick + 1)
                Else
                    'If there is one, then N = that one. 
                    'If there is more than one, pick a random one 
                    'This loop accomplishes both
                    Dim Selection As Integer = RAND.Next(0, Count)
                    For Each DE In NeighborList(N)
                        If NeighborList(DE.Key).Count = Min Then
                            If Selection = 0 Then
                                N = DE.Key
                                Dim s As String = DE.Key
                                ValuesLeft.Remove(s)
                                Exit For
                            Else
                                Selection -= 1
                            End If
                        End If
                    Next
                End If


                'Now that the new N is selected, loop again!
            End While


            'Check kid for duplicates
            Dim H As New Hashtable
            For j As Integer = 0 To AlleleCount - 1
                If H.Contains(Child1.Alleles(j)) Then
                    Dim ii As Integer = 45
                Else
                    H.Add(Child1.Alleles(j), Nothing)
                End If
            Next

        End Sub