Skip to content
検索結果に戻る

ロバストNSGA-II — 不確実性下での多目的最適化

提唱者
Kalyanmoy Deb and Himanshu Gupta
年
2006
種類
Robust evolutionary multi-objective optimization algorithm
系統
Simulation / optimization

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

ロバストNSGA-IIは、古典的なNSGA-II進化的アルゴリズムを拡張し、パラメータの不確実性を考慮に入れます。これにより、入力パラメータが公称値から逸脱した場合でも高い性能を維持するパレート最適解を見つけます。単一の点での目的値の最適化ではなく、不確実性の実現値の範囲または分布にわたって各候補解を評価し、パレート優越性に加えてロバスト性を選択基準とします。

手法の背後にある直感

実際には、工学設計や政策決定は不確実な運用条件に直面します。例えば、材料特性のばらつき、需要予測と現実の乖離、環境負荷の変動などです。公称パラメータ値で最適に見える解でも、もっともらしい逸脱条件下では性能が著しく低下する可能性があります。ロバストNSGA-IIは、各候補解をその設計点だけでなく、不確実なシナリオの近傍またはサンプルにわたって評価し、各目的の期待値と分散(または最悪ケース性能)を選択基準とすることで、この問題に対処します。したがって、このアルゴリズムは、公称性能のわずかな損失と引き換えに信頼性の大幅な向上をもたらし、不確実性下で競争力と安定性の両方を備えた解のパレートフロントを提供します。

歴史学

ロバストNSGA-IIは、2006年にDebとGuptaによって形式化されたロバスト多目的最適化フレームワークから生まれました。彼らはNSGA-IIの選択メカニズムに明示的なロバスト性指標を導入しました。基礎となるNSGA-IIアルゴリズムは、2002年にDeb、Pratap、Agarwal、Meyarivanによって発表されました。その後、工学設計、オペレーションズリサーチ、エネルギーシステムの研究者による研究により、確率的制約、混合不確実性タイプ、サロゲート支援ロバスト性評価を伴う問題にフレームワークが拡張されました。

使うべき場面

多目的問題に不確実なパラメータ(材料特性、需要、コスト、環境条件など)が含まれ、解が単一の設計点だけでなく、もっともらしい公称値からの逸脱に対しても許容可能なままである必要がある場合に、ロバストNSGA-IIを使用します。これは、工学設計、需要の不確実性下でのサプライチェーン計画、確率的発電を伴うエネルギーシステム最適化に適しています。計算予算が非常に厳しい場合は避けてください。なぜなら、世代ごとに個体あたりM個の不確実性サンプルを評価すると、関数評価コストがM倍になるためです。また、不確実性が目的変動に比べて無視できる場合、または候補あたり2〜3回の目的関数評価しか実行できない場合も避けてください。その場合は、標準NSGA-IIまたはサロゲート支援法の方が効率的です。

限界と注意点

  • 計算コストはM(評価あたりの不確実性サンプル数)に比例するため、目的評価がシミュレーションベースまたは時間のかかるものである場合は高価になります。
  • ロバスト性指標の選択(平均、分散、最悪ケース)は、どの解が好まれるかに大きく影響し、普遍的に正しい選択はありません。
  • 標準NSGA-IIと同じ理由で、3つ以上の目的の場合、性能が低下します。混雑距離が高次元の目的空間で識別力を失うためです。
  • ロバスト性を確実に推定するには十分に大きなMが必要ですが、Mが小さいと確率的ノイズが導入され、パレートフロントの近似を誤導する可能性があります。
  • 不確実性集合が不連続である場合や、不確実なパラメータ間の相関が複雑でサンプリングが難しい場合には、適用が容易ではありません。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 不確実性下で良好な性能を発揮することが明示的に検証されたパレート最適解を生成し、実際に性能が著しく低下する解のリスクを低減します。
  • NSGA-IIの高速非劣ソートとエリート主義を継承しており、ロバストに非劣な解が世代を超えて破棄されることがありません。
  • ロバスト性指標の柔軟性:リスク選好度に応じて、期待値、分散ペナルティ、最悪ケース、または確率的制約を代替できます。
  • コアとなる選択メカニズムを変更することなく、連続および離散の両方の決定空間で機能します。
  • 意思決定者に対し、多目的バランスとロバスト性レベルの両方で異なるトレードオフの選択肢を提供し、情報に基づいた選好の明確化を支援します。

応用

  • 変動する大気条件下での抗力と揚力のトレードオフを最適化するロバストな空力設計
  • 確率的な顧客需要下でのコストとサービスレベルのバランスをとるサプライチェーンネットワーク設計
  • 不確実な再生可能エネルギー発電と負荷プロファイルを伴うロバストなエネルギーシステム計画
  • 製造公差と負荷変動を考慮した多目的構造最適化
  • 期待リターンと分散のトレードオフを伴う市場の不確実性下でのポートフォリオ最適化
  • 気候変動による不確実な流入シナリオ下での配分と信頼性を最適化する水資源管理

使い方

使い方

1

決定変数ベクトルを符号化するN個の候補解からなる初期集団Pを生成します。不確実性モデルを定義します。どのパラメータが不確実であるか、それらの確率分布または摂動集合、および使用するロバスト性指標(期待値、分散、最悪ケース、または重み付き組み合わせ)を指定します。ベースラインの適合性を確立するために、すべての解を公称条件下で評価します。

2

