論文の概要: Speeding Up the NSGA-II With a Simple Tie-Breaking Rule

• arxiv url: http://arxiv.org/abs/2412.11931v1
• Date: Mon, 16 Dec 2024 16:15:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 14:00:36.039001
• Title: Speeding Up the NSGA-II With a Simple Tie-Breaking Rule
• Title（参考訳）: NSGA-IIのスピードアップ
• Authors: Benjamin Doerr, Tudor Ivan, Martin S. Krejca,
• Abstract要約: 我々は、次の人口の選択において、単純なタイブレーキングルールを解析する。 従来のOneMinMax、LeadingOnesZero、OneJumpJumpベンチマークでベンチマークの有効性を証明する。 両目的問題に対して,最小サイズ以上の集団規模を適度に増やすと,実行時保証が増加しないことを示す。
• 参考スコア（独自算出の注目度）: 9.044970217182117
• License:
• Abstract: The non-dominated sorting genetic algorithm~II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length $n$ and gap parameter $k$, we show a runtime guarantee of $O(\max\{n^{k+1},Nn\})$ function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice $N = \Theta(n)$, this result improves considerably over the $\Theta(Nn^k)$ runtime of the classic NSGA-II.
• Abstract（参考訳）: 非支配的ソート遺伝的アルゴリズム~II(NSGA-II)は最も一般的な多目的最適化ヒューリスティックである。 最近の数学的ランタイム解析により、離散探索空間における2つの欠点、すなわちNSGA-IIは2つ以上の目的で困難であり、人口規模の選択に非常に敏感であることがわかった。 これらの課題を克服するために、我々は、次の人口の選択における単純なタイブレーキングルールを解析する。 同様のルールが提案されているが、ほとんど受け入れられていない。 我々は,古典的なOneMinMax,LeadingOnesTrailingZeros,OneJumpZeroJumpベンチマーク上での数学的実行時解析によるタイブレークルールの有効性を実証する。 この修正されたNSGA-IIは、これまで3つ以上の目的を持つOneMinMaxで示されていた指数的な低ランタイム境界とは対照的に、多くの目的に対して3つのベンチマークを効率的に最適化できることを示す。 両目的問題に対して、最小許容サイズ以上の人口規模を適度に増やすと、実行時保証が増加しないことを示す。 例えば、表現長$n$とギャップパラメータ$k$のOneJumpZeroJump問題では、パレートフロントの少なくとも4倍の大きさのときに、$O(\max\{n^{k+1},Nn\})$関数のランタイム保証を示す。 最小選択$N = \Theta(n)$より大きい集団サイズの場合、この結果は古典的なNSGA-IIの$\Theta(Nn^k)$ランタイムよりも大幅に改善される。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• 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)
• 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)
• 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)
• Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection [27.270523212333018]
  本稿では,LOTZ,OneMinMax,COCZを解くための標準NSGA-IIのランニング時間解析について述べる。 具体的には、LOTZが$O(n3)$、OneMinMaxとCOCZが$O(n2log n)$であることを示す。 また, ランニングタイム上界はLOTZに強く, OneMinMax と COCZ にほぼ密であることを示す実験も行われた。
  論文  参考訳（メタデータ） (2022-03-22T09:10:50Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)

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

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