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

• arxiv url: http://arxiv.org/abs/2112.08581v6
• Date: Mon, 18 Sep 2023 14:03:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-20 02:10:38.325005
• Title: Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
• Title（参考訳）: 非支配的ソーティング遺伝的アルゴリズム(NSGA-II)の数学的実行解析
• Authors: Weijie Zheng, Benjamin Doerr
• Abstract要約: NSGA-IIにも実行時解析が可能であることを示す。 NSGA-IIは,パレートフロントの4倍の大きさの個体群を持つため,SEMOアルゴリズムやGSEMOアルゴリズムと同じランタイム保証を満たす。
• 参考スコア（独自算出の注目度）: 16.904475483445452
• 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 four times larger than the size of the Pareto front, the NSGA-II with two classic mutation operators and four different ways to select the parents satisfies the same asymptotic runtime guarantees as the SEMO and GSEMO algorithms on the basic OneMinMax and LeadingOnesTrailingZeros benchmarks. 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フロントの大きさの4倍の大きさの個体群を持つnsga-iiは,従来の2つの変異演算子と4つの異なる方法で親を選択することで,基本oneminmaxおよびleadingonestrailingzerosベンチマークにおけるsemoおよびgsemoアルゴリズムと同じ漸近的実行保証を満足できることが証明された。 しかし、人口の大きさがパレート前線のサイズに等しい場合、nsga-iiは完全なパレート前線を効率的に計算することはできない。 我々の実験は上記の結果を確認した。

関連論文リスト

• Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem [9.044970217182117]
  NSGA-IIは最も顕著な多目的進化アルゴリズムである。 NSGA-IIは指数時間以下ではパレートフロントを計算できないことを示す。
  論文  参考訳（メタデータ） (2024-11-15T07:50:40Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• 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)

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

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