論文の概要: Speeding Up the NSGA-II via Dynamic Population Sizes

• arxiv url: http://arxiv.org/abs/2509.01739v1
• Date: Mon, 01 Sep 2025 19:45:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 15:17:03.832329
• Title: Speeding Up the NSGA-II via Dynamic Population Sizes
• Title（参考訳）: 動的人口サイズによるNSGA-IIの高速化
• Authors: Benjamin Doerr, Martin S. Krejca, Simon Wietheger,
• Abstract要約: 本稿では, 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)
• 参考スコア（独自算出の注目度）: 24.440172242035228
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) at once, MOEAs are typically run with a large, static population of solution candidates, which can slow down the algorithm. We propose the dynamic NSGA-II (dNSGA-II), which is based on the popular NSGA-II and features a non-static population size. The dNSGA-II starts with a small initial population size of four and doubles it after a user-specified number $\tau$ of function evaluations, up to a maximum size of $\mu$. Via a mathematical runtime analysis, we prove that the dNSGA-II with parameters $\mu \geq 4(n + 1)$ and $\tau \geq \frac{256}{50} e n$ computes the full Pareto front of the \textsc{OneMinMax} benchmark of size $n$ in $O(\log(\mu) \tau + \mu \log(n))$ function evaluations, both in expectation and with high probability. For an optimal choice of $\mu$ and $\tau$, the resulting $O(n \log(n))$ runtime improves the optimal expected runtime of the classic NSGA-II by a factor of $\Theta(n)$. In addition, we show that the parameter $\tau$ can be removed when utilizing concurrent runs of the dNSGA-II. This approach leads to a mild slow-down by a factor of $O(\log(n))$ compared to an optimal choice of $\tau$ for the dNSGA-II, which is still a speed-up of $\Theta(n / \log(n))$ over the classic NSGA-II.
• Abstract（参考訳）: 多目的進化アルゴリズム(MOEA)は、多目的問題に対して最も広く、かつうまく適用された最適化アルゴリズムの一つである。 しかしながら、多くの最適トレードオフ(パレート・オプティマ)を一度に保存するために、MOEAは通常、大量の静的な解候補で実行され、アルゴリズムを遅くすることができる。 本稿では, NSGA-II をベースとした動的NSGA-II (dNSGA-II) を提案する。 dNSGA-IIは、4つの小さな初期集団サイズから始まり、ユーザが指定した関数評価の$\tau$の後に2倍になり、最大サイズは$\mu$になる。 数学的ランタイム解析により、dNSGA-II のパラメータ $\mu \geq 4(n + 1)$ と $\tau \geq \frac{256}{50} e n$ が $n$ in $O(\log(\mu) \tau + \mu \log(n))$ 関数評価を期待と高い確率で計算することを証明する。 最適な$\mu$と$\tau$を選択すると、結果の$O(n \log(n))$ランタイムは古典的なNSGA-IIの最適なランタイムを$\Theta(n)$で改善する。 さらに、dNSGA-IIの同時実行を利用する場合、$\tau$パラメータを削除可能であることを示す。 このアプローチは、古典的なNSGA-IIよりも$\Theta(n / \log(n))$のスピードアップである dNSGA-II に対して$\tau$ の最適選択と比較すると、$O(\log(n))$ の緩やかに低下する。

関連論文リスト

• 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)
• Speeding Up the NSGA-II With a Simple Tie-Breaking Rule [9.044970217182117]
  我々は、次の人口の選択において、単純なタイブレーキングルールを解析する。 従来のOneMinMax、LeadingOnesZero、OneJumpJumpベンチマークでベンチマークの有効性を証明する。 両目的問題に対して,最小サイズ以上の集団規模を適度に増やすと,実行時保証が増加しないことを示す。
  論文  参考訳（メタデータ） (2024-12-16T16:15:37Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• A First Runtime Analysis of the NSGA-II on a Multimodal Problem [17.049516028133958]
  この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。 この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。
  論文  参考訳（メタデータ） (2022-04-28T19:44:47Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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