論文の概要: Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem

• arxiv url: http://arxiv.org/abs/2411.10017v1
• Date: Fri, 15 Nov 2024 07:50:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-18 15:39:04.177373
• Title: Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem
• Title（参考訳）: 多目的リードワンズ問題におけるNSGA-IIの問題点
• Authors: Benjamin Doerr, Dimitri Korkotashvili, Martin S. Krejca,
• Abstract要約: NSGA-IIは最も顕著な多目的進化アルゴリズムである。 NSGA-IIは指数時間以下ではパレートフロントを計算できないことを示す。
• 参考スコア（独自算出の注目度）: 9.044970217182117
• License:
• Abstract: The NSGA-II is the most prominent multi-objective evolutionary algorithm (cited more than 50,000 times). Very recently, a mathematical runtime analysis has proven that this algorithm can have enormous difficulties when the number of objectives is larger than two (Zheng, Doerr. IEEE Transactions on Evolutionary Computation (2024)). However, this result was shown only for the OneMinMax benchmark problem, which has the particularity that all solutions are on the Pareto front, a fact heavily exploited in the proof of this result. In this work, we show a comparable result for the LeadingOnesTrailingZeroes benchmark. This popular benchmark problem appears more natural in that most of its solutions are not on the Pareto front. With a careful analysis of the population dynamics of the NGSA-II optimizing this benchmark, we manage to show that when the population grows on the Pareto front, then it does so much faster by creating known Pareto optima than by spreading out on the Pareto front. Consequently, already when still a constant fraction of the Pareto front is unexplored, the crowding distance becomes the crucial selection mechanism, and thus the same problems arise as in the optimization of OneMinMax. With these and some further arguments, we show that the NSGA-II, with a population size by at most a constant factor larger than the Pareto front, cannot compute the Pareto front in less than exponential time.
• Abstract（参考訳）: NSGA-IIは、最も顕著な多目的進化アルゴリズムである。 ごく最近、数学的な実行時解析により、目的の数が2より大きい場合(Zheng, Doerr)、このアルゴリズムは非常に困難であることが証明された。 IEEE Transactions on Evolutionary Computation (2024) しかしながら、この結果は、すべてのソリューションがParetoのフロントにあるという特筆すべきOneMinMaxベンチマーク問題に対してのみ示された。 本稿では、LeadingOnesTrailingZeroesベンチマークに匹敵する結果を示す。 この人気のあるベンチマーク問題は、ほとんどのソリューションがParetoにはないという点で、より自然に見えます。 このベンチマークを最適化したNGSA-IIの人口動態を慎重に分析することにより、パレートフロントで人口が増加すると、パレートフロントで広がるよりも、パレートオプティマを作成する方がはるかに速くなることを示した。 したがって、パレートフロントの定数がまだ探索されていない場合、群れ距離は決定的な選択機構となり、従ってOneMinMaxの最適化と同じ問題が発生する。 これらといくつかの議論により、NSGA-IIはパレートフロントよりも少なくとも一定の大きさの集団であり、指数時間以下ではパレートフロントを計算できないことを示す。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms [10.165640083594573]
  従来のベンチマークでは,SEMO,グローバルSEMO,SMS-EMOAアルゴリズムのほぼ28のランタイム保証が証明されている。 このような厳密な境界がこれらのMOEAの多目的利用に対して証明されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2024-04-19T09:46:59Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。 提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。 本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
  論文  参考訳（メタデータ） (2023-04-28T07:09:23Z)
• 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)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• 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)
• 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)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• 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)

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

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