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

• arxiv url: http://arxiv.org/abs/2505.01323v1
• Date: Fri, 02 May 2025 14:55:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-05 17:21:20.071314
• 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://creativecommons.org/licenses/by/4.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倍であることを保証することのみであり、数学的解析と実験の両方で、最適近似が効率的に見つからないことが示されている。

関連論文リスト

• 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)
• 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)
• 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)

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

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