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

• arxiv url: http://arxiv.org/abs/2409.00306v2
• Date: Wed, 07 May 2025 08:44:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-08 19:07:35.715879
• Title: Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It
• Title（参考訳）: 進化的アルゴリズムは、ノイズを検知するほどロバストになる
• Authors: Denis Antipov, Benjamin Doerr,
• Abstract要約: 我々は、再評価なしに単目的雑音問題を解く進化的アルゴリズムの最初の数学的実行時解析を行う。 再評価を行わないアルゴリズムは、従来のLeadingOnesベンチマークを最大定音率で最適化できることを示す。
• 参考スコア（独自算出の注目度）: 10.165640083594573
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized search heuristics (RSHs) are known to have a certain robustness to noise. Mathematical analyses trying to quantify rigorously how robust RSHs are to a noisy access to the objective function typically assume that each solution is re-evaluated whenever it is compared to others. This aims at preventing that a single noisy evaluation has a lasting negative effect, but is computationally expensive and 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 conduct the first mathematical runtime analysis of an evolutionary algorithm solving a single-objective noisy problem without re-evaluations. We prove that the $(1+1)$ evolutionary algorithm without re-evaluations can optimize the classic LeadingOnes benchmark with up to constant noise rates, in sharp contrast to the version with re-evaluations, where only noise with rates $O(n^{-2} \log n)$ can be tolerated. This result suggests that re-evaluations are much less needed than what was previously thought, and that they actually can be highly detrimental. The insights from our mathematical proofs indicate that this similar results are plausible for other classic benchmarks.
• Abstract（参考訳）: ランダムな探索ヒューリスティックス(RSHs)は、ノイズに対して一定の堅牢性を持つことが知られている。 客観的関数への雑音的アクセスに対して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)

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

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