論文の概要: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
- arxiv url: http://arxiv.org/abs/2312.10290v3
- Date: Wed, 12 Jun 2024 12:55:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-13 23:13:33.924004
- Title: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
- Title（参考訳）: 多目的最適化のためのSMS-EMOAの実行時解析
- Authors: Weijie Zheng, Benjamin Doerr,
- Abstract要約: 本稿ではSMSEMOAのための厳密なランタイム解析を行う。
SMS-EMOA は GSEMO と NSGA-II に匹敵する性能を示す。
- 参考スコア（独自算出の注目度）: 14.309243378538014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The classic NSGA-II was recently proven to have considerable difficulties in many-objective optimization. This paper conducts the first rigorous runtime analysis in many objectives for the SMS-EMOA, a steady-state NSGA-II that uses the hypervolume contribution instead of the crowding distance as the second selection criterion. To this aim, we first propose a many-objective counterpart, the m-objective mOJZJ, of the bi-objective OJZJ, which is the first many-objective multimodal benchmark for runtime analysis. We prove that SMS-EMOA computes the full Pareto front of this benchmark in an expected number of $O(\mu M n^k)$ iterations, where $n$ denotes the problem size (length of the bit-string representation), $k$ the gap size (a difficulty parameter of the problem), $M=(2n/m-2k+3)^{m/2}$ the size of the Pareto front, and $\mu$ the population size (at least the same size as the largest incomparable set). This result together with the existing negative result for the original NSGA-II shows that, in principle, the general approach of the NSGA-II is suitable for many-objective optimization, but the crowding distance as tie-breaker has deficiencies. We obtain three additional insights on the SMS-EMOA. Different from a recent result for the bi-objective OJZJ benchmark, a recently proposed stochastic population update often does not help for mOJZJ. It at most results in a speed-up by a factor of order $2^{k} / \mu$, which is $\Theta(1)$ for large $m$, such as $m>k$. On the positive side, we prove that heavy-tailed mutation irrespective of the number $m$ of objectives results in a speed-up of order $k^{0.5+k-\beta}/e^k$, the same advantage as previously shown for the bi-objective case. Finally, we conduct the first runtime analyses of the SMS-EMOA on the classic bi-objective OneMinMax and LOTZ benchmarks and show that the SMS-EMOA has a performance comparable to the GSEMO and the NSGA-II.
- Abstract（参考訳）: 古典的なNSGA-IIは、多目的最適化においてかなり困難であることが最近証明された。
本稿では,群集距離を第2選択基準としてではなく,超体積寄与を用いた定常NSGA-IIであるSMS-EMOAについて,多くの目的において,厳密なランタイム解析を行う。
そこで本研究では,まず,多目的型OJZJのmOJZJという,多目的型OJZJをランタイム解析のための最初の多目的型マルチモーダルベンチマークとして提案する。
SMS-EMOAは、このベンチマークの全Paretoフロントを$O(\mu M n^k)$ iterationsで計算し、$n$は問題サイズ(ビットストリング表現の長さ)、$k$はギャップサイズ(問題の難易度パラメータ)、$M=(2n/m-2k+3)^{m/2}はパレートフロントのサイズ、$\mu$は人口サイズ(少なくとも最大の非可算集合と同じサイズ)を表す。
この結果と元のNSGA-IIに対する既存の負の結果は、原則としてNSGA-IIの一般的なアプローチは多目的最適化に適しているが、タイブレーカとしての群集距離には欠点があることを示している。
SMS-EMOAについてさらに3つの知見を得た。
二目的OJZJベンチマークの最近の結果とは異なり、最近提案された確率的集団更新は、しばしばmOJZJにとって役に立たない。
つまり、$m>k$ のような $m$ に対して $\Theta(1)$ となる。
正の面では、目的数$m$によらず重み付き突然変異が、前述した双目的の場合と同じ優位性である$k^{0.5+k-\beta}/e^k$の順序の高速化をもたらすことを証明している。
最後に,従来の2目的のOneMinMaxとLOTZベンチマークを用いて,SMS-EMOAのランタイム解析を行い,GSEMOとNSGA-IIに匹敵する性能を示す。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - DI-MaskDINO: A Joint Object Detection and Instance Segmentation Model [67.56918651825056]
MaskDinoの開始変圧器デコーダ層から中間結果を調べる際に, 物体検出遅延がインスタンスセグメンテーションの遅れ(すなわち, 性能不均衡)の原因となる。
本稿では,DI-MaskDINOモデルを提案する。その中核となる考え方は,検出・セグメンテーションの不均衡を緩和し,最終的な性能を改善することである。
DI-MaskDINOはCOCOとBDD100Kベンチマークで既存のジョイントオブジェクト検出とインスタンスセグメンテーションモデルを上回っている。
論文 参考訳（メタデータ） (2024-10-22T05:22:49Z) - A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization [13.277972583315051]
最近の理論的研究により、NSGA-IIは2つ以上の目的を持つ問題を解くのに非常に困難であることが示されている。
我々は、これらの過去の研究の洞察を用いて、真に群集距離と呼ばれる群集距離の変種を定義する。
本アルゴリズムは,OneMinMax,COCZ,LOTZ,OJZJ$_k$問題の多目的バージョンを解くことができることを示す。
論文 参考訳（メタデータ） (2024-07-25T01:09:58Z) - Beyond SOT: Tracking Multiple Generic Objects at Once [141.36900362724975]
ジェネリックオブジェクト追跡(ジェネリックオブジェクト追跡、英: Generic Object Tracking、GOT)は、ビデオの最初のフレームでボックスをバウンディングすることによって指定されたターゲットオブジェクトを追跡する問題である。
大規模GOTベンチマークであるLaGOTを導入し,複数のアノテート対象オブジェクトをシーケンス毎に含む。
提案手法は単一オブジェクトのGOTデータセットに対して高い競合性を実現し,TrackingNet上での新たな技術状態が84.4%の成功率で設定されている。
論文 参考訳（メタデータ） (2022-12-22T17:59:19Z) - 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) - From Understanding the Population Dynamics of the NSGA-II to the First
Proven Lower Bounds [10.107150356618588]
我々は, NSGA-IIが適切な個体数を持つためには$Omega(Nnlog n)$関数評価が必要であることを証明した。
2つの目的の群集距離の寄与を計算するために、先頭定数を含む厳密な実行時推定値を得る。
論文 参考訳（メタデータ） (2022-09-28T10:11:20Z) - A First Runtime Analysis of the NSGA-II on a Multimodal Problem [17.049516028133958]
この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。
この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。
論文 参考訳（メタデータ） (2022-04-28T19:44:47Z) - Score-based Generative Modeling in Latent Space [93.8985523558869]
スコアベース生成モデル(SGM)は,最近,サンプル品質と分布範囲の両面で顕著な結果を示した。
本稿では,Latent Score-based Generative Model (LSGM)を提案する。
データから潜在空間への移動により、より表現力のある生成モデルをトレーニングし、非連続データにSGMを適用し、よりスムーズなSGMをより小さな空間で学習することができる。
論文 参考訳（メタデータ） (2021-06-10T17:26:35Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。