論文の概要: Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms:
Why Success Rates Matter
- arxiv url: http://arxiv.org/abs/2104.05624v3
- Date: Wed, 12 Oct 2022 14:40:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-04 01:54:55.271298
- Title: Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms:
Why Success Rates Matter
- Title（参考訳）: 非エリート進化アルゴリズムの自己調整型人口サイズ:なぜ成功率が重要か
- Authors: Mario Alejandro Hevia Fajardo and Dirk Sudholt
- Abstract要約: 進化的アルゴリズム(EA)は、親や子孫のサイズや突然変異率など、いくつかのパラメータを持つ汎用的なオプティマイザである。
最近の理論的研究により、自己調整パラメータ制御機構は離散的な問題においてEAの最高の静的パラメータよりも優れていることが示されている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Evolutionary algorithms (EAs) are general-purpose optimisers that come with
several parameters like the sizes of parent and offspring populations or the
mutation rate. It is well known that the performance of EAs may depend
drastically on these parameters. Recent theoretical studies have shown that
self-adjusting parameter control mechanisms that tune parameters during the
algorithm run can provably outperform the best static parameters in EAs on
discrete problems. However, the majority of these studies concerned elitist EAs
and we do not have a clear answer on whether the same mechanisms can be applied
for non-elitist EAs.
We study one of the best-known parameter control mechanisms, the one-fifth
success rule, to control the offspring population size $\lambda$ in the
non-elitist $(1,\lambda)$ EA. It is known that the $(1,\lambda)$ EA has a sharp
threshold with respect to the choice of $\lambda$ where the expected runtime on
the benchmark function OneMax changes from polynomial to exponential time.
Hence, it is not clear whether parameter control mechanisms are able to find
and maintain suitable values of $\lambda$.
For OneMax we show that the answer crucially depends on the success rate $s$
(i.\,e.\ a one-$(s+1)$-th success rule). We prove that, if the success rate is
appropriately small, the self-adjusting $(1,\lambda)$ EA optimises OneMax in
$O(n)$ expected generations and $O(n \log n)$ expected evaluations, the best
possible runtime for any unary unbiased black-box algorithm. A small success
rate is crucial: we also show that if the success rate is too large, the
algorithm has an exponential runtime on OneMax and other functions with similar
characteristics.
- Abstract（参考訳）: 進化的アルゴリズム(EA)は、親や子孫のサイズや突然変異率など、いくつかのパラメータを持つ汎用的なオプティマイザである。
EAのパフォーマンスがこれらのパラメータに大きく依存していることはよく知られている。
近年の理論的研究により、アルゴリズムの実行中にパラメータをチューニングする自己調整パラメータ制御機構は、離散問題に対するeasの最良の静的パラメータよりも優れていることが示されている。
しかし、これらの研究の大部分はエリート主義的EAに関するものであり、同じメカニズムが非エリート主義EAに適用できるかどうかについては明確な答えは得られていない。
我々は,非エリート$(1,\lambda)$ ea において,子孫の個体数を$\lambda$ で制御するために,最もよく知られたパラメータ制御機構である1-fifth success rule について検討した。
1,\lambda)$ EAは、ベンチマーク関数で期待されるランタイムが多項式から指数時間に変化する$\lambda$の選択に関して、鋭い閾値を持つことが知られている。
したがって、パラメータ制御機構が$\lambda$の適切な値を見つけ、維持できるかどうかは不明である。
OneMax の場合、その答えは成功率$s$ (i) に大きく依存する。
である。
は 1-$(s+1)$-th の成功規則である。
成功率が適切に小さい場合、自己調整の$(1,\lambda)$ ea は 1max in $o(n)$ expected generations と $o(n \log n)$ expected evaluation を最適化する。
成功率は小さく、成功率が大きすぎると、アルゴリズムはonemaxの指数関数ランタイムと同じような特性を持つ他の関数を持っていることも示します。
関連論文リスト
- Self-Adjusting Evolutionary Algorithms Are Slow on Multimodal Landscapes [0.0]
正の結果が他の局所最適値に拡張されないことを示す。
歪んだOneMaxベンチマークでは、自己調整の$(1, lambda)$-EAは、アルゴリズムがローカルオプティマからエスケープされるのを防ぐため、エリート的アルゴリズムと同じように遅くなる。
論文 参考訳（メタデータ） (2024-04-18T10:01:08Z) - Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic
Algorithm to Overcome the Noise [76.24156145566425]
進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。
我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
論文 参考訳（メタデータ） (2023-05-08T08:49:01Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Hard Problems are Easier for Success-based Parameter Control [0.0]
進化的アルゴリズムにおける自己調整パラメータは、離散的な問題において最良の固定パラメータにマッチするか、より優れる。
簡単な斜面がない場合、自己調整が意図されたように機能することを示す。
本稿では,難易度の高い難易度の高い難易度の高い難易度関数のLeadingOnesと新しいクラスOneMaxBlocksについて論じる。
論文 参考訳（メタデータ） (2022-04-12T13:56:29Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - When Non-Elitism Meets Time-Linkage Problems [19.798298260257432]
Elitist (1+$lambda$)EAと非elitist (1,$lambda$)EAのパフォーマンスを比較することにより、非elitismの影響を分析します。
確率1$(1,$lambda$)EAがグローバルな最適値に到達でき、期待されるランタイムは$O(n3+clog n)$ with $lambda=c log_fracee-1 n$ for the constant $cge 1$であることを示す。
論文 参考訳（メタデータ） (2021-04-14T13:03:42Z) - Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
我々は、最適な突然変異率の分析を、OneMax問題の2つの変種に拡張する。
すべての集団サイズを2i mid 0 le i le 18$で計算します。
我々の結果は、一般的な進化的アプローチを測ることのできる低い境界を提供するばかりではない。
論文 参考訳（メタデータ） (2020-06-20T01:23:14Z) - Does Comma Selection Help To Cope With Local Optima [9.853329403413701]
我々は、$(mu,lambda)$EAが$(mu+lambda)$EAに対してランタイム上の優位性をもたらすことはないことを示した。
これは、低次項から遠ざかるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行時結果である。
論文 参考訳（メタデータ） (2020-04-02T21:39:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。