Non-dominated Sorting Genetic Algorithm II

NSGA-II は、遺伝的アルゴリズムに基づく多目的最適化アルゴリズムです。複数の目的が競合する問題に適しており、他の目的を悪化させることなくどの目的も改善できない解の集合であるパレートフロントを見つけることを目標とします。

多目的最適化とは

単目的最適化には唯一の最良解が存在します。一方、多目的最適化には通常、単一の「最良」解は存在しません。代わりに、トレードオフ解の集合が存在します。

解 A が解 B を支配するとは、以下を満たす場合です。

他のどの解にも支配されない解の集合がパレートフロントを形成します。

個体（変数値の集合）の集団がランダムに生成され、評価されます。

集団は支配関係に基づいてフロントに分類されます。

このランク付けは非優越ランクと呼ばれます。

各フロント内で、各個体について混雑度距離（crowding distance）が計算されます。これは、目的空間内である個体が近傍からどれだけ孤立しているかを測る指標です。混雑度距離が大きい個体が優先されることで、パレートフロントに沿った多様性が促進されます。

以下の手順により新しい世代が生成されます。

Tunny は uniform（デフォルト）、blxalpha、sbx、vsbx、undx、spx のいくつかの交叉方法をサポートしています。

現在の集団と子集団の中から最良の個体が組み合わされ、集団サイズを維持するように選別されます。このエリート主義戦略により、過去の世代で見つかった良い解が失われることはありません。

STEP2 から STEP5 は、試行回数に達するまで繰り返されます。