論文の概要: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
- arxiv url: http://arxiv.org/abs/2312.10290v2
- Date: Thu, 25 Jan 2024 09:47:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-26 17:26:17.876924
- 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に匹敵する性能を示す。
関連論文リスト
- 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) - Bidirectional Looking with A Novel Double Exponential Moving Average to
Adaptive and Non-adaptive Momentum Optimizers [109.52244418498974]
我々は,新しいtextscAdmeta(textbfADouble指数textbfMov averagtextbfE textbfAdaptiveおよび非適応運動量)フレームワークを提案する。
我々は、textscAdmetaR と textscAdmetaS の2つの実装を提供し、前者は RAdam を、後者は SGDM をベースとしています。
論文 参考訳(メタデータ) (2023-07-02T18:16:06Z) - Analysing the Robustness of NSGA-II under Noise [1.7205106391379026]
EMOアルゴリズムNSGA-IIの最初のランタイム解析が登場した。
NSGA-IIがGSEMOを上回った時期は明らかではない。
論文 参考訳(メタデータ) (2023-06-07T15:33:54Z) - 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) - Parameterization of Cross-Token Relations with Relative Positional
Encoding for Vision MLP [52.25478388220691]
視覚多層パーセプトロン(MLP)はコンピュータビジョンタスクにおいて有望な性能を示す。
トークンミキシングレイヤを使用して、トランスフォーマーが使用するマルチヘッド自己保持機構とは対照的に、クロストークンインタラクションをキャプチャする。
トークン混合のためのクロストークン関係を効率的に符号化する新しい位置空間ゲーティングユニット(PoSGU)を提案する。
論文 参考訳(メタデータ) (2022-07-15T04:18:06Z) - 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) - Provable Stochastic Optimization for Global Contrastive Learning: Small
Batch Does Not Harm Performance [53.49803579981569]
各正の対と全ての負の対をアンカーポイントで対比する、コントラスト学習のグローバルな目的を考える。
SimCLRのような既存のメソッドは、十分な結果を得るために大きなバッチサイズを必要とする。
本稿では,SogCLRという表現のグローバルコントラスト学習を解くためのメモリ効率の最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-24T22:16:53Z) - GEO: Enhancing Combinatorial Optimization with Classical and Quantum
Generative Models [62.997667081978825]
我々は、生成モデルとして知られる機械学習モデルを活用する新しいフレームワークを導入し、最適化問題を解決する。
我々は、テンソルネットワークマシンに依存するGEOの量子インスパイアされたバージョンに注力する。
関数呼び出し数に対する固定予算が与えられた場合、その目標が最小限の最小値を求める場合、その優れた性能を示す。
論文 参考訳(メタデータ) (2021-01-15T18:18:38Z) - Convergence of Meta-Learning with Task-Specific Adaptation over Partial
Parameters [152.03852111442114]
モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。
本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
論文 参考訳(メタデータ) (2020-06-16T19:57:48Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。