Crossover Technique: Cycle Crossover
Cycle Crossover Operator
The Cycle Crossover operator identifies a number of so-called cycles between two parent chromosomes. Then, to form Child 1, cycle one is copied from parent 1, cycle 2 from parent 2, cycle 3 from parent 1, and so on. Here's an example:
Parent 1: 8 4 7 3 6 2 5 1 9 0
Parent 2: 0 1 2 3 4 5 6 7 8 9
Cycle 1 Values: 8 9 0 which will be marked Orange.
Cycle 1: We start with the first value in Parent 1 and drop down to the same position in Parent 2. 8 Goes to 0. Then, we look for 0 in Parent 1 and find it at the 10th position where we drop down to 9. Again, we look for this value in Parent 1 and find it in the 9th position and drop down to 8. Since we started with 8, we've completed our cycle.
Parent 1: 8 4 7 3 6 2 5 1 9 0
Parent 2: 0 1 2 3 4 5 6 7 8 9
Cycle 2 Values: 4 1 7 2 5 6 which will be marked Red.
Cycle 2: We start with 4 and drop down to 1. 1 is found in the 8th position in Parent 1 and we drop down to 7. 7 Drops down to 2, 2 Drops down to 5, 5 drops down to 6, and 6 drops down to 4 - Our cycle is complete.
Parent 1: 8 4 7 3 6 2 5 1 9 0
Parent 2: 0 1 2 3 4 5 6 7 8 9
Cycle 3 Value: 3
Cycle 3: The only possible cycle left is of length 1 and contains the value 3.
Filling in the offspring:
Parent 1: 8 4 7 3 6 2 5 1 9 0
Parent 2: 0 1 2 3 4 5 6 7 8 9
Child 1: 8 1 2 3 4 5 6 7 9 0
Child 2: 0 4 7 3 6 2 5 1 8 9
Copy Cycle 1: Cycle 1 values from Parent 1 and copied to Child 1, and values from Parent 2 will be copied to Child 2. Cycle 2 will by different.
Copy Cycle 2: Cycle 2 values from Parent 1 will be copied to Child 2, and values from Parent 1 will be copied to Child 1.
Copy Cycle 3: Cycle 3 is like Cycle 1, Parent 1 goes to Child 1, Parent 2 goes to Child 2.
|
| VB.NET 2008 Source Code: |
Sub Permutation_Cycle(ByRef Child1 As PChromo, ByRef Child2 As PChromo, ByRef Parent1 As PChromo, ByRef Parent2 As PChromo)
'Initialize Flags() to false. These will be used to flag a value of parent1 as 'considered'
Dim Flags(AlleleCount) As Boolean
For j As Integer = 0 To AlleleCount - 1
Flags(j) = False
Next
'We need fast lookups of a parent2's index, given a value -- so build a hash table
' entry key & value2 will house the allele value
' index2 will hold the index of the allele
' value1 will hold the value of parent1 at index2
Dim HT1 As New Hashtable
Dim TempPair As New Double_Index_Value_Pair
For j As Integer = 0 To AlleleCount - 1
TempPair = New Double_Index_Value_Pair
TempPair.value2 = Parent2.Alleles(j)
TempPair.index2 = j
TempPair.value1 = Parent1.Alleles(j)
HT1.Add(Parent2.Alleles(j), TempPair)
Next
'1 Identify all cycles
Dim Cycles As New Collection
Dim CycleStart As Integer 'refers to parent 1 index of cycle start
For j As Integer = 0 To AlleleCount - 1
Dim TempCycle As New Collection
'If this value isn't already a part of another cycle:
If Not Flags(j) Then
'A. Record cycle start index of parent1
CycleStart = j
'B. Advance one step in the cycle
TempPair = HT1(Parent1.Alleles(CycleStart))
TempCycle.Add(TempPair)
Flags(TempPair.index2) = True
'C. Advance until the cycle is complete
While Not TempPair.index2 = CycleStart
'Advance one more step in the cycle
TempPair = HT1(Parent1.Alleles(TempPair.index2))
TempCycle.Add(TempPair)
Flags(TempPair.index2) = True
End While
'D. Add this cycle to the list of cycles
Cycles.Add(TempCycle)
End If
Next
'2 Copy alternate cycles to kids
Dim C As Collection
Dim Counter As Integer = 0
For Each C In Cycles
'Alternate with each cycle which kid receives the values
For Each TempPair In C
If Counter Mod 2 = 0 Then
Child1.Alleles(TempPair.index2) = TempPair.value1
Child2.Alleles(TempPair.index2) = TempPair.value2
Else
Child1.Alleles(TempPair.index2) = TempPair.value2
Child2.Alleles(TempPair.index2) = TempPair.value1
End If
Next
Counter += 1
Next
End Sub