論文の概要: Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic
Algorithm to Overcome the Noise
- arxiv url: http://arxiv.org/abs/2305.04553v1
- Date: Mon, 8 May 2023 08:49:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-09 14:56:19.232340
- Title: Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic
Algorithm to Overcome the Noise
- Title(参考訳): 1 + (\lambda, \lambda))$の遺伝的アルゴリズムがノイズを克服するのを助ける
- Authors: Alexandra Ivanova, Denis Antipov, Benjamin Doerr
- Abstract要約: 進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。
我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
- 参考スコア(独自算出の注目度): 76.24156145566425
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary algorithms are known to be robust to noise in the evaluation of
the fitness. In particular, larger offspring population sizes often lead to
strong robustness. We analyze to what extent the $(1+(\lambda,\lambda))$
genetic algorithm is robust to noise. This algorithm also works with larger
offspring population sizes, but an intermediate selection step and a
non-standard use of crossover as repair mechanism could render this algorithm
less robust than, e.g., the simple $(1+\lambda)$ evolutionary algorithm. Our
experimental analysis on several classic benchmark problems shows that this
difficulty does not arise. Surprisingly, in many situations this algorithm is
even more robust to noise than the $(1+\lambda)$~EA.
- Abstract(参考訳): 進化的アルゴリズムは、適応性の評価において雑音に対して頑健であることが知られている。
特に、大きな子孫の個体数は、しばしば強い頑丈さをもたらす。
我々は、$(1+(\lambda,\lambda)の遺伝的アルゴリズムがどんなにノイズに強いかを分析する。
このアルゴリズムは、より大きな子孫の集団サイズで動作するが、中間選択ステップと、修復機構としてのクロスオーバーの非標準的な使用により、単純な$(1+\lambda)$進化アルゴリズムよりも頑丈ではない。
いくつかの古典的ベンチマーク問題に対する実験的解析は、この困難は生じないことを示している。
驚いたことに、多くの状況において、このアルゴリズムは$(1+\lambda)$~EAよりもノイズに強い。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - 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) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳(メタデータ) (2023-01-11T09:12:28Z) - Higher degree sum-of-squares relaxations robust against oblivious
outliers [14.58610686291355]
我々は、$Y=X*+N$という形の推定モデルを考える。
本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
論文 参考訳(メタデータ) (2022-11-14T13:09:12Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Learning stochastic decision trees [19.304587350775385]
対向雑音に対して最適に耐性のある決定木を学習するための準ポリノミカル時間アルゴリズムを提案する。
私たちのアルゴリズムはさらに適切で、それ自体が決定木である仮説を返します。
論文 参考訳(メタデータ) (2021-05-08T04:54:12Z) - The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
我々は、$(lambda,lambda)$の遺伝的アルゴリズムが、$O(n2)$のフィットネスクエリで最適であることを示す。
また,Hamと呼ばれる置換に基づく問題に対して,このアルゴリズムの最初の解析を行った。
論文 参考訳(メタデータ) (2020-04-18T17:04:57Z) - Exponential Upper Bounds for the Runtime of Randomized Search Heuristics [9.853329403413701]
アルゴリズムの任意のランダム化ローカルサーチ,アルゴリズム,シミュレートされたアニーリング,および (1+1) 進化的アルゴリズムが,任意の擬ブール弱単調関数を最適化可能であることを示す。
また、OneMaxベンチマークにおいて、単純な遺伝的アルゴリズムの突然変異に基づくバージョンの実行時の指数的な上限を証明した。
論文 参考訳(メタデータ) (2020-04-13T00:24:33Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳(メタデータ) (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。