論文の概要: 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つの目的に対する問題ではなく、一方の目的に沿ったペアワイズ非可換な解の任意のソートもまた、他方の目的(逆順序)に従ってそのようなソートである。

関連論文リスト

• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Non-Myopic Multi-Objective Bayesian Optimization [64.31753000439514]
  多目的最適化問題を解くために、有限水平逐次実験設計の問題を考察する。 この問題は、材料設計を含む多くの現実世界の応用で発生する。 我々はMOO問題に対する最初の非ミオピック手法を提案する。
  論文  参考訳（メタデータ） (2024-12-11T04:05:29Z)
• 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)
• 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)
• 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)

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

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