論文の概要: Analysing the Robustness of NSGA-II under Noise
- arxiv url: http://arxiv.org/abs/2306.04525v1
- Date: Wed, 7 Jun 2023 15:33:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-08 13:41:43.260637
- Title: Analysing the Robustness of NSGA-II under Noise
- Title（参考訳）: 騒音下におけるNSGA-IIのロバスト性の解析
- Authors: Duc-Cuong Dang, Andre Opris, Bahare Salehi, Dirk Sudholt
- Abstract要約: EMOアルゴリズムNSGA-IIの最初のランタイム解析が登場した。
NSGA-IIがGSEMOを上回った時期は明らかではない。
- 参考スコア（独自算出の注目度）: 1.7205106391379026
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Runtime analysis has produced many results on the efficiency of simple
evolutionary algorithms like the (1+1) EA, and its analogue called GSEMO in
evolutionary multiobjective optimisation (EMO). Recently, the first runtime
analyses of the famous and highly cited EMO algorithm NSGA-II have emerged,
demonstrating that practical algorithms with thousands of applications can be
rigorously analysed. However, these results only show that NSGA-II has the same
performance guarantees as GSEMO and it is unclear how and when NSGA-II can
outperform GSEMO. We study this question in noisy optimisation and consider a
noise model that adds large amounts of posterior noise to all objectives with
some constant probability $p$ per evaluation. We show that GSEMO fails badly on
every noisy fitness function as it tends to remove large parts of the
population indiscriminately. In contrast, NSGA-II is able to handle the noise
efficiently on \textsc{LeadingOnesTrailingZeroes} when $p<1/2$, as the
algorithm is able to preserve useful search points even in the presence of
noise. We identify a phase transition at $p=1/2$ where the expected time to
cover the Pareto front changes from polynomial to exponential. To our
knowledge, this is the first proof that NSGA-II can outperform GSEMO and the
first runtime analysis of NSGA-II in noisy optimisation.
- Abstract（参考訳）: 実行時解析は (1+1) ea のような単純な進化アルゴリズムの効率や、進化的多目的最適化 (emo) における gsemo と呼ばれる類似性の多くの結果を生み出した。
近年,広く引用されているEMOアルゴリズムNSGA-IIの最初の実行時解析が登場し,数千のアプリケーションによる実用的なアルゴリズムを厳格に分析できることが証明された。
しかし,これらの結果から,NSGA-IIはGSEMOと同じ性能保証を有しており,NSGA-IIがGSEMOより優れているかは明らかでない。
我々は,この質問を雑音の最適化で検討し,各目的に対して一定の確率 p$ で大量の後続雑音を付加する雑音モデルについて検討する。
その結果、GSEMOはノイズの多いフィットネス機能において、人口の大部分を無差別に除去する傾向にあることが明らかとなった。
これとは対照的に、NSGA-II は、$p<1/2$ のときに \textsc{LeadingOnesTrailingZeroes} 上でノイズを効率的に処理できる。
p=1/2$ で位相遷移を同定し、パレートフロントを覆う期待時間は多項式から指数関数に変化する。
我々の知る限り、NSGA-II が GSEMO より優れており、NSGA-II のノイズ最適化における最初の実行時解析である。
関連論文リスト
- Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis [3.748255320979002]
一般的な進化的多目的アルゴリズム(EMO)は、単純な(G)SEMOアルゴリズムと同じ性能を保証する。
我々は、GSEMOがOneTrapZeroTrapを最適化するために少なくとも$nn$のフィットネス評価を必要とするのに対し、一般的なEMOアルゴリズムNSGA-II、NSGA-III、SMS-EMOAは、ジェノタイプ重複を避けるための軽度な多様性メカニズムで拡張されているが、期待されるフィットネス評価は$O(n log n)$である。
論文 参考訳（メタデータ） (2024-05-22T12:09:00Z) - Runtime Analyses of NSGA-III on Many-Objective Problems [10.955844285189372]
本稿では,一般的な多目的ベンチマーク問題mLOTZ,mOMM,mCOCZにおけるNSGA-IIIのランタイム解析について述べる。
これらのパラメータは,問題次元,目的数,適合範囲によってどのようにスケールするかを示す。
我々の知る限り、これらは3つ以上の目的に対してNSGA-IIIの最初のランタイム解析である。
論文 参考訳（メタデータ） (2024-04-17T14:39:14Z) - Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic
Algorithm to Overcome the Noise [76.24156145566425]
進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。
我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
論文 参考訳（メタデータ） (2023-05-08T08:49:01Z) - 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) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳（メタデータ） (2022-06-02T15:21:55Z) - 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) - Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with
Heterophily [58.76759997223951]
我々はフォン・ノイマンエントロピーに基づく新しい計量を提案し、GNNのヘテロフィリー問題を再検討する。
また、異種データセット上でのほとんどのGNNの性能を高めるために、Conv-Agnostic GNNフレームワーク(CAGNN)を提案する。
論文 参考訳（メタデータ） (2022-03-19T14:26:43Z) - 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) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - GEO: Enhancing Combinatorial Optimization with Classical and Quantum
Generative Models [62.997667081978825]
我々は、生成モデルとして知られる機械学習モデルを活用する新しいフレームワークを導入し、最適化問題を解決する。
我々は、テンソルネットワークマシンに依存するGEOの量子インスパイアされたバージョンに注力する。
関数呼び出し数に対する固定予算が与えられた場合、その目標が最小限の最小値を求める場合、その優れた性能を示す。
論文 参考訳（メタデータ） (2021-01-15T18:18:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。