論文の概要: Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima

• arxiv url: http://arxiv.org/abs/2304.09712v1
• Date: Wed, 19 Apr 2023 15:00:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-20 14:04:17.782242
• Title: Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima
• Title（参考訳）: ランダム植込みオプティマを用いたOneMaxにおけるコマ選択性能の向上
• Authors: Joost Jorritsma, Johannes Lengler, Dirk Sudholt
• Abstract要約: このベンチマークでは、コンマの選択($(1,lambda)$ EA)が、選択($(1+lambda)$ EA)よりも高速であることを示す。 凍結音を解析するための新しい手法を開発し、独立性のある尾境界を持つ強力で汎用的な固定目標値を与える。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: It is an ongoing debate whether and how comma selection in evolutionary algorithms helps to escape local optima. We propose a new benchmark function to investigate the benefits of comma selection: OneMax with randomly planted local optima, generated by frozen noise. We show that comma selection (the $(1,\lambda)$ EA) is faster than plus selection (the $(1+\lambda)$ EA) on this benchmark, in a fixed-target scenario, and for offspring population sizes $\lambda$ for which both algorithms behave differently. For certain parameters, the $(1,\lambda)$ EA finds the target in $\Theta(n \ln n)$ evaluations, with high probability (w.h.p.), while the $(1+\lambda)$ EA) w.h.p. requires almost $\Theta((n\ln n)^2)$ evaluations. We further show that the advantage of comma selection is not arbitrarily large: w.h.p. comma selection outperforms plus selection at most by a factor of $O(n \ln n)$ for most reasonable parameter choices. We develop novel methods for analysing frozen noise and give powerful and general fixed-target results with tail bounds that are of independent interest.
• Abstract（参考訳）: 進化的アルゴリズムにおけるコマの選択が局所最適化から逃れるのにどう役立つのか、議論が続いている。 そこで我々は,コマ選択の利点を検討するための新しいベンチマーク関数を提案する。 このベンチマークでは、コマ選択($(1,\lambda)$ EA)は、固定ターゲットシナリオにおいて、このベンチマークでの選択($(1+\lambda)$ EA)よりも高速であり、両方のアルゴリズムが異なる振る舞いをする子孫サイズ$\lambda$であることを示す。 あるパラメータに対して、$(1,\lambda)$ EAは、高い確率(w.h.p.)を持つ$\Theta(n \ln n)$評価においてターゲットを見つけ、$(1+\lambda)$ EA.p.は、ほぼ$\Theta((n\ln n)^2)$評価を必要とする。 w.h.p. comma selection は、最も合理的なパラメータ選択に対して$O(n \ln n)$ の係数で、選択よりも優れる。 凍結音を解析するための新しい手法を開発し、独立性のある尾境界を持つ強力で一般的な固定目標値を与える。

関連論文リスト

• Run Time Bounds for Integer-Valued OneMax Functions [0.9012198585960443]
  探索空間 $mathbbZn$ を多値決定変数 $0,ldots,r-1n$ の観点から考える。 ステップサイズ適応のRSSが$Theta(n cdot log(|a|_1))$の最適化時間を達成することを示す。 本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
  論文  参考訳（メタデータ） (2023-07-21T18:49:06Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34: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)
• Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms: Why Success Rates Matter [0.0]
  進化的アルゴリズム(EA)は、親や子孫のサイズや突然変異率など、いくつかのパラメータを持つ汎用的なオプティマイザである。 最近の理論的研究により、自己調整パラメータ制御機構は離散的な問題においてEAの最高の静的パラメータよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2021-04-12T16:44:54Z)
• Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
  相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。 提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
  論文  参考訳（メタデータ） (2020-09-08T20:32:26Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• 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)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Does Comma Selection Help To Cope With Local Optima [9.853329403413701]
  我々は、$(mu,lambda)$EAが$(mu+lambda)$EAに対してランタイム上の優位性をもたらすことはないことを示した。 これは、低次項から遠ざかるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行時結果である。
  論文  参考訳（メタデータ） (2020-04-02T21:39:33Z)

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

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