Crossover Operators

Mutation Operators

**Crossover Technique: Edge Recombination**

Parent 1: A B F E D G C CHILD = Empty Chromosome |

Edge Recombination ExampleGiven our parents:
Parent 1: A B F E D G C 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 DiscussionThe 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