論文の概要: A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update

• arxiv url: http://arxiv.org/abs/2505.01256v3
• Date: Wed, 21 May 2025 16:20:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-22 13:19:52.288268
• Title: A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update
• Title（参考訳）: 多目的マルチモーダル問題におけるNSGA-IIIの初回実行時解析:確率的人口更新による推定指数の高速化
• Authors: Andre Opris,
• Abstract要約: NSGA-IIIは進化的多目的最適化において顕著なアルゴリズムである。 本稿では,多目的$OJZJfull$ベンチマーク上でNSGA-IIIの厳密なランタイム解析を行う。 NSGA-IIIは, ω(nd/2ln)$ の $mu に対して$mu/nd/2$ の係数で NSGA-II よりも高速であることを示す。
• 参考スコア（独自算出の注目度）: 1.223779595809275
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is well-suited for optimizing functions with more than three objectives, setting it apart from the classic NSGA-II. However, theoretical insights about NSGA-III of when and why it performs well are still in its early development. This paper addresses this point and conducts a rigorous runtime analysis of NSGA-III on the many-objective $\OJZJfull$ benchmark ($\OJZJ$ for short), providing runtime bounds where the number of objectives is constant. We show that NSGA-III finds the Pareto front of $\OJZJ$ in time $O(n^{k+d/2}+ \mu n \ln(n))$ where $n$ is the problem size, $d$ is the number of objectives, $k$ is the gap size, a problem specific parameter, if its population size $\mu \in 2^{O(n)}$ is at least $(2n/d+1)^{d/2}$. Notably, NSGA-III is faster than NSGA-II by a factor of $\mu/n^{d/2}$ for some $\mu \in \omega(n^{d/2})$. We also show that a stochastic population update, proposed by~\citet{UpBian}, provably guarantees a speedup of order $\Theta((k/b)^{k-1})$ in the runtime where $b>0$ is a constant. Besides~\cite{DoerrNearTight}, this is the first rigorous runtime analysis of NSGA-III on \OJZJ. Proving these bounds requires a much deeper understanding of the population dynamics of NSGA-III than previous papers achieved.
• Abstract（参考訳）: NSGA-IIIは進化的多目的最適化において顕著なアルゴリズムである。 3つ以上の目的を持つ関数を最適化するのに適しており、古典的なNSGA-IIとは別物となっている。 しかし、NSGA-IIIの時期と理由に関する理論的知見は、まだ初期段階にある。 本稿では、この点に対処し、多目的$\OJZJfull$ベンチマーク(略して$\OJZJ)上でNSGA-IIIの厳密なランタイム解析を行い、目的の数が一定となるランタイム境界を提供する。 NSGA-III が $\OJZJ$ in time $O(n^{k+d/2}+ \mu n \ln(n))$ where $n$ is the problem size, $d$ is the number of objectives, $k$ is the gap size, a problem specific parameters, if its population size $\mu \in 2^{O(n)}$ is least $(2n/d+1)^{d/2}$ であることを示す。 特に、NSGA-IIIは、ある$\mu \in \omega(n^{d/2})$に対して$\mu/n^{d/2}$の係数でNSGA-IIよりも高速である。 また、b>0$ が定数である実行時の順序 $\Theta((k/b)^{k-1})$ の高速化を確実に保証する。 ~\cite{DoerrNearTight} に加えて、これは OJZJ 上の NSGA-III の厳密なランタイム解析としては初めてである。 これらの境界を証明するためには、これまでの論文よりもNSGA-IIIの人口動態の深い理解が必要である。

関連論文リスト

• Speeding Up the NSGA-II With a Simple Tie-Breaking Rule [9.044970217182117]
  我々は、次の人口の選択において、単純なタイブレーキングルールを解析する。 従来のOneMinMax、LeadingOnesZero、OneJumpJumpベンチマークでベンチマークの有効性を証明する。 両目的問題に対して,最小サイズ以上の集団規模を適度に増やすと,実行時保証が増加しないことを示す。
  論文  参考訳（メタデータ） (2024-12-16T16:15:37Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• 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)
• From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds [10.107150356618588]
  我々は, NSGA-IIが適切な個体数を持つためには$Omega(Nnlog n)$関数評価が必要であることを証明した。 2つの目的の群集距離の寄与を計算するために、先頭定数を含む厳密な実行時推定値を得る。
  論文  参考訳（メタデータ） (2022-09-28T10:11:20Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)

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

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