Fugu-MT 論文翻訳(概要): Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms

論文の概要: Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms

arxiv url: http://arxiv.org/abs/2404.12746v2
Date: Tue, 11 Jun 2024 11:41:49 GMT
ステータス: 処理完了
システム内更新日: 2024-06-12 22:03:14.316125
Title: Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
Title（参考訳）: 多目的進化アルゴリズムのためのニアタイトランタイム保証
Authors: Simon Wietheger, Benjamin Doerr,
Abstract要約: 従来のベンチマークでは,SEMO,グローバルSEMO,SMS-EMOAアルゴリズムのほぼ28のランタイム保証が証明されている。このような厳密な境界がこれらのMOEAの多目的利用に対して証明されたのはこれが初めてである。
参考スコア（独自算出の注目度）: 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 bounds for the SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we prove near-tight runtime guarantees for these three algorithms on the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Our bounds depend only linearly on the Pareto front size, showing that these MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. 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 these MOEAs. While it is known that such results cannot hold for the NSGA-II, we do show that our bounds, via a recent structural result, transfer to the NSGA-III algorithm.
Abstract（参考訳）: 多目的進化アルゴリズム(MOEA)の数学的ランタイム解析の分野では大きな進歩があったが、離散多目的問題におけるMOEAの性能はほとんど理解されていない。特に、古典的なベンチマークにおけるSEMO、グローバルSEMO、SMS-EMOAアルゴリズムの既存のバウンダリは、すべてParetoフロントの約2倍である。本研究では,最も一般的な4つのベンチマーク問題であるOneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJumpにおいて,これらの3つのアルゴリズムのほぼ28のランタイム保証を証明した。私たちのバウンダリはParetoのフロントサイズにのみ依存しており、これらのベンチマーク上のMOEAは、以前の研究が示唆していたよりも、多くの目標にずっとうまく対応していることを示している。我々の境界は、ビットストリングの目的数と長さの小さな多項式因子と密接な関係にある。このような厳密な境界がこれらのMOEAの多目的利用に対して証明されたのはこれが初めてである。このような結果はNSGA-IIでは成り立たないことが知られているが、我々は最近の構造的結果を通じてNSGA-IIIアルゴリズムに遷移することを示す。

関連論文リスト

Runtime Analyses of NSGA-III on Many-Objective Problems [10.955844285189372]
本稿では,一般的な多目的ベンチマーク問題mLOTZ,mOMM,mCOCZにおけるNSGA-IIIのランタイム解析について述べる。これらのパラメータは,問題次元,目的数,適合範囲によってどのようにスケールするかを示す。我々の知る限り、これらは3つ以上の目的に対してNSGA-IIIの最初のランタイム解析である。
論文参考訳（メタデータ） (2024-04-17T14:39:14Z)
Runtime Analysis of the SMS-EMOA for Many-Objective Optimization [14.309243378538014]
本稿ではSMSEMOAのための厳密なランタイム解析を行う。 SMS-EMOA は GSEMO と NSGA-II に匹敵する性能を示す。
論文参考訳（メタデータ） (2023-12-16T02:23:09Z)
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)

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

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