はじめに
この記事は自分の備忘録として書いているため、わかりにくい場合はご了承ください。
記事の内容
遺伝的アルゴリズムの交叉の中でも特に循環交叉について取り上げます。
循環交叉の仕組み
循環交叉は順列コーディングに使われる交叉の方式です。
ステップ別に分けて解説していきます。
STEP0
まず、親1と親2の遺伝子の配列を以下のように与えます。
親1 =[ 3 , 7 , 2 , 5 , 6 , 1 , 4 ]
親2 =[ 1 , 7 , 3 , 6 , 2 , 4 , 5 ]
STEP1
ランダムに1組の数字を決めます。今回は、
親1 =[ 3 , 7 , 2 , 5 , 6 , 1 , 4 ]
親2 =[ 1 , 7 , 3 , 6 , 2 , 4 , 5 ]
にしました。
この位置を変えずに子に遺伝子をコピーします。
子1 =[ # , # , 2 , # , # , # , # ]
子2 =[ # , # , 3 , # , # , # , # ]
「#」はまだ数字が埋まっていない場所です。
STEP2
次に先ほどランダムに決めた数字のペアの対になっている数字を子に移します。
子1から見た場合は3で、子2から見た場合は2ですね。
この数字を親と同じ位置にコピーします。
親の数字の位置は以下のようになっています。
親1 =[ 3 , 7 , 2 , 5 , 6 , 1 , 4 ]
親2 =[ 1 , 7 , 3 , 6 , 2 , 4 , 5 ]
この位置を変えずに移すと
子1 =[ 3, # , 2 , # , # , # , # ]
子2 =[ # , # , 3 , # , 2 , # , # ]
のようにコピーされます。
STEP3
最後のステップです。
まず考えやすくするために以下のように子のリストを書き換えます。
子1 =[ 3 , #(7) , 2 , #(5) , #(6) , #(1) , #(4) ]
子2 =[ #(1) , #(7) , 3 , #(6) , 2 , #(4) , #(5) ]
（）内の数字は同じ位置に親が持つ数字です。
そしてこの数字を左から順番に子の間で入れ替えていきます。
まず左端だけ入れ替えると、
子1 =[3,#(1),2,#(5),#(6),#(1),#(4)]
子2 =[#(7),#(7),3,#(6),2,#(4),#(5)]
のようになります。
これを右端まで繰り返して「#」を取ると
子1 =[ 3 , 1 , 2 , 7 , 6 , 4 , 5 ]
子2 =[ 7 , 5 , 3 , 6 , 2 , 1 , 4 ]
のように遺伝子がコピーされました。
入れ替えた数字のペアは「子1の数字⇔子2の数字」として「5⇔7」「6⇔6」「1⇔4」「4⇔5」です。
これで完成です。