Genetic Algorithm Info

Crossover Operators

Mutation Operators

Crossover Technique: PMX

PMX Crossover
PMX Crossover is a genetic algorithm operator. For some problems it offers better performance than most other crossover techniques. Basically, parent 1 donates a swath of genetic material and the corresponding swath from the other parent is sprinkled about in the child. Once that is done, the remaining alleles are copied direct from parent 2.

  1. Randomly select a swath of alleles from parent 1 and copy them directly to the child. Note the indexes of the segment.

  2. Looking in the same segment positions in parent 2, select each value that hasn't already been copied to the child.

      • For each of these values:

        1. Note the index of this value in Parent 2. Locate the value, V, from parent 1 in this same position.

        2. Locate this same value in parent 2.

        3. If the index of this value in Parent 2 is part of the original swath, go to step i. using this value.

        4. If the position isn't part of the original swath, insert Step A's value into the child in this position.

  3. Copy any remaining positions from parent 2 to the child.
PMX 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

Child 1:  _ _ _ 3 6 2 5 1 _ _

1. We copy a random swath of consecutive alleles from Parent 1 to the Child.

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:  _ _ _ 3 6 2 5 1 _ _


2. '4' is the first value in the swath of Parent 2 that isn't in the child. We identify 6 as the value in the same position in Parent 1. We locate the value 6 in Parent 2 and notice that it is still in the swath. So, we go back to step 'i' using 6 as the value.

PMX 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

Child 1:  _ _ _ 3 6 2 5 1 _ _

3. Repeating Step i: Once again, we see that 5 is in the same position in Parent 1, and we locate 5 in Parent 2. It also is in the swath, so we repeat step 'i' once more with '5' as our value.

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:  _ _ 4 3 6 2 5 1 _ _

4. Repeating Step i: We see that 2 is in the same position in Parent 1, and we locate 2 in Parent 2 in the 3rd position. Finally, we have obtained a position in the Child for the value 4 from Step 2.

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:  _ 7 4 3 6 2 5 1 _ _

5. '7' is the next value in the swath in Parent 2 that isn't already included in the Child. So, we check the same index in Parent 1 and see a '1' in that position. Next, we check for '1' in Parent 2 and find it in the 2nd position. Since the 2nd position is not part of the swath, we've found a home for the value '7'.

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:  0 7 4 3 6 2 5 1 8 9

6. Now the easy part, we've taken care of all swath values, so everything else from Parent 2 drops down to the child.

If we wish to create a 2nd child with the same set of parents, simply swap the parents and start over.
VB.NET 2008 Source Code 
'PMX Crossover is very complicated, check out the oxypedia entry for details
            Public Sub Permutation_PMX(ByRef Child1 As PChromo, ByRef parent1 As PChromo, ByRef parent2 As PChromo)
                Static Dim iTemp As Integer
                Static Dim C As Collection
                Static Dim HS1, ValuesLeft As Hashtable
                Static Dim Pair As New Index_Value_Pair
                Static Dim Position As Integer
                HS1 = New Hashtable
                ValuesLeft = New Hashtable
                C = New Collection


                '1 Setup the Swath
                Dim randswathsize As Integer = RAND.Next(PMX_Master.Doubles(0) * AlleleCount, PMX_Master.Doubles(1) * AlleleCount) 
                'Doubles(0) = Min Swath Size || Doubles(1) = Max Swath Size

                If randswathsize < 2 Then randswathsize = 2

                'X refers to left index of Swath || Y refers to right index of swath
                Dim X As Integer = RAND.Next(0, AlleleCount - randswathsize)
                Dim Y As Integer = X + randswathsize - 1

                If Y - X = AlleleCount - 1 Then Y -= 2 'make sure the swath isn't the whole chromo

                '2. Fill up ValuesLeft - keeps track of which values can be given to child
                '  - Also initialize child values to sentinel value of -99999
                For j As Integer = 0 To AlleleCount - 1
                    ValuesLeft.Add(parent1.Alleles(j), Nothing)
                    Child1.Alleles(j) = -99999
                Next

                '3.Fill Child from index X to index Y of parent
                For j As Integer = X To Y
                    If Child1.Alleles(j) <> -99999 Then MsgBox("Help Me2")
                    If HS1.Contains(parent1.Alleles(j)) Then MsgBox("help me 8")
                    Child1.Alleles(j) = parent1.Alleles(j)
                    HS1.Add(parent1.Alleles(j), Nothing)
                    ValuesLeft.Remove(parent1.Alleles(j))
                Next

                '3. Figure out which values from Parent2's swath were not put in the child from Parent1
                For j As Integer = X To Y
                    If Not HS1.Contains(parent2.Alleles(j)) Then
                        Pair = New Index_Value_Pair
                        Pair.index = j
                        Pair.value = parent2.Alleles(j)
                        C.Add(Pair)
                    End If
                Next

                '4. 
                For Each Pair In C
                    '1. find position (in parent2) of value in Pair's position in child 
                    For j As Integer = 0 To AlleleCount - 1
                        If parent2.Alleles(j) = Child1.Alleles(Pair.index) Then
                            Position = j
                            Exit For
                        End If
                    Next

                    '2. If position is taken in child already, find position of item that is in its spot in parent 2
                    '     Otherwise, put it there
                    While Child1.Alleles(Position) <> -99999
                        'A. Find position of value in this spot in the child in parent 2
                        For j As Integer = 0 To AlleleCount - 1
                            If parent2.Alleles(j) = Child1.Alleles(Position) Then
                                Position = j
                                Exit For
                            End If
                        Next
                    End While

                    'If this is reached, we drop the Pair.value in Position
                    If Child1.Alleles(Position) <> -99999 Then MsgBox("Help Me4")
                    If HS1.Contains(Pair.value) Then MsgBox("help me 6")
                    Child1.Alleles(Position) = Pair.value
                    HS1.Add(Pair.value, Nothing)

                Next

                '5 Drop the remaining values in
                For j As Integer = 0 To AlleleCount - 1
                    If Not HS1.Contains(parent2.Alleles(j)) Then
                        If Child1.Alleles(j) <> -99999 Then MsgBox("Help Me5")
                        Child1.Alleles(j) = parent2.Alleles(j)
                        HS1.Add(parent2.Alleles(j), Nothing)
                    End If
                Next

            End Sub