論文の概要: Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm
II (NSGA-II)
- arxiv url: http://arxiv.org/abs/2203.02693v3
- Date: Sun, 1 Oct 2023 13:30:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-03 21:39:57.735535
- Title: Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm
II (NSGA-II)
- Title（参考訳）: 非支配ソーティング遺伝的アルゴリズム(NSGA-II)の近似保証
- Authors: Weijie Zheng, Benjamin Doerr
- Abstract要約: NSGA-IIは人口規模が小さい場合にパレートフロントをいかによく近似するかを考察する。
これはNSGA-IIの近似能力に関する最初の数学的研究であり、定常NSGA-IIに対する最初の実行時解析である。
- 参考スコア（独自算出の注目度）: 16.904475483445452
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent theoretical works have shown that the NSGA-II efficiently computes the
full Pareto front when the population size is large enough. In this work, we
study how well it approximates the Pareto front when the population size is
smaller.
For the OneMinMax benchmark, we point out situations in which the parents and
offspring cover well the Pareto front, but the next population has large gaps
on the Pareto front. Our mathematical proofs suggest as reason for this
undesirable behavior that the NSGA-II in the selection stage computes the
crowding distance once and then removes individuals with smallest crowding
distance without considering that a removal increases the crowding distance of
some individuals.
We then analyze two variants not prone to this problem. For the NSGA-II that
updates the crowding distance after each removal (Kukkonen and Deb (2006)) and
the steady-state NSGA-II (Nebro and Durillo (2009)), we prove that the gaps in
the Pareto front are never more than a small constant factor larger than the
theoretical minimum. This is the first mathematical work on the approximation
ability of the NSGA-II and the first runtime analysis for the steady-state
NSGA-II. Experiments also show the superior approximation ability of the two
NSGA-II variants.
- Abstract（参考訳）: 最近の理論的研究により、NSGA-IIは人口規模が十分に大きい場合、パレート前面全体を効率的に計算することが示された。
本研究は,人口が小さくなると,パレート前線をいかによく近似するかを考察する。
OneMinMaxベンチマークでは、親と子孫がパレートフロントをよくカバーする状況が指摘されているが、次の人口はパレートフロントに大きなギャップがある。
我々の数学的証明は,選択段階におけるnsga-iiが群集距離を1回計算し,除去が一部の個体の群集距離を増加させることを考慮せずに最小群集距離を持つ個体を除去するという,この望ましくない行動の理由を示唆している。
次に,この問題に支障を来さない2つの変種を分析した。
各除去後の群集距離を更新するNSGA-II (Kukkonen and Deb (2006)) と定常状態NSGA-II (Nebro and Durillo (2009)) について、パレートフロントのギャップが理論的最小値よりも小さい定数要素以上であることを証明する。
これはNSGA-IIの近似能力に関する最初の数学的研究であり、定常NSGA-IIに対する最初の実行時解析である。
実験では2種類のNSGA-IIの近似能力も優れていた。
関連論文リスト
- Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem [9.044970217182117]
NSGA-IIは最も顕著な多目的進化アルゴリズムである。
NSGA-IIは指数時間以下ではパレートフロントを計算できないことを示す。
論文 参考訳（メタデータ） (2024-11-15T07:50:40Z) - A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization [13.277972583315051]
最近の理論的研究により、NSGA-IIは2つ以上の目的を持つ問題を解くのに非常に困難であることが示されている。
我々は、これらの過去の研究の洞察を用いて、真に群集距離と呼ばれる群集距離の変種を定義する。
本アルゴリズムは,OneMinMax,COCZ,LOTZ,OJZJ$_k$問題の多目的バージョンを解くことができることを示す。
論文 参考訳（メタデータ） (2024-07-25T01:09:58Z) - Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Closing the Gap Between the Upper Bound and the Lower Bound of Adam's
Iteration Complexity [51.96093077151991]
我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。
本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
論文 参考訳（メタデータ） (2023-10-27T09:16:58Z) - 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) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。
集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。
我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
論文 参考訳（メタデータ） (2022-10-13T03:55:04Z) - From Understanding the Population Dynamics of the NSGA-II to the First
Proven Lower Bounds [10.107150356618588]
我々は, NSGA-IIが適切な個体数を持つためには$Omega(Nnlog n)$関数評価が必要であることを証明した。
2つの目的の群集距離の寄与を計算するために、先頭定数を含む厳密な実行時推定値を得る。
論文 参考訳（メタデータ） (2022-09-28T10:11:20Z) - Lookback for Learning to Branch [77.32867454769936]
Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。
近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
論文 参考訳（メタデータ） (2022-06-30T02:33:32Z) - On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks [91.3755431537592]
ニューラルネットワークのニューラルカーネル(NTK)に重みのランダムプルーニングが及ぼす影響について検討する。
特に、この研究は、完全に接続されたニューラルネットワークとそのランダムに切断されたバージョン間のNTKの等価性を確立する。
論文 参考訳（メタデータ） (2022-03-27T15:22:19Z) - Differentially Private SGDA for Minimax Problems [83.57322009102973]
本研究は, 勾配勾配降下上昇(SGDA)が原始二重集団リスクの弱さの観点から最適に有効であることを示す。
これは、非滑らかで強固なコンケーブ設定において、初めて知られている結果である。
論文 参考訳（メタデータ） (2022-01-22T13:05:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。