論文の概要: The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III)
- arxiv url: http://arxiv.org/abs/2504.21552v1
- Date: Wed, 30 Apr 2025 11:49:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-09 19:07:41.55728
- Title: The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III)
- Title（参考訳）: 非支配的ソーティング遺伝的アルゴリズム(NSGA-III)のための最初の理論的近似法
- Authors: Renzhong Deng, Weijie Zheng, Benjamin Doerr,
- Abstract要約: N$が少なくとも参照点数$N_r$である場合、OneMinMaxベンチマークの最大空区間(MEI)インジケータによって測定される近似品質は、$lceilfrac(5-2sqrt2)nN_r-1rceil$よりも長い空区間がないことを示す。
これはNSGA-IIと連続生存選択の顕著な違いであり、個体数の増加は近似の質を向上させる。
- 参考スコア（独自算出の注目度）: 12.731778729620478
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work conducts a first theoretical analysis studying how well the NSGA-III approximates the Pareto front when the population size $N$ is less than the Pareto front size. We show that when $N$ is at least the number $N_r$ of reference points, then the approximation quality, measured by the maximum empty interval (MEI) indicator, on the OneMinMax benchmark is such that there is no empty interval longer than $\lceil\frac{(5-2\sqrt2)n}{N_r-1}\rceil$. This bound is independent of $N$, which suggests that further increasing the population size does not increase the quality of approximation when $N_r$ is fixed. This is a notable difference to the NSGA-II with sequential survival selection, where increasing the population size improves the quality of the approximations. We also prove two results indicating approximation difficulties when $N<N_r$. These theoretical results suggest that the best setting to approximate the Pareto front is $N_r=N$. In our experiments, we observe that with this setting the NSGA-III computes optimal approximations, very different from the NSGA-II, for which optimal approximations have not been observed so far.
- Abstract（参考訳）: この研究は、NSGA-IIIがパレートフロントよりもN$が小さい場合にパレートフロントをいかにうまく近似するかを研究する最初の理論的解析を行う。
N$が少なくとも参照点数$N_r$であるとき、OneMinMaxベンチマークの最大空区間(MEI)インジケータによって測定される近似品質は、$\lceil\frac{(5-2\sqrt2)n}{N_r-1}\rceil$よりも長い空区間がないことを示す。
この境界は$N$とは独立であり、これは、N_r$が固定されたときの近似の質がさらに大きくなることはないことを示唆している。
これはNSGA-IIと連続生存選択の顕著な違いであり、個体数の増加は近似の質を向上させる。
また,N<N_r$の場合の近似困難を示す2つの結果も証明した。
これらの理論的結果は、パレートフロントを近似する最良の設定は、$N_r=N$であることを示している。
実験では, NSGA-III は NSGA-II とは全く異なる最適近似を計算し, これまでに最適近似が観測されていない。
関連論文リスト
- Speeding Up the NSGA-II With a Simple Tie-Breaking Rule [9.044970217182117]
我々は、次の人口の選択において、単純なタイブレーキングルールを解析する。
従来のOneMinMax、LeadingOnesZero、OneJumpJumpベンチマークでベンチマークの有効性を証明する。
両目的問題に対して,最小サイズ以上の集団規模を適度に増やすと,実行時保証が増加しないことを示す。
論文 参考訳（メタデータ） (2024-12-16T16:15:37Z) - Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - 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) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - 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) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - 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) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。