論文の概要: Better Approximation Guarantees for the NSGA-II by Using the Current Crowding Distance

• arxiv url: http://arxiv.org/abs/2203.02693v1
• Date: Sat, 5 Mar 2022 09:53:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-08 17:52:37.667423
• Title: Better Approximation Guarantees for the NSGA-II by Using the Current Crowding Distance
• Title（参考訳）: 現在の群集距離を用いたNSGA-IIの近似保証の改善
• Authors: Weijie Zheng, Benjamin Doerr
• Abstract要約: 本稿では,短時間の群集距離を用いたNSGA-IIの効率的な実装法を提案する。 パレートフロントのギャップは、少なくとも理論上の最小値よりも大きい定数因子であることが証明されている。
• 参考スコア（独自算出の注目度）: 15.56430085052365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent runtime analysis (Zheng, Liu, Doerr (2022)) has shown that a variant of the NSGA-II algorithm can efficiently compute the full Pareto front of the OneMinMax problem when the population size is by a constant factor larger than the Pareto front, but that this is not possible when the population size is only equal to the Pareto front size. In this work, we analyze how well the NSGA-II approximates the Pareto front when it cannot compute the whole front. We observe experimentally and by mathematical means that already when the population size is half the Pareto front size, relatively large gaps in the Pareto front remain. The reason for this phenomenon is that the NSGA-II in the selection stage computes the crowding distance once and then repeatedly removes individuals with smallest crowding distance without updating the crowding distance after each removal. We propose an efficient way to implement the NSGA-II using the momentary crowding distance. In our experiments, this algorithm approximates the Pareto front much better than the previous version. We also prove that the gaps in the Pareto front are at most a constant factor larger than the theoretical minimum.
• Abstract（参考訳）: 最近のランタイム解析 (Zheng, Liu, Doerr (2022)) では、NSGA-II アルゴリズムの変種は、集団サイズがパレート前面よりも大きい定数因子で 1MinMax 問題の完全パレートフロントを効率的に計算できるが、人口サイズがパレートフロントサイズに等しい場合にのみ、これは不可能であることを示した。 本研究では,NSGA-IIが正面全体を計算できない場合にパレートフロントをどの程度よく近似するかを解析する。 我々は,人口がパレートフロントサイズの半分である場合,パレートフロントの比較的大きな隙間が残っていることを実験的に,数学的に観察する。 この現象の理由は、選択段階のnsga-iiが1回群集距離を計算した後、各除去後の群集距離を更新せずに最小群集距離の個体を反復除去するからである。 本稿では,短時間の群集距離を用いた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)

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

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