論文の概要: Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It

• arxiv url: http://arxiv.org/abs/2409.00306v1
• Date: Sat, 31 Aug 2024 00:10:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-06 15:46:49.785862
• Title: Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It
• Title（参考訳）: 進化的アルゴリズムは、ノイズを検知するほどロバストになる
• Authors: Denis Antipov, Benjamin Doerr,
• Abstract要約: 再評価の必要性は過大評価される可能性があり、実際は有害である。 この進化的アルゴリズムの最初の分析は、再評価なしに単一目的雑音の問題を解くことで、そのようなアルゴリズムが以前考えられていたよりもずっと良いノイズに対処できることを示している。
• 参考スコア（独自算出の注目度）: 10.165640083594573
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized search heuristics (RHSs) are generally believed to be robust to noise. However, almost all mathematical analyses on how RSHs cope with a noisy access to the objective function assume that each solution is re-evaluated whenever it is compared to others. This is unfortunate, both because it wastes computational resources and because it requires the user to foresee that noise is present (as in a noise-free setting, one would never re-evaluate solutions). In this work, we show the need for re-evaluations could be overestimated, and in fact, detrimental. For the classic benchmark problem of how the $(1+1)$ evolutionary algorithm optimizes the LeadingOnes benchmark, we show that without re-evaluations up to constant noise rates can be tolerated, much more than the $O(n^{-2} \log n)$ noise rates that can be tolerated when re-evaluating solutions. This first runtime analysis of an evolutionary algorithm solving a single-objective noisy problem without re-evaluations could indicate that such algorithms cope with noise much better than previously thought, and without the need to foresee the presence of noise.
• Abstract（参考訳）: ランダム検索ヒューリスティックス(RHS)は一般にノイズに対して堅牢であると考えられている。 しかしながら、RSHが目的関数への雑音的アクセスにどう対処するかに関する数学的解析のほとんど全ては、各解が他と比べられるたびに再評価されると仮定する。 これは、計算資源を浪費していることと、ノイズが存在することを予見する必要があるためである(ノイズのない環境では、ソリューションを再評価しない)ためである。 本研究は,再評価の必要性を過大評価し,実際は有害であることを示す。 1+1)$の進化的アルゴリズムがLeadingOnesベンチマークをどのように最適化するかという古典的なベンチマーク問題に対して、ソリューションを再評価する際に許容できる$O(n^{-2} \log n)$のノイズレートよりもはるかに高い、一定のノイズレートの再評価を許容できることを示す。 この進化的アルゴリズムの最初の実行時解析は、再評価なしに単一目的雑音の問題を解くことで、そのようなアルゴリズムが従来考えられていたよりもずっと良いノイズに対処し、ノイズの存在を予見する必要がないことを示している。

関連論文リスト

• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise [7.421135890148154]
  対象関数にノイズが存在する場合の古典的ベンチマークの最初の解析を行う。 ビット単位の先行ノイズが$p le alpha/n$, $alpha$ a suitable constant であることを示す。 すべての解が各イテレーションで再評価されると、ノイズレート$p = omega(log(n)/n2)$がスーパーポリノミカルランタイムにつながることが証明される。
  論文  参考訳（メタデータ） (2023-05-17T14:48:06Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• Higher degree sum-of-squares relaxations robust against oblivious outliers [14.58610686291355]
  我々は、$Y=X*+N$という形の推定モデルを考える。 本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
  論文  参考訳（メタデータ） (2022-11-14T13:09:12Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  この仮定から逸脱すると、実際により良い統計的推定結果が得られることが示される。 特に、最適な雑音分布は、データと異なり、また、別の家族からさえも異なる。
  論文  参考訳（メタデータ） (2022-03-02T13:59:20Z)
• ReLU Regression with Massart Noise [52.10842036932169]
  本稿では、ReLU回帰の基本的問題として、Rectified Linear Units(ReLU)をデータに適合させることを目標としている。 我々は自然およびよく研究された半ランダムノイズモデルであるMassartノイズモデルにおけるReLU回帰に着目した。 このモデルにおいて,パラメータの正確な回復を実現する効率的なアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-09-10T02:13:22Z)
• Learning based signal detection for MIMO systems with unknown noise statistics [84.02122699723536]
  本論文では,未知のノイズ統計による信号を堅牢に検出する一般化最大確率(ML)推定器を考案する。 実際には、システムノイズに関する統計的な知識はほとんどなく、場合によっては非ガウス的であり、衝動的であり、分析不可能である。 我々のフレームワークは、ノイズサンプルのみを必要とする教師なしの学習アプローチによって駆動される。
  論文  参考訳（メタデータ） (2021-01-21T04:48:15Z)

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

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