Genetic Algorithm Info

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(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
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