論文の概要: Already Moderate Population Sizes Provably Yield Strong Robustness to Noise

• arxiv url: http://arxiv.org/abs/2404.02090v1
• Date: Tue, 2 Apr 2024 16:35:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-03 15:39:47.772888
• Title: Already Moderate Population Sizes Provably Yield Strong Robustness to Noise
• Title（参考訳）: 騒音に強いロバスト性を持つ中性個体群
• Authors: Denis Antipov, Benjamin Doerr, Alexandra Ivanova,
• Abstract要約: 2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
• 参考スコア（独自算出の注目度）: 53.27802701790209
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Experience shows that typical evolutionary algorithms can cope well with stochastic disturbances such as noisy function evaluations. In this first mathematical runtime analysis of the $(1+\lambda)$ and $(1,\lambda)$ evolutionary algorithms in the presence of prior bit-wise noise, we show that both algorithms can tolerate constant noise probabilities without increasing the asymptotic runtime on the OneMax benchmark. For this, a population size $\lambda$ suffices that is at least logarithmic in the problem size $n$. The only previous result in this direction regarded the less realistic one-bit noise model, required a population size super-linear in the problem size, and proved a runtime guarantee roughly cubic in the noiseless runtime for the OneMax benchmark. Our significantly stronger results are based on the novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring. We are optimistic that the technical lemmas resulting from this insight will find applications also in future mathematical runtime analyses of evolutionary algorithms.
• Abstract（参考訳）: 経験から、典型的な進化的アルゴリズムは、ノイズ関数評価のような確率的障害にうまく対応できることが示されている。 1+\lambda)$と$(1,\lambda)$の進化的アルゴリズムのこの最初の数学的ランタイム解析では、両方のアルゴリズムがOneMaxベンチマークの漸近的ランタイムを増大させることなく、一定のノイズ確率を許容できることが示される。 これに対し、集団サイズ$\lambda$ sufficesは、少なくとも問題サイズ$n$の対数である。 この方向に向けられた唯一の結果は、現実的でない1ビットノイズモデルであり、問題サイズが超直線的であることが必要であり、OneMaxベンチマークのノイズレスランタイムでは、ほぼ3分の1の保証が保証された。 より強力な結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという新しい証明理論に基づくものである。 この知見から得られた技術的補題は、進化的アルゴリズムの数学的ランタイム解析にも応用できると楽観的である。

関連論文リスト

• Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It [10.165640083594573]
  再評価の必要性は過大評価される可能性があり、実際は有害である。 この進化的アルゴリズムの最初の分析は、再評価なしに単一目的雑音の問題を解くことで、そのようなアルゴリズムが以前考えられていたよりもずっと良いノイズに対処できることを示している。
  論文  参考訳（メタデータ） (2024-08-31T00:10:10Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• 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)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Exponential Upper Bounds for the Runtime of Randomized Search Heuristics [9.853329403413701]
  アルゴリズムの任意のランダム化ローカルサーチ,アルゴリズム,シミュレートされたアニーリング,および (1+1) 進化的アルゴリズムが,任意の擬ブール弱単調関数を最適化可能であることを示す。 また、OneMaxベンチマークにおいて、単純な遺伝的アルゴリズムの突然変異に基づくバージョンの実行時の指数的な上限を証明した。
  論文  参考訳（メタデータ） (2020-04-13T00:24:33Z)

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

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