論文の概要: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
- arxiv url: http://arxiv.org/abs/2312.10290v1
- Date: Sat, 16 Dec 2023 02:23:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-19 17:26:43.229236
- Title: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
- Title（参考訳）: 多目的最適化のためのSMS-EMOAの実行時解析
- Authors: Weijie Zheng, Benjamin Doerr
- Abstract要約: 本稿では,多目的最適化のためのSMS-EMOAの厳密な実行時解析を行う。
まず,二目的OJZJベンチマークの m-目的 mOJZJ 問題である多目的 mOJZJ 問題を提案する。
SMS-EMOAは、このベンチマークの全前面を、期待される数$O(M2 nk)$で計算する。
- 参考スコア（独自算出の注目度）: 16.904475483445452
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The widely used multiobjective optimizer NSGA-II was recently proven to have
considerable difficulties in many-objective optimization. In contrast,
experimental results in the literature show a good performance of the SMS-EMOA,
which can be seen as a steady-state NSGA-II that uses the hypervolume
contribution instead of the crowding distance as the second selection
criterion.
This paper conducts the first rigorous runtime analysis of the SMS-EMOA for
many-objective optimization. To this aim, we first propose a many-objective
counterpart, the m-objective mOJZJ problem, of the bi-objective OJZJ benchmark,
which is the first many-objective multimodal benchmark used in a mathematical
runtime analysis. We prove that SMS-EMOA computes the full Pareto front of this
benchmark in an expected number of $O(M^2 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), and $M=(2n/m-2k+3)^{m/2}$ the size of the
Pareto front. This result together with the existing negative result on 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, the stochastic population update
often does not help for mOJZJ. It results in a
$1/\Theta(\min\{Mk^{1/2}/2^{k/2},1\})$ speed-up, which is $\Theta(1)$ for large
$m$ such as $m>k$. On the positive side, we prove that heavy-tailed mutation
still results in a speed-up of order $k^{0.5+k-\beta}$. Finally, we conduct the
first runtime analyses of the SMS-EMOA on the bi-objective OneMinMax and LOTZ
benchmarks and show that it has a performance comparable to the GSEMO and the
NSGA-II.
- Abstract（参考訳）: 広く使われている多目的最適化器NSGA-IIは、最近多目的最適化においてかなり困難であることが証明された。
これとは対照的に,実験結果からSMS-EMOAの性能は良好であり,第2選択基準として群集距離の代わりに超体積寄与を用いた定常NSGA-IIと見なすことができる。
本稿では,多目的最適化のためのSMS-EMOAの厳密な実行時解析を行う。
そこで本研究では,まず,2目的OJZJベンチマークの m-目的 mOJZJ 問題である多目的 mOJZJ 問題を数学的ランタイム解析に用いた最初の多目的マルチモーダルベンチマークを提案する。
SMS-EMOAは、このベンチマークの全Paretoフロントを$O(M^2 n^k)$イテレーションで計算し、$n$は問題サイズ(ビットストリング表現の長さ)、$kはギャップサイズ(問題の難易度パラメータ)、$M=(2n/m-2k+3)^{m/2}はParetoフロントのサイズである。
この結果と既存のNSGA-IIの負の結果は、原則としてNSGA-IIの一般的なアプローチは多目的最適化に適しているが、タイブレーカとしての群集距離には欠点があることを示している。
SMS-EMOAについてさらに3つの知見を得た。
bi-objective ojzjベンチマークの最近の結果とは異なり、確率的人口更新はmojzjにはあまり役に立たない。
1/\Theta(\min\{Mk^{1/2}/2^{k/2},1\})$スピードアップとなり、$m>k$のような大きな$m$に対して$\Theta(1)$となる。
正の面では、重く尾のついた突然変異がそれでも$k^{0.5+k-\beta}$のスピードアップをもたらすことを証明します。
最後に、二目的の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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。