論文の概要: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining
the Inefficiency For Three or More Objectives
- arxiv url: http://arxiv.org/abs/2211.13084v1
- Date: Wed, 23 Nov 2022 16:15:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 13:46:10.400831
- Title: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining
the Inefficiency For Three or More Objectives
- Title（参考訳）: NSGA-IIのランタイム分析:3つ以上の目的に対する非効率性の証明、定量化、説明
- Authors: Weijie Zheng, Benjamin Doerr
- Abstract要約: NSGA-IIは多目的最適化問題を解く最も顕著なアルゴリズムの1つである。
NSGA-IIは多数の目的に対して効果が低いことを示す。
- 参考スコア（独自算出の注目度）: 15.56430085052365
- 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 and, very
recently, also competitive mathematical performance guarantees, 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 prove and
quantify this phenomenon. We show that even on the simple 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. Our proofs suggest that 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ベンチマークでは、全ての解がパレート最適である場合でも、NSGA-IIは大きな集団を持つため、全パレートフロント(全てのパレートオプティマのオブジェクトベクトル)を指数時間で計算することはできない。
我々の証明は、この予期せぬ行動の理由は、群集距離の計算において、異なる目的が独立して考慮されるという事実にあることを示唆している。
これは2つの目的に対する問題ではなく、一方の目的に沿ったペアワイズ非可換な解の任意のソートもまた、他方の目的(逆順序)に従ってそのようなソートである。
関連論文リスト
- A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization [13.277972583315051]
最近の理論的研究により、NSGA-IIは2つ以上の目的を持つ問題を解くのに非常に困難であることが示されている。
我々は、これらの過去の研究の洞察を用いて、真に群集距離と呼ばれる群集距離の変種を定義する。
本アルゴリズムは,OneMinMax,COCZ,LOTZ,OJZJ$_k$問題の多目的バージョンを解くことができることを示す。
論文 参考訳（メタデータ） (2024-07-25T01:09:58Z) - UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms [10.165640083594573]
従来のベンチマークでは,SEMO,グローバルSEMO,SMS-EMOAアルゴリズムのほぼ28のランタイム保証が証明されている。
このような厳密な境界がこれらのMOEAの多目的利用に対して証明されたのはこれが初めてである。
論文 参考訳（メタデータ） (2024-04-19T09:46:59Z) - Runtime Analyses of NSGA-III on Many-Objective Problems [10.955844285189372]
本稿では,一般的な多目的ベンチマーク問題mLOTZ,mOMM,mCOCZにおけるNSGA-IIIのランタイム解析について述べる。
これらのパラメータは,問題次元,目的数,適合範囲によってどのようにスケールするかを示す。
我々の知る限り、これらは3つ以上の目的に対してNSGA-IIIの最初のランタイム解析である。
論文 参考訳（メタデータ） (2024-04-17T14:39:14Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。