論文の概要: Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up

• arxiv url: http://arxiv.org/abs/2610.35373v1
• Date: Mon, 26 Oct 2026 12:56:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:13.933551
• Title: Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up
• Title（参考訳）: MOEA/Dの共進化的ソリューション交換を理解する: 最短の通信ラディウスが最強のスピードアップを与える
• Abstract要約: 変異に基づくMOEA/Dは,異なる距離のサブプロブレム間で解が交換される場合,古典的なOneMaxベンチマークをどのように解決するかを検討する。 我々は,MOEA/Dが解の交換によって得られる利益を初めて示し,すでに非常に小さな通信ラジイ$r$が,このアルゴリズムの特徴から最大限に利益を得るのに十分であることを示す。
• 参考スコア（独自算出の注目度）: 19.441780035577352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Besides domination-based algorithms such as the NSGA-II, the decomposition-based MOEA/D is one of the most popular and successful optimization heuristic for multi-objective problems. It decomposes the problem into several, single-objective subproblems. By solving these in a co-evolutionary manner and archiving non-dominated solutions, it approximates or computes the Pareto front. Interestingly, so far no advantages from the co-evolutionary communication of subproblem solutions were proven. In this first mathematical runtime analysis addressing this research question, we investigate how the mutation-based MOEA/D solves the classic OneMinMax benchmark when solutions are exchanged among subproblems in different distances $r$. We show, for the first time, that the MOEA/D profits from an exchange of solutions, and that already very small communication radii $r$ are sufficient to maximally profit from this feature of the algorithm. More precisely, for all values $r \ge 1$ we prove a tight runtime guarantee of $Θ(n^2)$, where $n$ is the problem size. This is asymptotically faster than the known bound of $O(n^2 \log n)$ guarantee for $r=0$, which we complement with a matching bound of $Ω(n^2 \log n)$.
• Abstract（参考訳）: NSGA-IIのような支配に基づくアルゴリズムに加えて、分解に基づくMOEA/Dは多目的問題に対して最も人気があり、成功した最適化ヒューリスティックの1つである。 これは問題をいくつかの単目的のサブプロブレムに分解する。 これらを共進化的に解き、非支配的な解をアーカイブすることにより、パレートフロントを近似または計算する。 興味深いことに、今のところサブプロブレム解の共進化的コミュニケーションの利点は証明されていない。 この研究課題に対処する最初の数学的ランタイム解析では、変異に基づくMOEA/Dが、異なる距離のサブプロブレム間で解が交換されるときに、古典的なOneMinMaxベンチマークをどのように解決するかを検討する。 我々は,MOEA/Dが解の交換によって得られる利益を初めて示し,既に非常に小さな通信ラジイ$r$が,アルゴリズムのこの特徴から最大限に利益を得るのに十分であることを示す。 より正確には、すべての値 $r \ge 1$ に対して、$n$ が問題のサイズであるような、厳密なランタイム保証を証明します。 これは既知の$O(n^2 \log n)$保証の$r=0$よりも漸近的に速く、一致する$Ω(n^2 \log n)$を補完する。

関連論文リスト

• Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization [59.290497104061835]
  私たちは$n$ノードのネットワーク上に$()$-Goldsteinの固定子を見つけます。 $d$への依存は、高次元のレジームにおいて大きなボトルネックとなる。 対数$d$への依存は、追加の通信だけで取り除くことができることを示す。
  論文  参考訳（メタデータ） (2026-10-05T04:37:04Z)
• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。 まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。 決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
  論文  参考訳（メタデータ） (2026-07-21T00:40:59Z)
• First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables [23.47753638129204]
  二項決定空間上で定義された問題は、多目的進化アルゴリズムの理論において集中的に研究されている。 有限値 $r > 2$ の値を取る決定変数を扱うMOEAには、今のところ数学的ランタイム解析は存在しない。 多値決定変数を扱う場合、古典的MOEAは重大な問題に遭遇しないことが示される。
  論文  参考訳（メタデータ） (2026-05-14T13:42:52Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions [9.044970217182117]
  分解に基づく多目的進化アルゴリズム(MOEA/D)は、与えられた多目的関数$f$を直接最適化するのではなく、共進化的に$f$の単目的サブプロブレム$N + 1$を最適化する。 我々は、標準突然変異演算子のみを持つMOEA/Dが、OneMinMaxベンチマークのPareto全体を計算する方法について、初めて分析する。 パワーローに対する我々の全体的な境界は、MOEA/D が$N = O(nbeta - 1)$ に対して最も良く、結果として$O(n) となることを示唆している。
  論文  参考訳（メタデータ） (2024-05-02T05:32:19Z)
• 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)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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