論文の概要: From Understanding the Population Dynamics of the NSGA-II to the First
Proven Lower Bounds
- arxiv url: http://arxiv.org/abs/2209.13974v1
- Date: Wed, 28 Sep 2022 10:11:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-29 16:29:17.903089
- Title: From Understanding the Population Dynamics of the NSGA-II to the First
Proven Lower Bounds
- Title（参考訳）: NSGA-IIの個体群動態の理解から第1報下部境界まで
- Authors: Benjamin Doerr, Zhongdi Qu
- Abstract要約: 我々は, NSGA-IIが適切な個体数を持つためには$Omega(Nnlog n)$関数評価が必要であることを証明した。
2つの目的の群集距離の寄与を計算するために、先頭定数を含む厳密な実行時推定値を得る。
- 参考スコア（独自算出の注目度）: 10.107150356618588
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Due to the more complicated population dynamics of the NSGA-II, none of the
existing runtime guarantees for this algorithm is accompanied by a non-trivial
lower bound. Via a first mathematical understanding of the population dynamics
of the NSGA-II, that is, by estimating the expected number of individuals
having a certain objective value, we prove that the NSGA-II with suitable
population size needs $\Omega(Nn\log n)$ function evaluations to find the
Pareto front of the OneMinMax problem and $\Omega(Nn^k)$ evaluations on the
OneJumpZeroJump problem with jump size $k$. These bounds are asymptotically
tight (that is, they match previously shown upper bounds) and show that the
NSGA-II here does not even in terms of the parallel runtime (number of
iterations) profit from larger population sizes. For the OneJumpZeroJump
problem and when the same sorting is used for the computation of the crowding
distance contributions of the two objectives, we even obtain a runtime estimate
that is tight including the leading constant.
- Abstract（参考訳）: NSGA-IIのより複雑な人口動態のため、このアルゴリズムの既存の実行時保証には非自明な下界が伴わない。
NSGA-IIの人口動態に関する最初の数学的理解として、ある目標値を持つ個体の期待数を推定することにより、適切な人口規模を持つNSGA-IIは、OneMinMax問題のパレートフロントを見つけるために$\Omega(Nn\log n)$関数評価と、ジャンプサイズが$kのOneJumpZeroJump問題に対する$\Omega(Nn^k)$関数評価が必要であることを証明した。
これらの境界は漸近的に厳密であり(つまり、前述した上限と一致する)、NSGA-IIは、より大きな人口規模から得られる平行実行時(反復数)の利益さえも示さない。
onejumpzerojump問題に対して、同じソートが2つの目的の群集距離寄与の計算に使用される場合、リード定数を含むタイトなランタイム推定を得ることもできる。
関連論文リスト
- Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - 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) - 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) - 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) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z) - Bilinear Graph Neural Network with Neighbor Interactions [106.80781016591577]
グラフニューラルネットワーク(GNN)は,グラフデータ上で表現を学習し,予測を行う強力なモデルである。
本稿では,グラフ畳み込み演算子を提案し,隣接するノードの表現の対の相互作用で重み付け和を増大させる。
このフレームワークをBGNN(Bilinear Graph Neural Network)と呼び、隣ノード間の双方向相互作用によるGNN表現能力を向上させる。
論文 参考訳（メタデータ） (2020-02-10T06:43:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。