交叉

選択された個体間での染色体の組み替えにより新しい個体を生成するという交叉(crossover)は、 GAでは最も重要な役割を果たす遺伝的オペレータであるといえる。このような交叉は、 個体群の中から任意の２つの個体(親)をランダムに選び、さらに、ランダムに選ばれた１点あるいは 多点の交差点(crossover point)で遺伝子を組み替えることにより、新たな２つの個体(子)を 生成する操作である。

本研究では、１点交叉・２点交叉・一様交叉を用いた。

(1)１点交叉

１点交叉では、親１、親２の文字列上で交差点をランダムに１カ所選び、交差点$''\vert''$の右側の２つの親の 部分文字列をそのまま変換して、子１、子２を生成する。このような１点交叉の例は次の様になる。

親１： 11000$\vert$0001		子１： 110000100
親２： 10111$\vert$0100

(2)２点交叉

１点交叉では、交差点を１ヶ所選択したが、これを２カ所にしたものが２点交叉である。

具体的には、交差点の間で交互に２つの親の部分文字列をそっくりそのまま変換して、子１、子２を生成する。 このような２点交叉の例は次の様になる。

親１： 11$\vert$000$\vert$0001		子１： 111110001
親２： 10$\vert$111$\vert$0100

(3)一様交叉

一様交叉は、任意個の交差点を取ることのできる交叉法と見なされ、 1989年にG.Syswerdaによって提案された。 一様交叉では、まず${0,1}$をランダムに発生させて$n$ビットのマスクパターンを作る。 このマスクパターン上の１の遺伝子座には親１の遺伝子を、０の遺伝子座には親２の 遺伝子を受け継ぐ子１と、その逆の受け継ぎ方をする子２を生成させる。

このような一様交叉の例は次の様になる。

親１： 110000001

親２： 101110100

マスク： 101101101

子１： 100010001

子２： 111100100