| ■Pre | ■Up | ■Next |
1.NSGA2(Non-dominated S orting Genetic A lgorithms-II ）
SrinivasらのNSGA(Non-dominated Sorting Genetic Algorithm)にエリート主義を導入したアルゴリズムでDebらによって開発されたものである．
また、それ以外にもランキングによるソートの効率化，シェアリングに代わる混雑度の評価指標の導入が行われている．
２.NSGA（高速非優越ソートアプローチ）の複雑性
NSGAの非優越ソートは，個体数Nの個体を非優越のレベルに基づいてソートするためには（ランク1の個体のみを探し出すのに）O(mN^2)が必要となる．次のフロントを探索するために，第一フロントの個体を一時的に無視し，上記の手続きを繰り返す．最悪のケースでは，第二のフロントを見つけるのにもまたO(mN^2)の計算が必要となる．この手続きは，次のフロントを見つけるために続けられる．最も最悪の場合（各フロントに1個体しか存在しないような場合），このアルゴリズムの複雑性は，O(mN^3)になる．
３.NSGA2
・改善点１ ：高速優越ソート
STEP1.
各個体に対して，支配している個体の数と支配されている個体の数を同時に数えていく．（O(mN^2)）
STEP2.
ランク1（支配されている個体：０）の個体のみをフロント１用のリストF_1としてまとめる．
STEP3.
リストF_1に含まれる各個体（i）が支配している個体(j)に対して，支配されている数を1つづ引く
STEP4.
上記同様に，ランク1（最良のフロント）の個体のみをフロント2用のリストF_2としてまとめる．
STEP5.
この操作を全個体がなくなるまで繰り返す．
このような繰り返しの各々がO(N)を必要とする．この処理は，全てのフロントが分別されるまで続けられる．最大でN個のフロントが存在し得るので，最悪の場合におけるこのループの複雑性は，O(N^2)である．このアルゴリズム全体の複雑性は，O(mN^2) + O(N^2) or O(mN^2)である．
改善点２：シェアリングの代用--crowding distance--
NSGAや他の手法において、シェアリングパラメータρ_shareの設計を必要とすることがある．動的なシェアリングパラメーターの変化を行うという研究はあるものの、パラメータのない多様性保持のメカニズムが望ましい．
NSGA2ではシェアリングの代用として，パラメーターレスの多様性確保の手法を考案している．
NSGA2で使われる混雑度の指標は、各個体についてその両隣にいる個体間の距離であり、シェアリング半径のようなシステムパラメータを必要としない．
-混雑度の求め方-
各ランク内の個体集合を目的関数でソートし，隣接する個体を調べる．全個体それぞれの隣接する個体間の距離を求め，個体間の和の数値が低いものほどその個体は混雑していることとする．このパラメータを使用しない混雑度を用いて個体のバラツキを図っている．
改善点３：エリート主義の導入
選択において、次のような手順で行われる．
・選択個体群Nが母集団の数を超えない場合、ランク順に個体を選択していく．
・選択個体群Nが母集団超える場合、 改善点２で求めた混雑度を考慮してN個体選び出す．
