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.
|