論文の概要: Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
- arxiv url: http://arxiv.org/abs/2404.12746v3
- Date: Fri, 20 Jun 2025 09:11:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-23 19:00:04.637291
- Title: Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
- Title（参考訳）: 多目的進化アルゴリズムのためのニアタイトランタイム保証
- Authors: Simon Wietheger, Benjamin Doerr,
- Abstract要約: 我々は、(グローバル)SEMO、SMS-EMOA、バランスの取れたNSGA-II、NSGA-III、SPEA2を含む大規模なMOEAについて検討する。
LOTZベンチマークのSEMOのランタイムを$m ge 6$の目標にすると、実行時の保証は最大セットのサイズよりもさらに小さくなります。
- 参考スコア（独自算出の注目度）: 10.165640083594573
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing performance guarantees for classic MOEAs on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we consider a large class of MOEAs including the (global) SEMO, SMS-EMOA, balanced NSGA-II, NSGA-III, and SPEA2. For these, we prove near-tight runtime guarantees for the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Most of our bounds depend only linearly on the size of the largest incomparable set, showing that MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Most of our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of MOEAs.For the runtime of the SEMO on the LOTZ benchmark in $m \ge 6$ objectives, our runtime guarantees are even smaller than the size of the largest incomparable set. This is again the first time that such runtime guarantees are proven.
- Abstract（参考訳）: 多目的進化アルゴリズム(MOEA)の数学的ランタイム解析の分野では大きな進歩があったが、離散多目的問題におけるMOEAの性能はほとんど理解されていない。
特に、古典的ベンチマークにおける古典的MOEAのパフォーマンス保証は、すべてParetoの2倍程度である。
本研究では,(グローバル)SEMO,SMS-EMOA,バランスの取れたNSGA-II,NSGA-III,SPEA2などのMOEAについて検討する。
これらの結果から,OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, OneJumpZeroJumpの4つの最も一般的なベンチマーク問題に対して,ほぼ28のランタイム保証を証明した。
ほとんどの境界は、最大の非互換集合のサイズにのみ線形に依存しており、これらのベンチマーク上のMOEAは、以前の研究が示唆したよりも、多くの目標によく対応していることを示している。
我々の境界は、ビットストリングの目的数や長さの小さな多項式因子と密接な関係にある。
このような厳密な境界がMOEAの多目的利用のために証明されたのはこれが初めてであり、LOTZベンチマークにおけるSEMOのランタイムが$m \ge 6$の目標である場合、我々の実行保証は最大の非互換集合のサイズよりもさらに小さい。
このようなランタイム保証が証明されたのはこれが初めてである。
関連論文リスト
- Speeding Up the NSGA-II With a Simple Tie-Breaking Rule [9.044970217182117]
我々は、次の人口の選択において、単純なタイブレーキングルールを解析する。
従来のOneMinMax、LeadingOnesZero、OneJumpJumpベンチマークでベンチマークの有効性を証明する。
両目的問題に対して,最小サイズ以上の集団規模を適度に増やすと,実行時保証が増加しないことを示す。
論文 参考訳（メタデータ） (2024-12-16T16:15:37Z) - Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem [9.044970217182117]
NSGA-IIは最も顕著な多目的進化アルゴリズムである。
NSGA-IIは指数時間以下ではパレートフロントを計算できないことを示す。
論文 参考訳（メタデータ） (2024-11-15T07:50:40Z) - Runtime Analyses of NSGA-III on Many-Objective Problems [10.955844285189372]
本稿では,一般的な多目的ベンチマーク問題mLOTZ,mOMM,mCOCZにおけるNSGA-IIIのランタイム解析について述べる。
これらのパラメータは,問題次元,目的数,適合範囲によってどのようにスケールするかを示す。
我々の知る限り、これらは3つ以上の目的に対してNSGA-IIIの最初のランタイム解析である。
論文 参考訳（メタデータ） (2024-04-17T14:39:14Z) - SqueezeLLM: Dense-and-Sparse Quantization [80.32162537942138]
LLMにおける生成推論の主なボトルネックは、単一のバッチ推論のための計算ではなく、メモリ帯域幅である。
学習後量子化フレームワークであるSqueezeLLMを導入し、最大3ビットの超低精度でのロスレス圧縮を実現する。
本フレームワークは,2次情報に基づく最適ビット精度割当を探索する感度ベース非一様量子化法と,2次情報に基づくDense-and-Sparse分解法と,2次情報量割当値と感度重み値を効率的にスパース形式で格納するDense-and-Sparse分解法である。
論文 参考訳（メタデータ） (2023-06-13T08:57:54Z) - Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together! [100.19080749267316]
Sparsity May Cry"ベンチマーク(SMC-Bench)は、慎重に計算された4つのタスクと10のデータセットのコレクションである。
SMC-Benchは、よりスケーラブルで一般化可能なスパースアルゴリズムの開発を奨励するように設計されている。
論文 参考訳（メタデータ） (2023-03-03T18:47:21Z) - Beyond SOT: Tracking Multiple Generic Objects at Once [141.36900362724975]
ジェネリックオブジェクト追跡(ジェネリックオブジェクト追跡、英: Generic Object Tracking、GOT)は、ビデオの最初のフレームでボックスをバウンディングすることによって指定されたターゲットオブジェクトを追跡する問題である。
大規模GOTベンチマークであるLaGOTを導入し,複数のアノテート対象オブジェクトをシーケンス毎に含む。
提案手法は単一オブジェクトのGOTデータセットに対して高い競合性を実現し,TrackingNet上での新たな技術状態が84.4%の成功率で設定されている。
論文 参考訳（メタデータ） (2022-12-22T17:59:19Z) - 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) - 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) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。