集団内の各候補解xについて、指定されたパラメータ分布からM個の不確実性実現値を抽出します(または構造化された近傍を列挙します)。各実現値の下で目的関数をすべて評価し、結果をロバストな目的推定値に集約します。一般的な集約方法としては、期待性能のロバスト性推定値として平均を使用し、分散を考慮するために標準偏差に比例するペナルティを加える方法があります。この場合、ロバストな目的は f_robust(x) = mean[f(x, xi)] + lambda * std[f(x, xi)] となります。

3

公称値ではなくロバストな目的推定値を使用して、集団に高速非劣ソートを適用します。ロバストな目的のパレート優越性に基づいて、各解を非劣フロントF1、F2などに割り当てます。F1の解はロバストに非劣であり、他のどの解もすべてのロバストな目的で同時に優れているわけではありません。

4

各非劣フロント内で、各ロバスト目的軸に沿ってすべての解の混雑距離を計算します。混雑距離は、ロバスト目的空間における解の孤立度を定量化し、ロバストなパレートフロント全体にわたる広がりを促進します。混雑距離が大きい解は、疎に分布する領域を占めており、多様性を維持するために選択時に優先されます。

5

ロバストフロントと混雑距離に対する混雑比較演算子を使用して、二点トーナメント選択を適用します。交叉(シミュレーテッドバイナリ交叉)と突然変異(多項式突然変異)演算子を介して、サイズNの子孫集団Qを生成します。個体ごとにM個の不確実性サンプルを用いたロバスト性評価により、子孫解を再評価します。Mが大きい場合、このステップが実行時間を支配します。

6

親集団Pと子孫集団Qを結合し、2N個の解からなるプールを作成します。ロバストな非劣性と混雑距離によって再ソートします。次の世代を形成するために最適なN個の個体を選択し、エリート主義を維持します。最大世代数に達したとき、ハイパーボリュームが停滞したとき、または計算予算が尽きたときに終了します。最終的なロバストパレートフロントF1を返します。

よくある落とし穴

  • 評価あたりの不確実性サンプル数が少なすぎる(Mが20〜30未満)と、評価ノイズが導入され、非劣性ランキングが歪み、信頼性の低いロバストパレートフロントが生成されます。
  • 目的値のロバスト性と最適解のロバスト性を混同すること:目的空間でロバストな解であっても、実装が難しい精密な決定変数値を必要とする場合があります。
  • ロバストな目的が同等の尺度にあるかどうかを確認せずに、ロバスト目的空間でNSGA-IIのデフォルトの混雑距離を適用すること。距離を計算する前に目的を正規化してください。
  • 単一のレプリケーションを実行し、その結果を決定的なものとして扱うこと。常に複数の独立したレプリケーションを実行し、確率的変動を考慮するためにハイパーボリューム統計を報告してください。
  • 感度分析なしにラムダ(分散ペナルティの重み)をアドホックに選択すること。選択されたラムダは、明示的かつ正当化されるべきリスク態度を暗黙的に符号化しています。

よくある質問

ロバストNSGA-IIは標準NSGA-IIとどう違うのですか?

標準NSGA-IIは、各候補解を公称パラメータ値で評価し、それらの目的値をパレート優越性のために使用します。ロバストNSGA-IIは、不確実なパラメータのM個の実現値にわたって各解を評価し、結果をロバストな目的推定値(例:平均と分散)に集約し、それらの推定値を優越性ランキングに使用します。これにより、計算コストはM倍に増加しますが、パラメータが公称値から逸脱した場合でも競争力を維持する解が得られます。

個体あたり何個の不確実性サンプルMを使用すべきですか?

普遍的なルールはありません。目的評価が安価な場合、一般的な出発点はM = 30〜50のモンテカルロサンプルです。高価な評価の場合、M = 5〜10が必要になる場合があります。感度分析を実行し、ロバストな目的推定値が安定するまでMを増やしてください。準乱数(ラテン超方格またはSobol)サンプリングは、同じMに対して純粋なランダムサンプリングよりも優れたカバレッジを達成します。

3つ以上の目的でロバストNSGA-IIを使用できますか?

アルゴリズムは適用できますが、標準NSGA-IIと同じ理由で性能が低下します。混雑距離が高次元の目的空間で識別力を失い、ほとんどの解が最初の非劣フロントに集中するためです。4つ以上の目的の場合、混雑距離の代わりに参照点ベースの選択を使用するNSGA-IIIのロバストな変種を検討してください。

どのロバスト性指標を選択すべきですか?

選択はリスク態度に依存します。平均のみの最適化は、変動性をペナルティなしで期待性能を目標とします。これは繰り返しの意思決定に適しています。平均と分散の組み合わせは不安定性をペナルティとし、リスク回避的な状況に適しています。最悪ケース(ミニマックス)最適化は非常に保守的であり、単一の壊滅的な実現値が許容できない場合にのみ適切です。選択を文書化し、正当化してください。なぜなら、それはロバストパレートフロントに現れる解に実質的に影響を与えるからです。

返された解が本当にロバストであることをどのように検証しますか?

アルゴリズム終了後、各パレートフロント解を、最適化中に使用されたサンプルとは独立した、新しい大規模な不確実性サンプルセット(例:M = 1000)で再評価します。目的の平均と分散が、進化的実行からの推定値と一致するかどうかを確認します。大きな不一致がある場合、最適化中のMが小さすぎたか、不確実性モデルが誤って指定されていたことを示します。

関連する手法

参考文献

  1. 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 文献を開く
    コピーしました。
  2. Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463-494.

    DOI 文献を開く
    コピーしました。