論文の概要: A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic
Algorithm III (NSGA-III)
- arxiv url: http://arxiv.org/abs/2211.08202v4
- Date: Mon, 12 Jun 2023 08:11:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-14 02:09:31.882053
- Title: A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic
Algorithm III (NSGA-III)
- Title（参考訳）: 非支配ソーティング遺伝的アルゴリズム(NSGA-III)の数学的実行解析
- Authors: Simon Wietheger, Benjamin Doerr
- Abstract要約: NSGA-II (Non-Maninated Sorting Genetic Algorithm II) は、実世界の応用において最も顕著な多目的進化アルゴリズムである。
NSGA-IIIは2つ以上の目的をうまく扱うことを目的としたNSGA-IIの改良である。
- 参考スコア（独自算出の注目度）: 9.853329403413701
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most
prominent multi-objective evolutionary algorithm for real-world applications.
While it performs evidently well on bi-objective optimization problems,
empirical studies suggest that it is less effective when applied to problems
with more than two objectives. A recent mathematical runtime analysis confirmed
this observation by proving the NGSA-II for an exponential number of iterations
misses a constant factor of the Pareto front of the simple 3-objective
OneMinMax problem.
In this work, we provide the first mathematical runtime analysis of the
NSGA-III, a refinement of the NSGA-II aimed at better handling more than two
objectives. We prove that the NSGA-III with sufficiently many reference points
-- a small constant factor more than the size of the Pareto front, as suggested
for this algorithm -- computes the complete Pareto front of the 3-objective
OneMinMax benchmark in an expected number of O(n log n) iterations. This result
holds for all population sizes (that are at least the size of the Pareto
front). It shows a drastic advantage of the NSGA-III over the NSGA-II on this
benchmark. The mathematical arguments used here and in previous work on the
NSGA-II suggest that similar findings are likely for other benchmarks with
three or more objectives.
- Abstract（参考訳）: NSGA-II (Non-Maninated Sorting Genetic Algorithm II) は、実世界の応用において最も顕著な多目的進化アルゴリズムである。
双目的最適化問題では明らかにうまく機能するが、2つ以上の目的を持つ問題に適用すると効果が低いことが実証研究で示唆されている。
最近の数学的ランタイム解析により、NGSA-IIを指数的な反復数で証明することで、単純な3つの客観的なOneMinMax問題のパレートフロントの定数因子を見逃すことが確認された。
本研究では,NSGA-IIIの数学的ランタイム解析として,NSGA-IIを改良し,2つ以上の目的をうまく扱えるようにした。
このアルゴリズムが提案するように、十分に多くの基準点を持つNSGA-IIIは、3オブジェクトのOneMinMaxベンチマークの完全なParetoフロントを、期待される数のO(n log n)反復で計算する。
この結果は、すべての人口規模(少なくともパレートフロントの大きさ)に当てはまる。
このベンチマークではNSGA-IIIのNSGA-IIに対する大きな優位性を示している。
ここで用いられる数学的議論と、NSGA-IIに関する以前の研究は、他の3つ以上の目的を持つベンチマークに対して同様の発見が考えられることを示唆している。
関連論文リスト
- Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms [10.165640083594573]
従来のベンチマークでは,SEMO,グローバルSEMO,SMS-EMOAアルゴリズムのほぼ28のランタイム保証が証明されている。
このような厳密な境界がこれらのMOEAの多目的利用に対して証明されたのはこれが初めてである。
論文 参考訳（メタデータ） (2024-04-19T09:46:59Z) - Runtime Analyses of NSGA-III on Many-Objective Problems [10.955844285189372]
本稿では,一般的な多目的ベンチマーク問題mLOTZ,mOMM,mCOCZにおけるNSGA-IIIのランタイム解析について述べる。
これらのパラメータは,問題次元,目的数,適合範囲によってどのようにスケールするかを示す。
我々の知る限り、これらは3つ以上の目的に対してNSGA-IIIの最初のランタイム解析である。
論文 参考訳（メタデータ） (2024-04-17T14:39:14Z) - 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 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) - 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) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
ポイントクラウド上で学習するためのグラフ畳み込みネットワーク(GCN)の計算効率の向上を目指します。
一連の実験により、最適化されたネットワークは計算複雑性を減らし、メモリ消費を減らし、推論速度を加速した。
論文 参考訳（メタデータ） (2021-04-12T17:59:16Z) - Self-supervised Geometric Perception [96.89966337518854]
自己教師付き幾何知覚(self-supervised geometric perception)は、基底幾何モデルラベルなしで対応マッチングのための特徴記述子を学ぶためのフレームワークである。
また,SGPは,地上トラスラベルを用いて訓練した教師付きオークルよりも同等か優れる最先端性能を達成できることを示す。
論文 参考訳（メタデータ） (2021-03-04T15:34:43Z) - PC-RGNN: Point Cloud Completion and Graph Neural Network for 3D Object
Detection [57.49788100647103]
LiDARベースの3Dオブジェクト検出は、自動運転にとって重要なタスクです。
現在のアプローチでは、遠方および閉ざされた物体の偏りと部分的な点雲に苦しむ。
本稿では,この課題を2つの解決法で解決する新しい二段階アプローチ,pc-rgnnを提案する。
論文 参考訳（メタデータ） (2020-12-18T18:06:43Z) - Convergence of Meta-Learning with Task-Specific Adaptation over Partial
Parameters [152.03852111442114]
モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。
本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
論文 参考訳（メタデータ） (2020-06-16T19:57:48Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。