論文の概要: A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy

• arxiv url: http://arxiv.org/abs/2507.03666v1
• Date: Fri, 04 Jul 2025 15:38:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-08 15:46:34.825569
• Title: A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy
• Title（参考訳）: PAES-25の初回実行時解析:Paretoアーカイブ進化戦略の拡張版
• Authors: Andre Opris,
• Abstract要約: 本稿では,PAES-25の数学的実行時解析について述べる。 PAES-25は,m$-LOTZに1ビットの変異を伴って,厳密なランタイム境界を導出する。 標準的なビット突然変異を持つPAES-25は、予想される$O(n4)$イテレーションで、双方向のLOTZベンチマークを最適化する。
• 参考スコア（独自算出の注目度）: 1.223779595809275
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: This paper presents a first mathematical runtime analysis of PAES-25, an enhanced version of the original Pareto Archived Evolution Strategy (PAES) coming from the study of telecommunication problems over two decades ago to understand the dynamics of local search of MOEAs on many-objective fitness landscapes. We derive tight expected runtime bounds of PAES-25 with one-bit mutation on $m$-LOTZ until the entire Pareto front is found: $\Theta(n^3)$ iterations if $m=2$, $\Theta(n^3 \log^2(n))$ iterations if $m=4$ and $\Theta(n(2n/m)^{m/2} \log(n/m))$ iterations if $m>4$ where $n$ is the problem size and $m$ the number of objectives. To the best of our knowledge, these are the first known tight runtime bounds for an MOEA outperforming the best known upper bound of $O(n^{m+1})$ for (G)SEMO on $m$-LOTZ when $m$ is at least $4$. We also show that archivers, such as the Adaptive Grid Archiver (AGA), Hypervolume Archiver (HVA) or Multi-Level Grid Archiver (MGA), help to distribute the set of solutions across the Pareto front of $m$-LOTZ efficiently. We also show that PAES-25 with standard bit mutation optimizes the bi-objective LOTZ benchmark in expected $O(n^4)$ iterations, and we discuss its limitations on other benchmarks such as OMM or COCZ.
• Abstract（参考訳）: 本稿では,多目的フィットネスランドスケープにおけるMOEAの局所探索のダイナミクスを理解するために,20年以上前の通信問題の研究から生まれた,オリジナルのPareto Archived Evolution Strategy(PAES)の強化版であるPAES-25の数学的実行時解析について述べる。 $\Theta(n^3)$ iterations if $m=2$, $\Theta(n^3 \log^2(n))$ iterations if $m=4$ and $\Theta(n(2n/m)^{m/2} \log(n/m))$ iterations if $m>4$ where $n$ is the problem size and $m$ the objectives。 我々の知る限り、これらはMOEAの最もよく知られた上限である$O(n^{m+1})$ for (G)SEMO on $m$-LOTZ に対して、m$が少なくとも$4$である場合に、最初の厳密なランタイム境界である。 また、Adaptive Grid Archiver (AGA)、Hypervolume Archiver (HVA)、Multi-Level Grid Archiver (MGA)などのアーカイブが、Paretoの$m$-LOTZのフロントにソリューションの集合を分散させるのに有効であることを示す。 また,標準的なビット突然変異を持つPAES-25は,O(n^4)$繰り返しの2目的LOTZベンチマークを最適化し,OMMやCOCZなどの他のベンチマーク上での制限について議論する。

関連論文リスト

• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  これは従来の$tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$で改善されている。
  論文  参考訳（メタデータ） (2025-03-15T07:09:36Z)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) [22.123838452178585]
  本研究では, 強度進化アルゴリズム2 (SPEA2) の動作時間解析を行った。 具体的には、一般的に使用される3つの多目的問題、すなわち$m$OneMinMax、$m$LeadingOnesZeroes、$m$-OneZeroJumpを解決するためのSPEA2の実行時間が期待されていることを証明します。
  論文  参考訳（メタデータ） (2024-06-23T14:12:22Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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