Rubicite Genetic Algorithm Framework

Rubicite Genetic Algorith Framework Tutorial

General:

Crossovers:

Mutations:

Crossover Technique: Order 1

Order 1 Crossover
Order 1 Crossover is a fairly simple permutation crossover. Basically, a swath of consecutive alleles from parent 1 drops down, and remaining values are placed in the child in the order which they appear in parent 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: 0 4 7 3 6 2 5 1 8 9

Step 1: Select a random swath of consecutive alleles from parent 1. (underlined)

Step 2: Drop the swath down to Child 1 and mark out these alleles in Parent 2.

Order 1 Crossover
Step 3: Starting on the right side of the swath, grab alleles from parent 2 and insert them in Child 1 at the right edge of the swath. Since 8 is in that position in Parent 2, it is inserted into Child 1 first at the right edge of the swath. Notice that alleles 1, 2 and 3 are skipped because they are marked out and 4 is inserted into the 2nd spot in Child 1.

Step 4: If you desire a second child from the two parents, flip Parent 1 and Parent 2 and go back to Step 1.

Order 1 Performance
Order 1 crossover is perhaps the fastest of all crossover operators because it requires virtually no overhead operations. On a generation by generation basis, edge recombination typically outperforms Order 1, but the fact that Order 1 runs between 100 and 1000 times faster usually allows the processing of more generations in a given time period.

VB.NET 2008 Source Code

Public Sub Permutation_Order_1(ByRef Child1 As PChromo, ByRef Child2 As PChromo, ByRef Parent1 As PChromo, ByRef Parent2 As PChromo) 'Crossover parents i and i + 1 Dim HS1 As New Hashtable Dim Hs2 As New Hashtable Dim iTemp As Integer '*** Debug 'Dim DString As String 'For k As Integer = 0 To AlleleCount - 1 ' DString &= vbTab & parent1.Alleles(k) 'Next 'DString &= vbCrLf 'For k As Integer = 0 To AlleleCount - 1 ' DString &= vbTab & parent2.Alleles(k) 'Next 'The first step is to pick out a set of consecutive indices for each parent 'X is the left-most index of the set 'Y is the right-most index of the set Dim X As Integer = RAND.Next(0, AlleleCount) Dim Y As Integer Do Y = RAND.Next(0, AlleleCount) Loop Until Y <> X If X > Y Then : iTemp = X : X = Y : Y = iTemp : End If 'Fill Childrenz from index X to index Y of parents For j As Integer = X To Y Child1.Alleles(j) = Parent1.Alleles(j) HS1.Add(Parent1.Alleles(j), Nothing) Child2.Alleles(j) = Parent2.Alleles(j) Hs2.Add(Parent2.Alleles(j), Nothing) Next 'Fill in the rest of Child 1 ' - The term 'order' comes into play here ' We order the remaining values based upon their position in the opposite parent ' So, we'll order the remaining values for child 1 based upon their relative order in parent 2 ' Also, the ordering starts after the set of consecutive indexes, otherwise the order starts at Y + 1 ' Going to use 2 loops to do it ' marker marks the position in the child to insert the next value from the parent 'From Y+1 to the end of Parent2 Dim marker As Integer = Y + 1 : If marker = AlleleCount Then marker = 0 'if marker is too high, wrap it around For j As Integer = Y + 1 To AlleleCount - 1 If Not HS1.Contains(Parent2.Alleles(j)) Then Child1.Alleles(marker) = Parent2.Alleles(j) HS1.Add(Parent2.Alleles(j), Nothing) marker += 1 If marker = AlleleCount Then marker = 0 'if marker is too high, wrap it around End If Next 'From 0 to Y for Child 1 - Values coming from Parent2 For j As Integer = 0 To Y If Not HS1.Contains(Parent2.Alleles(j)) Then Child1.Alleles(marker) = Parent2.Alleles(j) HS1.Add(Parent2.Alleles(j), Nothing) marker += 1 If marker = AlleleCount Then marker = 0 'if marker is too high, wrap it around End If Next 'Fill in the rest of Child 2 - Values coming from Parent1 'From Y + 1 to the end of Parent1 marker = Y + 1 : If marker = AlleleCount Then marker = 0 ' if marker is too high, wrap it around For j As Integer = Y + 1 To AlleleCount - 1 If Not Hs2.Contains(Parent1.Alleles(j)) Then Child2.Alleles(marker) = Parent1.Alleles(j) Hs2.Add(Parent1.Alleles(j), Nothing) marker += 1 If marker = AlleleCount Then marker = 0 'if marker is too high, wrap it around End If Next 'from 0 to Y for child 2 - values coming from parent 1 For j As Integer = 0 To Y If Not Hs2.Contains(Parent1.Alleles(j)) Then Child2.Alleles(marker) = Parent1.Alleles(j) Hs2.Add(Parent1.Alleles(j), Nothing) marker += 1 If marker = AlleleCount Then marker = 0 'if marker is too high, wrap it around End If Next 'DString &= vbCrLf 'For k As Integer = 0 To AlleleCount - 1 ' DString &= vbTab & Child1.Alleles(k) 'Next 'DString &= vbCrLf 'For k As Integer = 0 To AlleleCount - 1 ' DString &= vbTab & Child2.Alleles(k) 'Next 'DString &= vbCrLf & "X: " & X & " Y: " & Y & vbCrLf ' MsgBox(DString) End Sub