論文の概要: Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds

• arxiv url: http://arxiv.org/abs/2511.07125v1
• Date: Mon, 10 Nov 2025 14:11:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:45.29289
• Title: Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds
• Title（参考訳）: NSGA-III:タイトランタイム境界の人口動態の厳密な理解に向けて
• Authors: Andre Opris,
• Abstract要約: 双目的のOneMinMax(2$-OMM)問題に対してNSGA-IIIの厳密なランタイム境界を証明した。 これは、古典的なベンチマーク問題でNSGA-IIIにバウンドされた最初の低いランタイムである。 また、$m$-objective OneMinMax 問題において、NSGA-III の最もよく知られた上限も改善する。
• 参考スコア（独自算出の注目度）: 5.482532589225553
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Evolutionary algorithms are widely used for solving multi-objective optimization problems. A prominent example is NSGA-III, which is particularly well suited for solving problems involving more than three objectives, distinguishing it from the classical NSGA-II. Despite its empirical success, the theoretical understanding of NSGA III remains very limited, especially with respect to runtime analysis. A central open problem concerns its population dynamics, which involve controlling the maximum number of individuals sharing the same fitness value during the exploration process. In this paper, we make a significant step towards such an understanding by proving tight runtime bounds for NSGA-III on the bi-objective OneMinMax ($2$-OMM) problem. Firstly, we prove that NSGA-III requires $\Omega(n^2 \log(n) / \mu)$ generations in expectation to optimize $2$-OMM assuming the population size $\mu$ satisfies $n+1 \leq \mu =O(\log(n)^c(n+1))$ where $n$ denotes the problem size and $c<1$ is a constant. Apart from~\cite{opris2025multimodal}, this is the first proven lower runtime bound for NSGA-III on a classical benchmark problem. Complementing this, we secondly improve the best known upper bound of NSGA-III on the $m$-objective OneMinMax problem ($m$-OMM) of $O(n \log(n))$ generations by a factor of $\mu /(2n/m + 1)^{m/2}$ for a constant number $m$ of objectives and population size $(2n/m + 1)^{m/2} \leq \mu \in O(\sqrt{\log(n)} (2n/m + 1)^{m/2})$. This yields tight runtime bounds in the case $m = 2$, and the surprising result that NSGA-III beats NSGA-II by a factor of $\mu/n$ in the expected runtime.
• Abstract（参考訳）: 進化的アルゴリズムは多目的最適化問題の解法に広く用いられている。 NSGA-IIIは3つ以上の目的を含む問題の解決に特に適しており、古典的なNSGA-IIと区別されている。 実験的な成功にもかかわらず、NSGA IIIの理論的理解は、特に実行時解析に関して非常に限定的である。 中心的なオープン問題は、探索プロセス中に同じフィットネス値を共有する最大数の個人を制御することを含む、人口動態に関するものである。 本稿では,二目的のOneMinMax(2$-OMM)問題に対してNSGA-IIIの厳密なランタイム境界を証明し,そのような理解に向けて大きな一歩を踏み出した。 まず、NSGA-IIIが人口規模を$n+1 \leq \mu =O(\log(n)^c(n+1))$$n$が問題サイズを表し、$c<1$が定数であることを仮定して、2$OMMを最適化するために$\Omega(n^2 \log(n) / \mu)$世代が必要であることを証明する。 ~\cite{opris2025multimodal} 以外は、古典的なベンチマーク問題においてNSGA-IIIで証明された最初の低ランタイムである。 これを補うと、$m$-objective OneMinMax problem ($m$-OMM) of $O(n \log(n))$ generation by a factor of $\mu /(2n/m + 1)^{m/2}$ for a constant number $m$ of objectives and population size $(2n/m + 1)^{m/2} \leq \mu \in O(\sqrt{\log(n)} (2n/m + 1)^{m/2})$である。 NSGA-III が NSGA-II を$\mu/n$ で破る驚くべき結果となる。

関連論文リスト

• Speeding Up the NSGA-II via Dynamic Population Sizes [24.440172242035228]
  本稿では, NSGA-II をベースとした動的NSGA-II (dNSGA-II) を提案する。 パラメータ $mu geq 4(n + 1)$ と $tau geq frac25650 e n$ の dNSGA-II が scOneMinMax ベンチマークのフルフロントを計算していることを示す。 最適な $mu$ と $tau$ を選択するには、$O(n log(n)
  論文  参考訳（メタデータ） (2025-09-01T19:45:17Z)
• A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update [1.223779595809275]
  NSGA-IIIは進化的多目的最適化において顕著なアルゴリズムである。 本稿では,多目的$OJZJfull$ベンチマーク上でNSGA-IIIの厳密なランタイム解析を行う。 NSGA-IIIは, ω(nd/2ln)$ の $mu に対して$mu/nd/2$ の係数で NSGA-II よりも高速であることを示す。
  論文  参考訳（メタデータ） (2025-05-02T13:26:05Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。 次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
  論文  参考訳（メタデータ） (2024-11-21T17:41:09Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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