実数型GAに於ける交叉法の改良

トップページ研究分野と周辺進化型計算遺伝的アルゴリズム

実数型GAは、遺伝子を構成する数字が0、1のバイナリではなく、何らかの実数を取る。其れはTSPであれば訪問する都市の番号である等、解に直接関係の在る数字である。
遺伝子を構成する数字は、遺伝子の長さがnであれば、n次元のベクトルとなる。
図は遺伝子長が2の例で、通常のGAでは考えられない短さだが、原理を簡単に示すために二次元とした。
通常の交叉では、図のように、n+1世代の個体は、それを作るn世代の個体間を結ぶ線(ここでは斜めの線)からは必ずはずれる所に出来る。
しかし或る程度、進化が進んで、各個体が優秀になって来た場合、任意の二個体の「間」に相当する場所に、さらに優れた個体が存在する場合が多い。
交叉法の改良は、このあたりを考慮して作られている方法が多い。これらは単純な数値の入れ替えではなく、親個体の数値を合成して別の数値を作る場合が多い。

BLX-α交叉

2つの親個体から、以下の方法により次世代を生成する(遺伝子長=2の簡単な例で示す)。
親個体のベクトル(2次元)を其々x座標、y座標で示し、(x1,y1)、(x2,y2)とすると、子供のx座標とy座標の発生範囲を以下のように決める。
dx=|x1-x2|、dy=|y1-y2|とおく。min_x=min(x1,x2)、min_y=min(y1,y2)、max_x=max(x1,x2)、max_y=max(y1,y2)とおく。
ここで、min(a,b)はa,bのうち小さな方の値、max(a,b)はa,bのうち大きな方の値を取るとする。
次世代のx座標の最小値をmin_cxとし、min_cx=min_x-αdxとする。
次世代のx座標の最大値をmax_cxとし、max_cx=max_x+αdxとする。
次世代のy座標の範囲も同様に、min_cy=min_y-αdy、max_cy=max_y+αdyとする。
ここでαは任意に設定出来るパラメータで、0.5以下の数値が用いられる場合が多い。0.3前後が良いかもしれない。

結局、次世代の存在範囲は、図の赤線の中になる。親個体によって出来る長方形を、x軸y軸の其々α倍伸ばした長方形で囲まれた範囲となる。
より良い個体は、親個体の「間」に在る確率は高いが、敢えてはずれた範囲も入れるのは、解の多様性を保つためと考えられる。
次世代の具体的な座標は、この範囲の中から乱数によりランダムに設定する(黄色の丸の部分)。次元数が増えても、計算の拡張は容易である事が分かるだろう。

SPX(シンプレックス交叉)

シンプレックスとはn次元空間に於いて、n+1個の点から成る図形の事で、例えば2次元平面の場合は、三角形がシンプレックスである。
この方法は、変数の数(遺伝子長)がnであれば、n+1の親世代により次世代の生成を行なう(例えば3個体で1個体を生成する方法は、自然界には存在しない)。
2変数の場合、3個体を用いる。図のような配置であったとすると、まずそれらの重心g(ベクトルの平均)を求める。
gx=(x1+x2+x3)/3、gy=(y1+y2+y3)/3となる。図の上では、ちょうど中心あたりに位置する事になる。
次に、親個体の数だけ、以下のベクトルを求める。
s1x=gx+ε(x1-gx)、s1y=gy+ε(y1-gy)
s2x=gx+ε(x2-gx)、s2y=gy+ε(y2-gy)
s3x=gx+ε(x3-gx)、s3y=gy+ε(y3-gy)
ここでεは拡張率と呼ばれる1より大きい定数で、n+2の平方根等が用いられている。
図のように、例えばy1の方がgyより大きければ、ε(y1-gy)は正となり、s1yはgyより大きくなる。
逆に、x1の方がgxより小さければ、ε(x1-gx)は負となり、s1xはx1より小さくなる。
つまり、親個体で作る三角形より外側に、このベクトルは作られる。重心から或る親個体に引いた矢印のε倍のところにベクトルが作られる。
後の二つもε倍の位置に置かれ、三つの外側のベクトル(s1,s2,s3)が右図のように作られる。

次に以下の式によって、子個体(c1,c2,c3)の位置を決める。
c1x=s1x、c1y=s1y
c2x=r1(s1x-s2x)+s2x、c2y=r1(s1y-s2y)+s2y
c3x=r2(s2x-s3x+r1(s1x-s2x))+s3x、c3y=r2(s2y-s3y+r1(s1y-s2y))+s3y
ここで、r1=u[0,1]、r2=(u[0,1]の1/2乗)となる。u[0,1]は区間0~1.0間の乱数を表している。
c1は、s1と一致している。c2は、s2からs1に至るベクトルのr1倍の位置にある。
c3は、s3からs2に至るベクトル(青矢印)と、s2からs1に至るベクトルのr1倍のベクトル(短い方の紫矢印)の和(緑矢印)となるベクトルのr2倍の位置にある。

r1、r2は乱数だが、1未満であるため、1/2乗した方が大きくなる(1/3乗でさらに大きくなる)ので、r2の方がr1より大きくなる傾向にある。
つまり、c1、c2は拡張率によって、親個体で作る三角形より外側に置かれるのだが、c3はr2が大きくなって来る事で、親個体の三角形の内側に入って来るようになる。
LBX-α交叉がランダムに親個体間の周辺に子個体を生成するのに対し、SPXは親個体同士を結ぶ線分を重視して子個体の位置を決めている。
これは、y=f(x)のように、遺伝子を構成する変数(ここではxとyの二つ)間に依存関係が在る場合は有効な手法と言える。親個体同士を結ぶ線分がy=f(x)の線に乗っているとすると、子個体もその線上付近に現れる可能性が高いからだ。
変数(遺伝子長)をn個(n次元)に拡張した場合の式を、ベクトル表記で示す(ベクトル表記と加減算については、「ベクトル」のページを参照)。
ここで、親ベクトルをP1,P2...,P(n+1)、子ベクトルをC1,C2...,C(n+1)、親ベクトルの重心(ベクトル)をg、外側のベクトルをS1,S2...,S(n+1)と表記している。