NSGA-II
Non-dominated Sorting Genetic Algorithm II
本セクションでは、多目的最適化の代表的な手法である NSGA-II を紹介します。
NSGA-II は、遺伝的アルゴリズムに基づく多目的最適化アルゴリズムです。 複数の目的が競合する問題に適しており、他の目的を悪化させることなくどの目的も改善できない解の集合であるパレートフロントを見つけることを目標とします。 Grasshopper では Wallacei でも使用されており、多目的最適化では広く使われている手法です。
多目的最適化とは
単目的最適化には唯一の最良解が存在します。
一方、多目的最適化には通常、単一の「最良」解は存在せず、代わりにトレードオフ解の集合が存在します。 たとえば構造物の重量と変形量をどちらも小さくしたい場合、重量を下げれば部材は細くなり変形は大きくなりやすいため、両方を同時に最小にする解は得られないことがほとんどです。 そのため多目的最適化では、一つの答えを出すのではなく、どこまで一方を犠牲にできるかという選択肢の集合を得ることを目指します。
解 A が解 B を支配するとは、以下を満たす場合です。
Aがすべての目的においてBと少なくとも同等以上であり、かつAが少なくとも 1 つの目的においてBよりも厳密に優れている
他のどの解にも支配されない解の集合がパレートフロントを形成します。 NSGA-II の各ステップは、この支配関係を手がかりに集団を並べ替えることで、パレートフロントに近い個体を世代ごとに残していくように組み立てられています。
NSGA-II の仕組み
STEP1: 初期集団
個体（変数値の集合）の集団がランダムに生成され、評価されます。 最初の段階では目的関数の形状について何もわかっていないので、まずは偏りなく集団を散らすことから始めます。
STEP2: 非優越ソート
集団は支配関係に基づいてフロントに分類されます。
- フロント 1: 他のどの解にも支配されない解（現在のパレートフロント）
- フロント 2: フロント 1 の解にのみ支配される解
- 以降同様に続く…
このランク付けは非優越ランクと呼ばれます。 ランクが小さい個体ほどパレートフロントに近いため、次の世代に残す個体を選ぶ際の第一の基準になります。
STEP3: 混雑距離
各フロント内で、各個体について混雑距離（crowding distance）が計算されます。
これは、目的空間内である個体が、近傍からどれだけ孤立しているかを測る指標です。
同じフロントに属する個体は非優越ランクだけでは優劣がつかないため、この混雑距離が 2 つ目の基準になります。 混雑距離が大きい個体が優先されることで、パレートフロントに沿った多様性が促進されます。 逆に密集した個体ばかりを残すと、得られる解がフロントの一部に固まってしまい、トレードオフを比べるという多目的最適化の目的から外れてしまいます。
STEP4: 選択、交叉、突然変異
以下の手順により新しい世代が生成されます。
- 選択: より良い非優越ランクを持つ個体を優先し、ランクが同じ場合は混雑距離が大きい個体を優先する
- 交叉: 2 つの親解を組み合わせて子解を生成する
- 突然変異: 多様性を維持するために子解をランダムに摂動させる
選択でこの 2 つの基準を順に見ているのは、STEP2 で求めたパレートフロントへの近さと、STEP3 で求めた多様性を、どちらも次の世代に引き継ぐためです。
Tunny は uniform（デフォルト）、blxalpha、sbx、vsbx、undx、spx
のいくつかの交叉方法をサポートしています。 交叉は 2
つの親から子を作る操作であり、どの方法を選ぶかによって、生成される子解の散らばり方が変わります。
STEP5: エリート主義
現在の集団と子集団の中から最良の個体が組み合わされ、集団サイズを維持するように選別されます。
このエリート主義戦略により、過去の世代で見つかった良い解が失われることはなく、世代を重ねてもパレートフロントが後退することはありません。
STEP2 から STEP5 は、試行回数に達するまで繰り返されます。
NSGA-II を使うべき場面
- 2 つ以上の目的関数がある場合
- 多様なトレードオフ解の集合（パレートフロント全体）が欲しい場合
- 目的関数の形状について強い事前知識がない場合
- 十分な評価予算がある場合（遺伝的アルゴリズムは一般に、収束にベイズ的手法よりも多くの試行回数を必要とします）
NSGA-II は集団を世代交代させながら少しずつ解を改善していく手法であり、1 試行ごとに確率モデルを作り直すベイズ最適化とは進み方が異なります。 そのため、1 試行にかかる時間が短く、試行回数を多く確保できる問題に向いています。 サンプラーの選び方のページで NSGA-II が試行回数の多い側の候補になっているのは、このためです。