論文の概要: A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)

• arxiv url: http://arxiv.org/abs/2211.08202v1
• Date: Tue, 15 Nov 2022 15:10:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-16 13:16:28.682475
• Title: A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
• Title（参考訳）: 非支配ソーティング遺伝的アルゴリズム(NSGA-III)の数学的実行解析
• Authors: Benjamin Doerr, Simon Wietheger
• Abstract要約: NSGA-IIは現実世界の応用において最も顕著な多目的進化アルゴリズムである。 我々は,textscOneMinMaxベンチマークの3目的変種に基づいて,NSGA-IIIの数学的ランタイム解析を行った。
• 参考スコア（独自算出の注目度）: 9.853329403413701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The NSGA-II (Non-dominated Sorting Genetic Algorithm) is the most prominent multi-objective evolutionary algorithm for real-world applications. While it performs evidently well on bi-objective benchmarks, empirical studies suggest that its performance worsens when applied to functions with more than two objectives. As a remedy, the NSGA-III with a slightly adapted selection for the next generation was proposed. In this work, we provide the first mathematical runtime analysis of the NSGA-III, on a 3-objective variant of the \textsc{OneMinMax} benchmark. We prove that employing sufficiently many (at least $\frac{2n^2}{3}+\frac{5n}{\sqrt{3}}+3$) reference points ensures that once a solution for a certain trade-off between the objectives is found, the population contains such a solution in all future iterations. Building on this observation, we show that the expected number of iterations until the population covers the Pareto front is in $O(n^3)$. This result holds for all population sizes that are at least the size of the Pareto front.
• Abstract（参考訳）: NSGA-II (Non-dominated Sorting Genetic Algorithm) は、実世界の応用において最も顕著な多目的進化アルゴリズムである。 2つの目的を持つ関数に適用すると、その性能が悪化することが実証研究で示唆されている。 救済策として、NSGA-IIIは次の世代に若干適応した選択が提案された。 本研究では, NSGA-III の初となる数学的ランタイム解析を \textsc{OneMinMax} ベンチマークの 3 目的変種上で提供する。 十分多くの(少なくとも$\frac{2n^2}{3}+\frac{5n}{\sqrt{3}}+3$)基準点を用いることで、目標間のあるトレードオフに対する解が見つかると、その集団は将来の全ての反復においてそのような解を含むことが証明される。 この観測に基づいて、人口がパレートフロントをカバーするまでのイテレーションの期待数は、$O(n^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)

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

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