NSGA-II — 非支配ソート遺伝的アルゴリズムII
- 年
- 2002
- 種類
- Evolutionary multi-objective optimisation algorithm
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
NSGA-II(非支配ソート遺伝的アルゴリズムII)は、多目的進化最適化における標準的な参照アルゴリズムであり、2002年にDeb、Pratap、Agarwal、Meyarivanによって導入されました。複数の相反する目的を単一のスコアに集約するのではなく、世代を超えて候補解の集団を進化させ、高速非支配ソートとクラウディング距離指標を使用して多様性を維持することにより、パレート最適トレードオフ解のセット(パレートフロント)を返します。
手法の背後にある直感
製品を同時に可能な限り安価で耐久性のあるものにしたいと想像してみてください。安価であることは通常、耐久性が低いことを意味するため、単一の完璧な答えはありません。 sensible compromises の家族が存在します。NSGA-IIは、競合する設計の集団のように機能します。各世代で、すべての目的において他の設計に支配されている弱い設計は排除され、生存者は、単一のコーナーに集中するのではなく、トレードオフの全範囲をカバーするように広げられます。十分な世代の後、優先順位に合ったバランスを選択できる、豊富なオプションのメニュー(パレートフロント)が残ります。
歴史学
NSGA-IIは、2002年にインド工科大学カーンプルのKalyanmoy Debと同僚によって、元のNSGA(Srinivas & Deb、1994)の修正され大幅に改善された後継者として発表されました。主な革新は、O(MN²)の複雑さを持つ高速非支配ソート手順、共有パラメータなしで解の多様性を維持するための明示的なクラウディング距離演算子、およびエリート選択メカニズムでした。2002年のIEEE Transactions on Evolutionary Computation論文は、進化計算で最も引用された作品の1つとなり、NSGA-IIを進化的多目的アルゴリズムの事実上のベンチマークとして確立しました。後のバリアント(NSGA-III(2014)など)は、フレームワークを多目的問題に拡張します。
使うべき場面
NSGA-IIは、情報損失なしに単一の基準にマージできない、2つ以上の相反する目的関数を持つ問題に適用されます。決定変数は連続、バイナリ、またはカテゴリカルであり、目的ランドスケープに対する分布仮定は必要ありません。このアルゴリズムは、単一の最適解よりもトレードオフ解のスペクトルがより有用な工学設計、リソース割り当て、スケジューリング、およびポートフォリオ問題に適しています。良好なフロントカバレッジを達成するには、十分な世代数(通常は数百世代以上)が必要です。世代数が少なすぎることが主な失敗モードです。
限界と注意点
- 目的の数が3つまたは4つを超えるとパフォーマンスが低下します。クラウディング距離は、高次元では不十分な多様性尺度になります。
- 集団サイズと世代数の慎重な調整が必要です。世代数が少なすぎると、適切なフロントカバレッジが得られません。
- 高価なシミュレーションを伴う目的関数の評価は、アルゴリズムの計算コストを高くします。
- 結果は確率的です。異なるランダムシードは異なるパレートフロントをもたらす可能性があるため、複数の実行と統計的比較(例:ハイパーボリューム)が推奨されます。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 単一の実行で、パレート最適トレードオフ解の多様なセットを生成し、異なる重みで最適化を繰り返す必要がなくなります。
- 高速非支配ソートはO(MN²)時間(M目的、N集団サイズ)で実行されるため、中程度の問題サイズで実行可能です。
- エリート選択により、早期に見つかった良い解が決して破棄されないことが保証されます。
- 分布仮定なしで、連続、バイナリ、およびカテゴリカルな決定変数に適用可能です。
- 工学、オペレーションズリサーチ、および計算科学のドメイン全体で広く検証されています。
応用
- 工学設計:機械部品の重量を同時に最小化し、構造強度を最大化する。
- 環境およびエネルギーシステム:電力網または再生可能エネルギー計画におけるコスト、排出量、および信頼性のバランスをとる。
- ヘルスケアおよびオペレーションズリサーチ:患者の待ち時間、リソース利用率、およびコストを同時に最適化するスケジューリング。
- 金融におけるポートフォリオ最適化およびビジネスにおけるプロジェクト選択:リターン、リスク、および流動性のトレードオフ。
- 機械学習におけるハイパーパラメータチューニング:精度とモデルの複雑さまたは推論時間のトレードオフを最適化する。
使い方
使い方
候補解の集団は、決定変数をその境界内でランダムに(または設計によって)サンプリングすることによって作成されます。集団サイズは、最初から目的空間全体にわたる多様性を確保するのに十分な大きさに設定されます。
各候補解は決定変数の値にデコードされ、すべての目的関数が評価されます。結果は、個体ごとの目的スコアのベクトルになります。このステップは、目的がシミュレーションまたは高価なモデルを含む場合、計算上のボトルネックとなることがよくあります。
解は非支配ソートによってランク付けされます。最初のフロントには、他のどの解にもすべての目的において支配されていないすべての解が含まれます。2番目のフロントには、最初のフロントの解にのみ支配されている解が含まれます。そしてその逆も同様です。各フロント内で、クラウディング距離スコアが計算され、解が近傍からどれだけ孤立しているかを測定します。クラウディング距離が高いほど、解はそのフロントの混雑していない領域を占めていることを意味します。
エリート選択戦略は、現在の集団と子孫をマージし、最高のN個の個体を保持します。フロントを順番に埋め、最後の許容可能なフロント内のタイを破るためにクラウディング距離を使用します。これにより、前の世代で見つかった良い解が決して失われないことが保証されます。
選択された個体は、遺伝子演算子(バイナリトーナメント選択、シミュレーテッドバイナリクロスオーバー(SBX)、および多項式突然変異)を介して繁殖し、新しい子孫集団を生成します。これらの演算子は、有望な解の近傍を探索しながら、意味のあるバリエーションを維持します。
ステップは、指定された世代数だけ進化を繰り返して評価されます。収束は、パレートフロントの視覚的検査またはハイパーボリューム指標の追跡によって判断されます。最終的な出力は、真のパレートフロントを近似する非支配解セットです。
よくある落とし穴
- 通常、数百世代未満の実行では不完全なパレートフロントが得られます。計算予算がタイトな場合は、代わりに重み付き単一目的最適化を検討してください。
- 単一目的の問題を多目的として扱うことは不要です。単一目的オプティマイザーを使用してください。
- 適切な変数境界を設定しないと、探索空間の実行可能または意味のある領域に到達しない集団につながります。
- パレートフロントの解を1つだけ報告し、完全なフロントを開示しないと、NSGA-IIが明らかにしようとしているトレードオフ構造が隠されてしまいます。
よくある質問
NSGA-IIにはいくつの世代が必要ですか?
普遍的なルールはありませんが、通常、数百世代未満の実行では不完全なパレートフロントが得られます。実用的なアプローチは、世代にわたるハイパーボリューム指標をプロットし、それが安定したら停止することです。計算予算でこれができない場合は、重み付き単一目的オプティマイザーがより安全な代替手段です。
パレートフロントとは何ですか?
パレートフロントとは、他の少なくとも1つの目的を悪化させることなく、1つの目的の改善が不可能な解のセットです。NSGA-IIはこのフロントを近似し、単一の答えではなく、バランスの取れた妥協の完全なメニューを提供します。
NSGA-IIは2つ以上の目的を扱えますか?
はい、しかしクラウディング距離(多様性メカニズム)は、目的の数が3つまたは4つ(「多目的」レジーム)を超えると効果が低下します。5つ以上の目的を持つ問題では、通常、NSGA-IIIまたはMOEA/Dのような分解ベースのアルゴリズムが推奨されます。
NSGA-IIは決定論的ですか?
いいえ。遺伝子演算子と初期集団にはランダム性が含まれるため、異なるランダムシードでの異なる実行は、異なるパレートフロント近似をもたらす可能性があります。ベストプラクティスは、アルゴリズムを複数回実行し、ハイパーボリューム指標を使用してフロントの品質を比較することです。
関連する手法
参考文献
Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
DOI 文献を開くコピーしました。Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.
DOI 文献を開くコピーしました。