論文の概要: A First Runtime Analysis of the NSGA-II on a Multimodal Problem

• arxiv url: http://arxiv.org/abs/2204.13750v1
• Date: Thu, 28 Apr 2022 19:44:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-02 15:12:11.654699
• Title: A First Runtime Analysis of the NSGA-II on a Multimodal Problem
• Title（参考訳）: マルチモーダル問題におけるNSGA-IIの最初の実行時解析
• Authors: Zhongdi Qu and Benjamin Doerr
• Abstract要約: この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。
• 参考スコア（独自算出の注目度）: 10.107150356618588
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Very recently, the first mathematical runtime analyses of the multi-objective evolutionary optimizer NSGA-II have been conducted (AAAI 2022, GECCO 2022 (to appear), arxiv 2022). We continue this line of research with a first runtime analysis of this algorithm on a benchmark problem consisting of two multimodal objectives. We prove that if the population size $N$ is at least four times the size of the Pareto front, then the NSGA-II with four different ways to select parents and bit-wise mutation optimizes the OneJumpZeroJump benchmark with jump size~$2 \le k \le n/4$ in time $O(N n^k)$. When using fast mutation, a recently proposed heavy-tailed mutation operator, this guarantee improves by a factor of $k^{\Omega(k)}$. Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm.
• Abstract（参考訳）: 最近では、多目的進化最適化器NSGA-IIの最初の数学的ランタイム解析が行われた(AAAI 2022, GECCO 2022 (to appear), arxiv 2022)。 2つのマルチモーダル目的からなるベンチマーク問題に対して,このアルゴリズムの初回実行時解析を行い,この一連の研究を継続する。 N$がパレートフロントの少なくとも4倍の大きさであれば、NSGA-IIは4つの異なる方法で親を選択することができ、ビットワイドの変異はOneJumpZeroJumpベンチマークをジャンプサイズ~2$le k \le n/4$ in time $O(N n^k)$で最適化する。 最近提案されたヘビーテール変異演算子であるfast mutationを使用すると、この保証は$k^{\omega(k)}$によって改善される。 この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。

関連論文リスト

• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。 現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。 本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-29T07:24:11Z)
• Runtime Analysis of the SMS-EMOA for Many-Objective Optimization [14.309243378538014]
  本稿ではSMSEMOAのための厳密なランタイム解析を行う。 SMS-EMOA は GSEMO と NSGA-II に匹敵する性能を示す。
  論文  参考訳（メタデータ） (2023-12-16T02:23:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Analysing the Robustness of NSGA-II under Noise [1.7205106391379026]
  EMOアルゴリズムNSGA-IIの最初のランタイム解析が登場した。 NSGA-IIがGSEMOを上回った時期は明らかではない。
  論文  参考訳（メタデータ） (2023-06-07T15:33:54Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• Massively Parallel Genetic Optimization through Asynchronous Propagation of Populations [50.591267188664666]
  Propulateは、グローバル最適化のための進化的最適化アルゴリズムとソフトウェアパッケージである。 提案アルゴリズムは, 選択, 突然変異, 交叉, 移動の変種を特徴とする。 Propulateは解の精度を犠牲にすることなく、最大で3桁高速であることがわかった。
  論文  参考訳（メタデータ） (2023-01-20T18:17:34Z)
• 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 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)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。 また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
  論文  参考訳（メタデータ） (2022-06-26T06:51:31Z)
• 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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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