About circular crossover of genetic algorithms

Introduction

This article is written as a memorandum of my own, so please understand if it is difficult to understand.

Article content

Among the crossovers of genetic algorithms, we will focus on circular crossovers.

Mechanism of circulation crossing

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

About circular crossover of genetic algorithms
About all of numpy
About assignment of numpy.ndarray
About MultiIndex of pandas
About variable of chainer
Search for stable structures of metal nanoclusters using genetic algorithms
About max_iter of LogisticRegression () of scikit-learn
About the ease of Python
About Japanese support of cometchat
About various encodings of Python 3
About all of numpy (2nd)
About cost calculation of MeCab
About the components of Luigi
About HOG output of Scikit-Image
About the features of Python
About data management of anvil-app-server