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