This article is written as a memorandum of my own, so please understand if it is difficult to understand.
Among the crossovers of genetic algorithms, we will focus on circular crossovers.
Circular crossover is a method of crossover used for permutation coding. I will explain it step by step. STEP0 First, give the gene sequences of parent 1 and parent 2 as follows.
Parent 1 = [3, 7, 2, 5, 6, 1, 4] Parent 2 = [1, 7, 3, 6, 2, 4, 5] STEP1 Randomly decide a set of numbers. This time,
Parent 1 = [3, 7, ** 2 **, 5, 6, 1, 4] Parent 2 = [1, 7, ** 3 **, 6, 2, 4, 5]
I made it. Copy the gene to the offspring without changing this position.
Child 1 = [#, #, 2, #, #, #, #] Child 2 = [#, #, 3, #, #, #, #]
"#" Is a place where the numbers are not filled yet. STEP2 Next, transfer the paired numbers of the randomly determined number pair to the child. It is 3 when viewed from child 1, and 2 when viewed from child 2. Copy this number to the same location as the parent. The positions of the parent numbers are as follows.
Parent 1 = [** 3 **, 7, 2, 5, 5, 6, 1, 4] Parent 2 = [1, 7, 3, 6, ** 2 **, 4, 5]
If you move it without changing this position
Child 1 = [** 3 **, #, 2, #, #, #, #] Child 2 = [#, #, 3, #, ** 2 **, #, #]
It will be copied like this. STEP3 This is the last step. First, rewrite the list of children as follows to make it easier to think about.
Child 1 = [3, # (7), 2, # (5), # (6), # (1), # (4)] Child 2 = [# (1), # (7), 3, # (6), 2, # (4), # (5)]
The numbers in parentheses are the numbers that the parent has at the same position. Then, this number is exchanged between the children in order from the left. First, if you replace only the left end,
Child 1 = [3, ** # (1) , 2, # (5), # (6), # (1), # (4)] Child 2 = [ # (7) **, # (7), 3, # (6), 2, # (4), # (5)]
It looks like. If you repeat this until the right end and take "#"
Child 1 = [3, 1, 2, 7, 6, 4, 5] Child 2 = [7, 5, 3, 6, 2, 1, 4, 4]
The gene was copied as follows. The exchanged number pairs are "5⇔7", "6⇔6", "1⇔4", and "4⇔5" as "number of child 1⇔number of child 2". That's all there is to it.
Recommended Posts