論文の概要: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm

• arxiv url: http://arxiv.org/abs/2505.01266v1
• Date: Fri, 02 May 2025 13:40:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-05 17:21:20.041094
• Title: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm
• Title（参考訳）: GSEMO多目的進化アルゴリズムの人口動態の理解から学ぶタイトランタイム保証
• Authors: Benjamin Doerr, Martin Krejca, Andre Opris,
• Abstract要約: 本稿では,GSEMO(Global Simple Evolution Multi-Objective)アルゴリズムのダイナミクスについて検討する。 我々は、古典的なCountingOnesCountingZeros(COCZ)ベンチマークに対して、$Omega(n2 log n)$の下位境界を証明した。 我々の手法は他の古典的なベンチマークにまで拡張し、例えば、最初の$Omega(nk+1)$ lower bound for the OJZJ benchmark(英語版)などである。
• 参考スコア（独自算出の注目度）: 9.966672345291707
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order $\Omega(n^2 \log n)$, for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time $O(n^2)$, improving over the previous estimate of $O(n^2 \log n)$ for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first $\Omega(n^{k+1})$ lower bound for the OJZJ benchmark in the case that the gap parameter is $k \in \{2,3\}$. We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs.
• Abstract（参考訳）: GSEMO(Global Simple Evolution Multi-objective Optimizationr)は、単純だが効果的な多目的進化アルゴリズム(MOEA)である。 非支配的な解のみを維持することにより、最適化プロセスのニーズに自動的に適応する可変な集団サイズを持つ。 動的個体群の大きさの欠点は、このアルゴリズムの個体群動態が理解しにくく、例えば、散発的厳密な実行時解析のみが存在するという事実である。 本研究では,GSEMOのダイナミクス,特にCountingOnesCountingZeros(COCZ)ベンチマークに対する理解を深める。 このことから、20年以上知られている半順序上界と初めて一致する位数 $\Omega(n^2 \log n)$ の下位境界を証明できる。 また、GSEMO は時間 $O(n^2)$ においてパレートフロントの任意の定数を発見でき、最初のパレート最適点を見つけるために、以前の推定値 $O(n^2 \log n)$ よりも改善されることを示す。 我々の手法は他の古典的ベンチマークにまで拡張し、例えば、ギャップパラメータが$k \in \{2,3\}$の場合、最初の$\Omega(n^{k+1})$ lower bound for the OJZJ benchmark。 したがって、我々はMOEAの数学的解析に新しい手法が役立つと楽観的である。

関連論文リスト

• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise [7.421135890148154]
  対象関数にノイズが存在する場合の古典的ベンチマークの最初の解析を行う。 ビット単位の先行ノイズが$p le alpha/n$, $alpha$ a suitable constant であることを示す。 すべての解が各イテレーションで再評価されると、ノイズレート$p = omega(log(n)/n2)$がスーパーポリノミカルランタイムにつながることが証明される。
  論文  参考訳（メタデータ） (2023-05-17T14:48:06Z)
• The $(1+(\lambda,\lambda))$ Global SEMO Algorithm [8.34061303235504]
  我々は、$(lambda,lambda)$の遺伝的計算を多目的進化計算に転送できることを示した。 我々は,従来のグローバルSEMOアルゴリズムの変種である$(lambda,lambda)$ global SEMOアルゴリズムを定義し,OneMinMaxアルゴリズムがグローバルSEMOよりもベンチマークで高速であることを証明した。
  論文  参考訳（メタデータ） (2022-10-07T15:18:32Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [14.309243378538014]
  OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。 確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。 また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
  論文  参考訳（メタデータ） (2020-12-14T03:07:39Z)
• A new regret analysis for Adam-type algorithms [78.825194932103]
  理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。 最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-21T19:19:51Z)

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

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