論文の概要: Does Comma Selection Help To Cope With Local Optima
- arxiv url: http://arxiv.org/abs/2004.01274v3
- Date: Wed, 10 Nov 2021 08:03:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-17 09:27:03.928178
- Title: Does Comma Selection Help To Cope With Local Optima
- Title（参考訳）: Comma Selectionは、ローカルオプティマイマでコープを助けるか?
- Authors: Benjamin Doerr
- Abstract要約: 我々は、$(mu,lambda)$EAが$(mu+lambda)$EAに対してランタイム上の優位性をもたらすことはないことを示した。
これは、低次項から遠ざかるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行時結果である。
- 参考スコア（独自算出の注目度）: 9.853329403413701
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One hope when using non-elitism in evolutionary computation is that the
ability to abandon the current-best solution aids leaving local optima. To
improve our understanding of this mechanism, we perform a rigorous runtime
analysis of a basic non-elitist evolutionary algorithm (EA), the
$(\mu,\lambda)$ EA, on the most basic benchmark function with a local optimum,
the jump function. We prove that for all reasonable values of the parameters
and the problem, the expected runtime of the $(\mu,\lambda)$~EA is, apart from
lower order terms, at least as large as the expected runtime of its elitist
counterpart, the $(\mu+\lambda)$~EA (for which we conduct the first runtime
analysis on jump functions to allow this comparison). Consequently, the ability
of the $(\mu,\lambda)$~EA to leave local optima to inferior solutions does not
lead to a runtime advantage.
We complement this lower bound with an upper bound that, for broad ranges of
the parameters, is identical to our lower bound apart from lower order terms.
This is the first runtime result for a non-elitist algorithm on a multi-modal
problem that is tight apart from lower order terms.
- Abstract（参考訳）: 進化的計算に非エリートムを用いる場合の希望の一つは、現在の最良の解を放棄する能力が局所的なオプティマを離れる助けとなることである。
このメカニズムの理解を深めるために、我々は、局所最適なジャンプ関数を持つ最も基本的なベンチマーク関数の上に、基本的な非エリート進化アルゴリズム(ea)である$(\mu,\lambda)$ eaの厳密なランタイム解析を行う。
パラメータと問題のすべての妥当な値に対して、$(\mu,\lambda)$~EAの期待ランタイムは、少なくともそのエリート主義者が期待するランタイムである$(\mu+\lambda)$~EA(ジャンプ関数で最初のランタイム解析を行い、この比較を可能にする)の少なくとも大小の項を除いては、低次の項であることを示す。
したがって、$(\mu,\lambda)$~EAがローカル最適化を劣ったソリューションに委ねる能力は、実行時の優位性にはならない。
我々は、この下界を、パラメータの広い範囲において、下位次数項とは別個の下界と同一の上限で補う。
これは、低次項と密接な関係にあるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行結果である。
関連論文リスト
- Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
GOMEAは、リンク学習を利用して問題構造を効率的に活用する進化的アルゴリズムである。
GOMEAは確率の高い$O(m32k)$で解くことができ、$m$はサブファンクションの数、$k$はサブファンクションの長さである。
これは (1+1) 進化的 EA と比較して大きなスピードアップであり、これは$O(ln(m)(mk)k)$期待される評価を必要とする。
論文 参考訳（メタデータ） (2024-07-11T09:37:21Z) - Self-Adjusting Evolutionary Algorithms Are Slow on Multimodal Landscapes [0.0]
正の結果が他の局所最適値に拡張されないことを示す。
歪んだOneMaxベンチマークでは、自己調整の$(1, lambda)$-EAは、アルゴリズムがローカルオプティマからエスケープされるのを防ぐため、エリート的アルゴリズムと同じように遅くなる。
論文 参考訳（メタデータ） (2024-04-18T10:01:08Z) - Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳（メタデータ） (2023-12-19T01:52:13Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - 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) - Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms:
Why Success Rates Matter [0.0]
進化的アルゴリズム(EA)は、親や子孫のサイズや突然変異率など、いくつかのパラメータを持つ汎用的なオプティマイザである。
最近の理論的研究により、自己調整パラメータ制御機構は離散的な問題においてEAの最高の静的パラメータよりも優れていることが示されている。
論文 参考訳（メタデータ） (2021-04-12T16:44:54Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - A Rigorous Runtime Analysis of the $(1 + (\lambda, \lambda))$ GA on Jump
Functions [8.34061303235504]
我々は,このアルゴリズムの最初の実行時解析を,ジャンプ関数ベンチマークであるマルチモーダル問題クラス上で実施する。
ジャンプ関数の局所最適性を残すという孤立した問題に対して、$(n/k)k/2 eTheta(k)$のランタイムにつながる証明可能な最適パラメータを決定する。
論文 参考訳（メタデータ） (2020-04-14T17:54:12Z) - Incorporating Expert Prior in Bayesian Optimisation via Space Warping [54.412024556499254]
大きな探索空間では、アルゴリズムは関数の最適値に達する前に、いくつかの低関数値領域を通過する。
このコールドスタートフェーズの1つのアプローチは、最適化を加速できる事前知識を使用することである。
本稿では,関数の事前分布を通じて,関数の最適性に関する事前知識を示す。
先行分布は、探索空間を最適関数の高確率領域の周りに拡張し、最適関数の低確率領域の周りに縮小するようにワープする。
論文 参考訳（メタデータ） (2020-03-27T06:18:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。