論文の概要: An Extended Jump Function Benchmark for the Analysis of Randomized Search Heuristics

• arxiv url: http://arxiv.org/abs/2105.03090v1
• Date: Fri, 7 May 2021 07:21:10 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-10 12:11:57.167824
• Title: An Extended Jump Function Benchmark for the Analysis of Randomized Search Heuristics
• Title（参考訳）: ランダム化探索ヒューリスティック解析のための拡張ジャンプ関数ベンチマーク
• Authors: Henry Bambury, Antoine Bultel, Benjamin Doerr
• Abstract要約: 幅のフィットネスが低い谷を含むジャンプ関数の拡張クラス $textscJump_k,delta$ を提案します。 この新しいクラスは、特にグローバルな最適点から遠く離れている場合に、より広いフィットネスバレーでの実験を可能にすることを示す。
• 参考スコア（独自算出の注目度）: 4.38301148531795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Jump functions are the most studied non-unimodal benchmark in the theory of randomized search heuristics, in particular, evolutionary algorithms (EAs). They have significantly improved our understanding of how EAs escape from local optima. However, their particular structure -- to leave the local optimum one can only jump directly to the global optimum -- raises the question of how representative such results are. For this reason, we propose an extended class $\textsc{Jump}_{k,\delta}$ of jump functions that contain a valley of low fitness of width $\delta$ starting at distance $k$ from the global optimum. We prove that several previous results extend to this more general class: for all $k = o(n^{1/3})$ and $\delta < k$, the optimal mutation rate for the $(1+1)$~EA is $\frac{\delta}{n}$, and the fast $(1+1)$~EA runs faster than the classical $(1+1)$~EA by a factor super-exponential in $\delta$. However, we also observe that some known results do not generalize: the randomized local search algorithm with stagnation detection, which is faster than the fast $(1+1)$~EA by a factor polynomial in $k$ on $\textsc{Jump}_k$, is slower by a factor polynomial in $n$ on some $\textsc{Jump}_{k,\delta}$ instances. Computationally, the new class allows experiments with wider fitness valleys, especially when they lie further away from the global optimum.
• Abstract（参考訳）: ジャンプ関数はランダム化探索ヒューリスティック、特に進化アルゴリズム(eas)の理論において最も研究されている非ユニモーダルベンチマークである。 彼らは、EAが地域最適化からどのように逃れるかについての理解を著しく改善しました。 しかし、その特定の構造 -- 局所的な最適性を残すことは、グローバルな最適性に直接ジャンプするしかなく -- は、そのような結果がどの程度代表的であるかという疑問を提起する。 そこで本稿では,全球最適値から距離$k$で出発する幅の低適合性谷を含むジャンプ関数の拡張クラス$\textsc{jump}_{k,\delta}$を提案する。 すべての$k = o(n^{1/3})$ と $\delta < k$ に対して、$(1+1)$~ea の最適な突然変異率は$\frac{\delta}{n}$ であり、速い $(1+1)$~ea は、従来の$(1+1)$~ea よりも、$\delta$ で超指数的に速い。 しかし、いくつかの既知の結果が一般化していないことも観察している: スタグネーション検出を伴うランダム化局所探索アルゴリズムは、いくつかの$\textsc{jump}_{k,\delta}$インスタンスで$k$ on $\textsc{jump}_k$の係数多項式による高速$(1+1)$~eaよりも高速である。 計算の面では、この新クラスはより広いフィットネス・バレーでの実験を可能にする。

関連論文リスト

• Hyper-Heuristics Can Profit From Global Variation Operators [12.774575491521926]
  モーブアクセプタンス・ハイパーヒューリスティック(MAHH)は,マルチモーダルCLIFFベンチマークの局所的最適化を極めて効率よく残していることを示す。 また、MAHHの局所的な1ビット突然変異演算子を、EAで一般的に使用されるグローバルビットワイズ演算子に置き換えると、JUMP関数上の$min1, O(fraceln(n)m)m, O(nm)$のランタイムが得られることを示す。
  論文  参考訳（メタデータ） (2024-07-19T12:10:05Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• 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)
• Self-adjusting Population Sizes for the $(1, \lambda)$-EA on Monotone Functions [7.111443975103329]
  突然変異率$c/n$ for $cle 1$で、1:s+1)$-successルールで集団サイズを適応的に制御する。 この$c=1$のセットアップは1maxで$s1$で効率的であるが、$s ge 18$で非効率的であることを示す。
  論文  参考訳（メタデータ） (2022-04-01T15:46:12Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)
• 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)

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

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