Cycle Crossover Operator Tutorial

Crossover Operators

Mutation Operators

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