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

• arxiv url: http://arxiv.org/abs/2112.08581v1
• Date: Thu, 16 Dec 2021 03:00:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-17 16:33:54.673746
• Title: A First Mathematical Runtime Analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
• Title（参考訳）: 非支配的ソーティング遺伝的アルゴリズム(NSGA-II)の最初の数学的実行解析
• Authors: Weijie Zheng, Yufei Liu, Benjamin Doerr
• Abstract要約: NSGA-IIは、実世界の応用において最も集中的に使用される多目的ソート遺伝的アルゴリズムである。 NSGA-IIにも数学的解析が可能であることを示す。
• 参考スコア（独自算出の注目度）: 5.28539620288341
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such study exists for the NSGA-II so far. In this work, we show that mathematical runtime analyses are feasible also for the NSGA-II. As particular results, we prove that with a population size larger than the Pareto front size by a constant factor, the NSGA-II with two classic mutation operators and three different ways to select the parents satisfies the same asymptotic runtime guarantees as the SEMO and GSEMO algorithms on the basic OneMinMax and LOTZ benchmark functions. However, if the population size is only equal to the size of the Pareto front, then the NSGA-II cannot efficiently compute the full Pareto front (for an exponential number of iterations, the population will always miss a constant fraction of the Pareto front). Our experiments confirm the above findings.
• Abstract（参考訳）: 非支配的ソート遺伝アルゴリズムII(NSGA-II)は、現実世界の応用において最も集中的に使用される多目的進化アルゴリズムである。 しかし、数学的な方法で解析されたいくつかの単純なMOEAとは対照的に、NSGA-IIにはそのような研究は存在しない。 本研究では,NSGA-IIにも数学的ランタイム解析が適用可能であることを示す。 特に,paretoフロントサイズより大きい個体群を定数係数で表すと,nsga-iiは2つの古典的変異演算子を持ち,親の選択方法が3つ異なることが,基本的なoneminmaxベンチマーク関数とlotzベンチマーク関数上のsemoとgsemoアルゴリズムと同じ漸近的実行保証を満たすことを証明した。 しかし、人口規模がパレートフロントのサイズに等しい場合、NSGA-IIはパレートフロント全体を効率的に計算することができない(指数的な回数の反復の場合、人口は常にパレートフロントの一定の割合を逃すことになる)。 我々の実験は上記の結果を確認した。

関連論文リスト

• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem [9.044970217182117]
  NSGA-IIは最も顕著な多目的進化アルゴリズムである。 NSGA-IIは指数時間以下ではパレートフロントを計算できないことを示す。
  論文  参考訳（メタデータ） (2024-11-15T07:50:40Z)
• Analysing the Robustness of NSGA-II under Noise [1.7205106391379026]
  EMOアルゴリズムNSGA-IIの最初のランタイム解析が登場した。 NSGA-IIがGSEMOを上回った時期は明らかではない。
  論文  参考訳（メタデータ） (2023-06-07T15:33:54Z)
• 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)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• 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)
• Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) [16.904475483445452]
  NSGA-IIは人口規模が小さい場合にパレートフロントをいかによく近似するかを考察する。 これはNSGA-IIの近似能力に関する最初の数学的研究であり、定常NSGA-IIに対する最初の実行時解析である。
  論文  参考訳（メタデータ） (2022-03-05T09:53:30Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• What Are Bayesian Neural Network Posteriors Really Like? [63.950151520585024]
  ハミルトニアンモンテカルロは、標準およびディープアンサンブルよりも大きな性能向上を達成できることを示す。 また,深部分布は標準SGLDとHMCに類似しており,標準変動推論に近いことが示された。
  論文  参考訳（メタデータ） (2021-04-29T15:38:46Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。 我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
  論文  参考訳（メタデータ） (2020-10-28T17:59:59Z)

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

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