論文の概要: Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II

• arxiv url: http://arxiv.org/abs/2505.01323v2
• Date: Sun, 08 Jun 2025 13:36:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 16:33:10.047498
• Title: Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II
• Title（参考訳）: 多目的最適化における証明近似保証:SPEA2がNSGA-IIに勝る
• Authors: Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, Mohammed Lagmah,
• Abstract要約: 強度進化アルゴリズム2(SPEA2)は、支配に基づく多目的進化アルゴリズム(MOEA)の1つである。 簡単な定常SPEA2がパレートフロントの最適近似を時間内に計算できることを実証する。
• 参考スコア（独自算出の注目度）: 8.279693387917217
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of $\sigma$-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.
• Abstract（参考訳）: NSGA-IIとSMS-EMOAと共に、パレート進化アルゴリズム2(SPEA2)は、最も顕著な支配に基づく多目的進化アルゴリズム(MOEA)の1つである。 NSGA-II とは違って、双対非支配解の比較には群を成す距離(実際には隣り合う解までの距離)は使用せず、他のすべての解との距離の上に構築された$\sigma$-distances の複雑なシステムである。 本研究では、このより複雑な距離体系が優れていることを示す最初の数学的証明を与える。 より具体的には、単純な定常SPEA2は、OneMinMaxベンチマークのParetoフロントの最適近似を多項式時間で計算できることを証明している。 NSGA-IIの同等の変種に対する最も証明された保証は、近似比が約2倍であることを保証することのみであり、数学的解析と実験の両方で、最適近似が効率的に見つからないことが示されている。

関連論文リスト

• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization [56.805574957824135]
  2方向部分AUCAUCは、不均衡なデータを持つバイナリ分類における重要な性能指標である。 TPAUC最適化のための既存のアルゴリズムは未探索のままである。 TPAUC最適化のための2つの革新的な二重座標ブロック座標アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-05-28T03:55:05Z)
• Optimal Distribution of Solutions for Crowding Distance on Linear Pareto Fronts of Two-Objective Optimization Problems [5.072077366588175]
  NSGA-IIは最適化すべき明確な基準に基づいていない。 最も簡単な条件下で,群集距離の最適分布について検討する。
  論文  参考訳（メタデータ） (2025-04-24T03:22:49Z)
• MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes [57.24311218570012]
  EF21-P (匿名2024) と MARINA-P (arXiv:2402.06412) の非滑らか凸理論を非サイズ凸設定で拡張する。 我々は、定数、減少、適応(aktype)ステップの理論的保証を提供する。
  論文  参考訳（メタデータ） (2024-12-22T16:18:34Z)
• Towards Running Time Analysis of Interactive Multi-objective Evolutionary Algorithms [23.815981112784552]
  本稿では,実際のiMOEAに対して,最初の実行時間解析(EAの本質的理論的側面)を提供する。 我々は、OneMinMaxとOneJumpZeroJumpの問題を解くために、よく開発された対話型NSGA-IIのランニングタイムが、それぞれ$O(n log n)$と$O(nk)$であることを示す。
  論文  参考訳（メタデータ） (2023-10-12T14:57:47Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives [16.904475483445452]
  NSGA-IIは多目的最適化問題を解く最も顕著なアルゴリズムの1つである。 NSGA-IIは多数の目的に対して効果が低いことを示す。
  論文  参考訳（メタデータ） (2022-11-23T16:15:26Z)
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III) [9.853329403413701]
  NSGA-II (Non-Maninated Sorting Genetic Algorithm II) は、実世界の応用において最も顕著な多目的進化アルゴリズムである。 NSGA-IIIは2つ以上の目的をうまく扱うことを目的としたNSGA-IIの改良である。
  論文  参考訳（メタデータ） (2022-11-15T15:10:36Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) [16.904475483445452]
  NSGA-IIにも実行時解析が可能であることを示す。 NSGA-IIは,パレートフロントの4倍の大きさの個体群を持つため,SEMOアルゴリズムやGSEMOアルゴリズムと同じランタイム保証を満たす。
  論文  参考訳（メタデータ） (2021-12-16T03:00:20Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• The Cone epsilon-Dominance: An Approach for Evolutionary Multiobjective Optimization [1.0323063834827413]
  進化アルゴリズムの収束と多様性を改善するためのコーン・エプシロン・マディナンス・アプローチ。 16のよく知られたベンチマーク問題が実験セクションで検討されている。 その結果,コーン-エプス-MOEAは,検討したすべてのパフォーマンス指標に対して,効率的かつバランスの取れた性能を示すことができることが示唆された。
  論文  参考訳（メタデータ） (2020-07-14T14:13:13Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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