論文の概要: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining
the Inefficiency For Many Objectives
- arxiv url: http://arxiv.org/abs/2211.13084v4
- Date: Tue, 26 Sep 2023 12:32:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-27 18:27:17.891406
- Title: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining
the Inefficiency For Many Objectives
- Title(参考訳): NSGA-IIのランタイム分析:多くの目的に対する非効率性の証明、定量化、説明
- Authors: Weijie Zheng, Benjamin Doerr
- Abstract要約: NSGA-IIは多目的最適化問題を解く最も顕著なアルゴリズムの1つである。
NSGA-IIは多数の目的に対して効果が低いことを示す。
- 参考スコア(独自算出の注目度): 16.904475483445452
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The NSGA-II is one of the most prominent algorithms to solve multi-objective
optimization problems. Despite numerous successful applications, several
studies have shown that the NSGA-II is less effective for larger numbers of
objectives. In this work, we use mathematical runtime analyses to rigorously
demonstrate and quantify this phenomenon. We show that even on the simple
$m$-objective generalization of the discrete OneMinMax benchmark, where every
solution is Pareto optimal, the NSGA-II also with large population sizes cannot
compute the full Pareto front (objective vectors of all Pareto optima) in
sub-exponential time when the number of objectives is at least three. The
reason for this unexpected behavior lies in the fact that in the computation of
the crowding distance, the different objectives are regarded independently.
This is not a problem for two objectives, where any sorting of a pair-wise
incomparable set of solutions according to one objective is also such a sorting
according to the other objective (in the inverse order).
- Abstract(参考訳): NSGA-IIは多目的最適化問題を解く最も顕著なアルゴリズムの1つである。
多くの応用が成功したにもかかわらず、NSGA-IIは多数の目的に対して効果が低いことがいくつかの研究で示されている。
本研究では,この現象の厳密な実証と定量化に数学的ランタイム解析を用いる。
すべての解がパレート最適である離散的 oneminmax ベンチマークの単純な $m$-objective 汎化においても、人口規模が大きい nsga-ii では、目的数が少なくとも 3 である場合、全パレートフロント(すべてのパレートオプティマの目的ベクトル)をサブ指数時間で計算することはできない。
この予期せぬ行動の理由は、密集距離の計算において、異なる目的が独立に考慮されるという事実にある。
これは2つの目的に対する問題ではなく、一方の目的に沿ったペアワイズ非可換な解の任意のソートもまた、他方の目的(逆順序)に従ってそのようなソートである。
関連論文リスト
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization [16.904475483445452]
本稿では,多目的最適化のためのSMS-EMOAの厳密な実行時解析を行う。
まず,二目的OJZJベンチマークの m-目的 mOJZJ 問題である多目的 mOJZJ 問題を提案する。
SMS-EMOAは、このベンチマークの全前面を、期待される数$O(M2 nk)$で計算する。
論文 参考訳(メタデータ) (2023-12-16T02:23:09Z) - Towards Running Time Analysis of Interactive Multi-objective
Evolutionary Algorithms [23.815981112784552]
本稿では,実際のiMOEAに対して,最初の実行時間解析(EAの本質的理論的側面)を提供する。
我々は、OneMinMaxとOneJumpZeroJumpの問題を解くために、よく開発された対話型NSGA-IIのランニングタイムが、それぞれ$O(n log n)$と$O(nk)$であることを示す。
論文 参考訳(メタデータ) (2023-10-12T14:57:47Z) - BOtied: Multi-objective Bayesian optimization with tied multivariate
ranks [49.85896045032822]
非支配解と最高多変量階との自然な関係を示し、これは合同累積分布関数(CDF)の最外層線と一致する。
我々はCDFインジケータに基づくBOtiedと呼ばれる取得関数を提案する。
論文 参考訳(メタデータ) (2023-06-01T04:50:06Z) - A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic
Algorithm III (NSGA-III) [9.853329403413701]
NSGA-II (Non-Maninated Sorting Genetic Algorithm II) は、実世界の応用において最も顕著な多目的進化アルゴリズムである。
NSGA-IIIは2つ以上の目的をうまく扱うことを目的としたNSGA-IIの改良である。
論文 参考訳(メタデータ) (2022-11-15T15:10:36Z) - Multi-Objective GFlowNets [59.16787189214784]
本稿では,多目的最適化の文脈において,多様な候補を生成する問題について検討する。
薬物発見やマテリアルデザインといった機械学習の多くの応用において、目標は、競合する可能性のある目標のセットを同時に最適化する候補を生成することである。
GFlowNetsをベースとした多目的GFlowNets(MOGFNs)を提案する。
論文 参考訳(メタデータ) (2022-10-23T16:15:36Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - Provable Stochastic Optimization for Global Contrastive Learning: Small
Batch Does Not Harm Performance [53.49803579981569]
各正の対と全ての負の対をアンカーポイントで対比する、コントラスト学習のグローバルな目的を考える。
SimCLRのような既存のメソッドは、十分な結果を得るために大きなバッチサイズを必要とする。
本稿では,SogCLRという表現のグローバルコントラスト学習を解くためのメモリ効率の最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-24T22:16:53Z) - Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic
Algorithm II (NSGA-II) [16.904475483445452]
NSGA-IIにも実行時解析が可能であることを示す。
NSGA-IIは,パレートフロントの4倍の大きさの個体群を持つため,SEMOアルゴリズムやGSEMOアルゴリズムと同じランタイム保証を満たす。
論文 参考訳(メタデータ) (2021-12-16T03:00:20Z) - Many Objective Bayesian Optimization [0.0]
マルチオブジェクトベイズ最適化(MOBO)は、ブラックボックスの同時最適化に成功している一連の手法である。
特に、MOBO法は、多目的最適化問題における目的の数が3以上である場合に問題があり、これは多くの目的設定である。
GPが測定値とアルゴリズムの有効性の予測分布を予測できるような,玩具,合成,ベンチマーク,実実験のセットで実証的な証拠を示す。
論文 参考訳(メタデータ) (2021-07-08T21:57:07Z) - Tackling the Objective Inconsistency Problem in Heterogeneous Federated
Optimization [93.78811018928583]
本稿では、フェデレートされた異種最適化アルゴリズムの収束性を分析するためのフレームワークを提供する。
我々は,高速な誤差収束を保ちながら,客観的な矛盾を解消する正規化平均化手法であるFedNovaを提案する。
論文 参考訳(メタデータ) (2020-07-15T05:01:23Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳(メタデータ) (2020-06-12T00:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。