遺伝オペレータ

遺伝オペレータには, 交配, 突然変異, 自然淘汰の3種類がある.

• 交配
• 突然変異
• 自然淘汰

交配

交配は, 二つの個体を部分的に組合せて新しい個体を生成する操作である. 交配はGAに おいて最も重要な位置を占める遺伝オペレータであり, 適切なコード化と組み合わせる ことでGAの性能を支配すると言われている.

一般的なGAでは, ビットストリングの一部を入れ換える交差法が用いられるが,生成さ れる個体が定義域に入らない不能解や, 極めて評価の悪い解となる確率が高い. このため, 我々が提案する以下の相対ベクトル交差法を使用する.

相対ベクトル交差法 :

個体Aに個体Bを交配させるには, まず個体Aから変数 軸を二つ選び(図では ), 図5.13(a)に示す個体Aと の相対位置関係にある7箇所のいずれかを確率的に選んで個体A'を生成する. これ は個体Aから個体Bへの相対ベクトルの各要素を 倍した差分を個 体Aに加えることに等しい.

A'が定義域の内側に存在するときは, A'がそのまま交配結果となる. A'が 定義域の外側に存在する場合には, 図5.13(b)のように, Aと A'の中点A''を計算する(2). この中点操作を定義域に入るまで繰り返 す(3). 図では二回の中点操作によって, 定義域内部に存在する個体A''' を得ている.

この交配法の特徴として, 生成された個体A'と元の個体Aの距離が, 元の2個体A, Bの距離と等しいため, 多様性が維持されやすいという性質がある. また, 中点操作 により定義域の境界付近に個体が生成されやすいので, 高速にパレート最適個体に到 達できる.

図5.13 交配(相対ベクトル交差法)のメカニズム

突然変異

突然変異は, 単一の個体の一部を変化させ新しい個体を生成する操作である. 初期集団 に十分な多様性があり, 交配がその多様性を失わず探索するならば, 突然変異は必ずし も必要ではない. むしろ, 問題の特性を活かした交配法を中心に探索する方が効率がよ いのが普通である. 突然変異が探索を支配的な役割を果たすならば, それはランダムサー チと変わらないからである. したがって, 突然変異の発生確率は可能であれば, 低く抑 えるべきである.

一般的なGAでは, ランダムに選んだ1ビットを反転する方法が用いられるが, ここでは, 以下に示す微小シフト法を使用する.

微小シフト法 :

交配と同様に個体Aから変数軸を一つ選び(図では ), 乱 数により値を微小に変化させ個体A'を得る(図5.14(1)). もし, 個体A'が定義域の外側に存在する場合は, 個体AとA'の間 で交配と同様の中点操作を定義域に入るまで繰り返す.

図5.14 突然変異(微小シフト法)のメカニズム

自然淘汰

自然淘汰は, 交配や突然変異で生成された個体により増大した個体数をあらかじめ与え られた個体数まで減じる操作である.

多目的最適化GAにおいては目標関数がベクトル値であり単純な値の大小では比較できな い. そのため個体間の優越関係に基づいて定められる半順序(ランク)を利用して比較を 行なう. 個体 X が 個の個体に優越されているとき, X のランク を

のように定める[9]. 図5.15にランキングの例を示す.

図5.15 ランキングの例

ルーレット選択 :

ランクの値に応じた確率で生き残る選択法である. よ りランクの小さい個体はより多く, しかしランクの大きい個体も多少は生き残るよう に選択する. ルーレット選択は最も基本的な自然淘汰法である.

ランクのシェアリング :

ルーレット選択と共に用いて, ランクを個体 の混雑度でバイアスし, 集団の多様性を向上させる操作である.

どのような遺伝オペレータを用いても, 最終的に得られるパレート最適個体集合の分 布に偏りが生じることが多い. この偏りの一因は初期集合の分布の偏りにあるが, 主 たる原因は交 配によって生成される個体の偏りである.

パレート最適個体の多様性を高めるために, 自然選択にランキングのシェアリング を導入する. シェアリング は同じ場所や近い場所に2個体以上が存在する時に, 生き 残り確率を減少させる方法である. 次の niche count (混雑度とも呼ばれる) をランクに乗じて, ランクを調節する.

ここで, d[i,j] は個体 i と個体 j の目的関数域での距離である. Sh(d) はシェアリング 関数であり, d[i,j] の減少関数として与えられる. 次の三角シェ アリング関数がよく用いられる[10] .

はniche半径と呼ばれ, 望ましい個体間の距離であ る. HornHorn94によると, すべてのパレート最適個体について各軸 i の最大 値 と最小値 の差の2乗和の平方根または差の絶対値の総和 が1つのパレート最適解の占める広さ に対応し, 個体数 N と評価関数 の次元 p との間に次の近似関係が成り立つ.

パレート最適個体保存選択 :

一方, もっと単純にその時点でのパレート最 適個体のみ残し, そうでない個体をすべて除去するという方法もあり, この単純な戦 略で十分な性能を実現している例もある[44] [43] .ランク1の個 体のみ残すというランキング選択の特殊な場合と考えることもできる.

パレート最適個体数が集団サイズよりも小さければすべての個体を残し, より多けれ ば(b)のシェアリング選択によって多様性をできるだけ維持するように選択する. な お, 一回の適応度の計算時間が大きい問題では, すべてのパレート最適個体を残し, 集団サイズが徐々に大きくなってゆくような方法も有効である. 我々は, 後者の方法 を採用した.

なお, ランキングおよび シェアリング は集団中のすべての個体に対してその優越関係 または距離を調べる必要あるので, 計算量が多くなるという問題がある. 同時に, 大域 的な演算であることも並列化のネックとなる.