Fugu-MT 論文翻訳(概要): Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives

論文の概要: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives

arxiv url: http://arxiv.org/abs/2211.13084v3
Date: Mon, 19 Jun 2023 14:24:43 GMT
ステータス: 処理完了
システム内更新日: 2023-06-22 04:58:18.009406
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は多数の目的に対して効果が低いことを示す。
参考スコア（独自算出の注目度）: 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, 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つの目的に対する問題ではなく、一方の目的に沿ったペアワイズ非可換な解の任意のソートもまた、他方の目的(逆順序)に従ってそのようなソートである。

関連論文リスト

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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。