3.3 遺伝的アルゴリズムによるパレート 最適解生成法
3.3.4 MOGA
1993年にFonsecaにより提案されたMOGA(Multi-Objective Genetic Algorithm)19）は，
パレ ート的概念を探索に用いたアルゴ リズムである．MOGAでは，個体の評価としてパ レートランキング法を用いた評価方法を行っている．
パレートランキング法では，個体Xiがni個の個体に優越されているとき，Xiのランク r(Xi)を
r(Xi) = 1 +ni (3.7)
のように定めることにしている．この手続きによるランキング例を図 3.6に示す．なお，図 3.6は最小化問題におけるランキングの例である．
このランキング法を用いた選択手法とし ては，ランクの値を適合度に変換し 用いるルー レット選択，各世代で非劣個体(ランク1の個体)のみ残すパレート最適個体保存選択など がある．
また，非劣解集合の多様性保持のための手法とし て，FonsecaとFlemingは各ランク間 においてニッチングを提案している．このニッチングは，3.3.3節において用いたシェアリ ング関数(式3.4)を用いる方法である．このシェアリング関数では，設計変数空間での距 離ではなく，目的関数空間での距離を用いる．あるランクにおける個体iとj間の距離は，
次式により求まる．
f
1(x)
f
2(x)
1
3 3 1
1 1
1 6
図3.6 The concept of Pareto-ranking
dij = M
k=1
fki −fkj fkmax−fkmin
2
(3.8) 式(3.8)のfkmax, fkminは，k番目の目的関数値の最大値と最小値である．式(3.4)を用い てSh(dij)の値を求める．その後，ニッチングカウントを下記の式によって求める．
nci =
j=1
µriSh(di,k) (3.9)
式(3.9)におけるµriは，ランクriにおける個体の数を表している．
適合度割当て
MOGAにおける適合度割当ての流れを以下に示す．
Step 1 各変数の初期化を行う(µ(j) = 0(j = 1, . . . , N) : i= 1)．変数µ(j)はランクjに 属する個体数を保持する変数である．
Step 2 個体iを支配している個体の数niを数え，個体iのランクriをri= 1 +niとし て 計算する．また，ランクriが属するµ(ri)を更新する(µ(ri) =µ(ri) + 1)． Step 3 i < Nならば ，i=i+ 1を行い Step 2へ戻る．そうでなければ Step 4 へ進む．
Step 4 µ(ri)>0を満たすriからランクの最大値を求めr∗とする．ランク値を基準に個体 のソートを行い，全ての個体に対する平均適合度割当てを式(3.10)に従い求める
Fi=N −
ri−1 k=1
µ(k)−0.5(µ(ri)−1) (3.10)
ランクri = 1を持つ個体iに対して，式(3.10)はFi =N−0.5(µ(1)−1)の適合度 を割当てる．このFi値は，µ(1)の平均値であり，NからN−µ(1) + 1までの連続 する整数である．ランクカウンタをrc = 1に定める．
Step 5 ランクrcの各個体iに対して，同じランクを持つ自分以外の個体からニッチカウント
を計算する．この計算は，式(3.9)を用いる．ニッチカウントを用いてFj =Fj/ncj の変換を行う．同じ 平均適合度を維持するため，次式のように割当て適合度をス ケール化する．
Fj → Fjµ(rc) µ(rc)
k=1 Fk
Fj (3.11)
Step 6 もしrc < r∗ならば ，rc =rc+ 1を行いStep 5へ．そうでなければ ，この処理は 終了する．
このように，ランクriの値が1に近い(低い)個体ほど 高い適合度が割当てられ，ランク riの値が大きい(高い)個体ほど 低い適合度が割当てられる．
利点
MOGAは，適合度割当てスキームがシンプルである．ニッチングが目的関数空間で行わ れるため，MOGAでは連続問題だけでなく離散的な組み合わせ問題などに対しても容易に 適用することができる．また，目的関数空間でのニッチングを行うMOGAは，目的関数 空間における非劣解の広がりを求める場合に適した手法であるといえる．
欠点
個体間の支配関係が適合度割当てに用いられているものの，(ランク1の非劣個体を除い て)特定のランクに属する個体全てに同じ適合度を割り振る必要はない．これは，ある探索 領域において幾つかの個体方向へ望まない偏りが生じ る危険性を持っている．特に，この アルゴ リズムではパレート最適フロントの形，探索空間の個体密度に探索が影響されやす い2）．
また，MOGAにおける適合度の割当て計算では，よりランクの悪い解が，よりランクの 良好な解に対して常により悪い適合度を割当てるとは限らない．そのため，より良好なラ
ンクの個体が混み合って存在した場合には，これらの個体に対するニッチカウントが大き くなり，ランクの低い個体の適合度がランクの高い個体の適合度よりも高くなる可能性が ある．もし ，このような逆転現象が生じた場合，より良好なランクを持つ全ての個体に対 して適切な選択圧がかからなくなり，結果とし て収束の遅延，それ以上の探索が不可能と なる．