論文の概要: Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy

• arxiv url: http://arxiv.org/abs/2505.01647v1
• Date: Sat, 03 May 2025 01:34:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-06 18:49:35.214255
• Title: Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy
• Title（参考訳）: 単純な老化戦略によるSMS-EMOAのスケーラブルな高速化
• Authors: Mingfeng Li, Weijie Zheng, Benjamin Doerr,
• Abstract要約: 本研究では,ある年齢未満の個人を除去可能な年齢から除外する,老化に基づく異なる非エリート選択機構を提案する。 目的数に関係なく、$max1,Theta(k)k-1$ の係数でスピードアップを証明します。
• 参考スコア（独自算出の注目度）: 12.731778729620478
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Different from single-objective evolutionary algorithms, where non-elitism is an established concept, multi-objective evolutionary algorithms almost always select the next population in a greedy fashion. In the only notable exception, Bian, Zhou, Li, and Qian (IJCAI 2023) proposed a stochastic selection mechanism for the SMS-EMOA and proved that it can speed up computing the Pareto front of the bi-objective jump benchmark with problem size $n$ and gap parameter $k$ by a factor of $\max\{1,2^{k/4}/n\}$. While this constitutes the first proven speed-up from non-elitist selection, suggesting a very interesting research direction, it has to be noted that a true speed-up only occurs for $k \ge 4\log_2(n)$, where the runtime is super-polynomial, and that the advantage reduces for larger numbers of objectives as shown in a later work. In this work, we propose a different non-elitist selection mechanism based on aging, which exempts individuals younger than a certain age from a possible removal. This remedies the two shortcomings of stochastic selection: We prove a speed-up by a factor of $\max\{1,\Theta(k)^{k-1}\}$, regardless of the number of objectives. In particular, a positive speed-up can already be observed for constant $k$, the only setting for which polynomial runtimes can be witnessed. Overall, this result supports the use of non-elitist selection schemes, but suggests that aging-based mechanisms can be considerably more powerful than stochastic selection mechanisms.
• Abstract（参考訳）: 非楕円性が確立された概念である単一目的進化アルゴリズムとは異なり、多目的進化アルゴリズムは、ほとんどの場合、欲求的な方法で次の集団を選択する。 唯一の例外として、Bian, Zhou, Li, Qian (IJCAI 2023) はSMS-EMOAの確率的選択機構を提案し、問題サイズ$n$とギャップパラメータ$k$を$\max\{1,2^{k/4}/n\}$で計算できることを示した。 これは、非楕円選択による最初の証明されたスピードアップであり、非常に興味深い研究方向を示唆するが、真のスピードアップは、ランタイムが超ポリノミカルである$k \ge 4\log_2(n)$に対してのみ発生し、後の研究で示されているように、より多くの目的に対して利点が低下することに注意する必要がある。 本研究では,ある年齢未満の個人を除去可能な年齢から除外する,老化に基づく異なる非エリート選択機構を提案する。 これは確率選択の2つの欠点を是正する: 目的の個数に関係なく、$\max\{1,\Theta(k)^{k-1}\}$でスピードアップを証明する。 特に、多項式ランタイムを目撃できる唯一の設定である定数$k$については、すでに正のスピードアップが観測できる。 全体として、この結果は非エリート選択スキームの使用を支持するが、老化に基づくメカニズムは確率的選択機構よりもかなり強力である可能性が示唆されている。

関連論文リスト

• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Runtime Analysis of the SMS-EMOA for Many-Objective Optimization [14.309243378538014]
  本稿ではSMSEMOAのための厳密なランタイム解析を行う。 SMS-EMOA は GSEMO と NSGA-II に匹敵する性能を示す。
  論文  参考訳（メタデータ） (2023-12-16T02:23:09Z)
• 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)
• A Large-scale Multiple-objective Method for Black-box Attack against Object Detection [70.00150794625053]
  我々は、真正の確率を最小化し、偽正の確率を最大化し、より多くの偽正の物体が新しい真正の有界箱を作らないようにする。 我々は、GARSDCと呼ばれるランダム・サブセット選択とディバイド・アンド・コンカーによる標準的な遺伝的アルゴリズムを拡張し、効率を大幅に改善する。 最先端攻撃法と比較して、GARSDCはmAPでは平均12.0、広範囲な実験ではクエリでは約1000倍減少する。
  論文  参考訳（メタデータ） (2022-09-16T08:36:42Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• 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)

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

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