- 製造業出身のデータサイエンティストがお送りする記事
- 今回は多目的最適化手法の中で、NSGA-Ⅱを勉強しましたので、整理しました。
多目的最適化とは
目的関数が複数存在する最適化問題を多目的最適化問題と呼びます。多目的最適化における最適性とは、優越されていないパレート最適解を見つけることを指します。
NSGA-Ⅱとは
NSGA-Ⅱ(Elitist Non-dominated Sorting Genetic Algorithm)は、Debらによって2002年に提案された多目的遺伝的アルゴリズムです。これは遺伝的アルゴリズム(Genetic Algorithm)を多目的最適化問題に拡張したものです。
NSGA-Ⅱの特徴は下記3点があります。
- 高速非優劣ソートによるランキング法
- 混雑度ソートによる個体選択
- 混雑度トーナメント選択による遺伝子操作
NSGA-Ⅱのアルゴリズム概要
NSGA-Ⅱでは、親母集団$P_t$と遺伝子操作（交叉・突然変異）を行って探索を行うための子母集団$Q_t$の2つの独立した集団を用いて解探索を行う手法です。具体的なアルゴリズムの流れは下記の通りです。
① サイズNの親母集団$P_t$をランダムに生成し、サイズNの子母集団$Q_t$を生成し、$P_t$と$Q_t$を組合せて集団$R_t$を生成する。
② 集団$R_t$に対して非優劣ソートを実施し、全個体をランク毎（$F_1$, $F_2$, ・・・）と分類する。
③ 新たな空の親母集団$P_{t+1}$を生成し、②の非優劣ソートでランクが上位の個体で親母集団$P_{t+1}$を構成していく。
④ ③で親母集団$P_{t+1}$を構成していく途中で、個体サイズがNを越える時、サイズNを越えるランクの個体に対して、混雑度ソートを実行し、混雑度の高い個体を個体サイズがNになるまで取り除く。
⑤ 親母集団$P_{t+1}$に対して混雑度トーナメント選択により、交叉・突然変異すべき個体を選択し、遺伝子操作を行い新たな子集団$Q_{t+1}$を生成する。
⑥ 親母集団$P_{t+1}$と子集団$Q_{t+1}$を組み合わせて新たな集団$R_{t+1}$を生成する。
⑦ ②へ戻り、これまでの操作を終了条件が満たすまで繰り返し実施します。
高速非優劣ソートとは
高速非優劣ソートのアルゴリズムは下記の通りです。
① 各個体に対して、支配している個体の数と支配されている個体の数を同時に数えます。
② ランク1（支配されている個体：0）の個体のみをフロント1用のリストF_1として纏めます。
③ リストF_1に含まれる各個体（i）が支配している個体（j）に対して、支配されている数を1ずつ引きます。
④ ランク1（最良のフロント）の個体のみをフロント2用のリストF_2として纏めます。
⑤ ③〜④を繰り返し、全ての個体が無くなるまで実施します。
混雑度とは
各ランク内の個体集合を目的関数でソートし、隣接する個体を調べます。全個体それぞれの隣接する個体間の距離を求め、個体間の和の数値が低いものほど、その個体は混雑している事とし、それを混雑度と呼びます。
混雑度ソートとは
選択個体群$M$が母集団の数$N$を超えない場合は、ランク順に個体を選択します。選択個体群$M$が母集団の数
$N$を超える場合は、混雑度を考慮して個体を選択します。
さいごに
最後まで読んで頂き、ありがとうございました。
今回は多目的最適化問題のNSGA-Ⅱを整理しました。
次は実装したものを纏めたいと思います。
訂正要望がありましたら、ご連絡頂けますと幸いです。