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