論文の概要: Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer
- arxiv url: http://arxiv.org/abs/2511.07150v1
- Date: Mon, 10 Nov 2025 14:43:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-11 21:18:45.303787
- Title: Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer
- Title（参考訳）: SPEA2多目的最適化のためのランタイム保証の改善
- Authors: Benjamin Doerr, Martin S. Krejca, Milan Stanković,
- Abstract要約: SPEA2 は NSGA-II とは全く異なる集団動態を持つことを示す。
O(nk)$の最高のランタイム保証は、$mu = Theta+1n)$と$lambda = O(nk)$に対してのみ達成されるだけでなく、任意の$muでは、lambda = O(nk)$に対して達成される。
- 参考スコア（独自算出の注目度）: 21.23874800091344
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size $\mu \ge n - 2k + 3$ and offspring population size $\lambda$ computes the Pareto front of the OneJumpZeroJump benchmark with gap size $k$ in an expected number of $O( (\lambda+\mu)n + n^{k+1})$ function evaluations. This shows that the best runtime guarantee of $O(n^{k+1})$ is not only achieved for $\mu = \Theta(n)$ and $\lambda = O(n)$ but for arbitrary $\mu, \lambda = O(n^k)$. Thus, choosing suitable parameters -- a key challenge in using heuristic algorithms -- is much easier for the SPEA2 than the NSGA-II.
- Abstract（参考訳）: NSGA-IIと共に、SPEA2は最も広く使われている支配に基づく多目的進化アルゴリズムの一つである。
両方のアルゴリズムでは、既知のランタイム保証は集団サイズで線形であり、NSGA-IIでは、一致した下位境界が存在する。
SPEA2のより複雑な選択機構について慎重に研究し、人口動態が全く異なることを示す。
これらの結果から,OneMinMaxやLeadingOnesTrailingZeros,OneJumpZeroJumpといった,人口規模に依存しないベンチマークのランタイム保証が証明された。
例えば、親集団サイズ$\mu \ge n - 2k + 3$および子孫集団サイズ$\lambda$は、期待数$O( (\lambda+\mu)n + n^{k+1})$関数評価において、ギャップサイズ$k$のOneJumpZeroJumpベンチマークのParetoフロントを計算する。
これは、$O(n^{k+1})$の最高のランタイム保証が、$\mu = \Theta(n)$と$\lambda = O(n)$に対してのみ達成されるだけでなく、任意の$\muでは \lambda = O(n^k)$に対して達成されることを示している。
したがって、ヒューリスティックアルゴリズムを使用する上で重要な課題である適切なパラメータを選択することは、NSGA-IIよりもSPEA2にとってずっと簡単である。
関連論文リスト
- Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds [5.482532589225553]
双目的のOneMinMax(2$-OMM)問題に対してNSGA-IIIの厳密なランタイム境界を証明した。
これは、古典的なベンチマーク問題でNSGA-IIIにバウンドされた最初の低いランタイムである。
また、$m$-objective OneMinMax 問題において、NSGA-III の最もよく知られた上限も改善する。
論文 参考訳（メタデータ） (2025-11-10T14:11:07Z) - 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) - Speeding Up the NSGA-II With a Simple Tie-Breaking Rule [9.044970217182117]
我々は、次の人口の選択において、単純なタイブレーキングルールを解析する。
従来のOneMinMax、LeadingOnesZero、OneJumpJumpベンチマークでベンチマークの有効性を証明する。
両目的問題に対して,最小サイズ以上の集団規模を適度に増やすと,実行時保証が増加しないことを示す。
論文 参考訳（メタデータ） (2024-12-16T16:15:37Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - 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) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。