論文の概要: Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax
- arxiv url: http://arxiv.org/abs/2006.11457v1
- Date: Sat, 20 Jun 2020 01:23:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 22:28:44.059004
- Title: Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax
- Title（参考訳）: OneMax上の$(1+\lambda)$ EAの最適変更率
- Authors: Maxim Buzdalov and Carola Doerr
- Abstract要約: 我々は、最適な突然変異率の分析を、OneMax問題の2つの変種に拡張する。
すべての集団サイズを2i mid 0 le i le 18$で計算します。
我々の結果は、一般的な進化的アプローチを測ることのできる低い境界を提供するばかりではない。
- 参考スコア（独自算出の注目度）: 1.0965065178451106
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The OneMax problem, alternatively known as the Hamming distance problem, is
often referred to as the "drosophila of evolutionary computation (EC)", because
of its high relevance in theoretical and empirical analyses of EC approaches.
It is therefore surprising that even for the simplest of all mutation-based
algorithms, Randomized Local Search and the (1+1) EA, the optimal mutation
rates were determined only very recently, in a GECCO 2019 poster.
In this work, we extend the analysis of optimal mutation rates to two
variants of the $(1+\lambda)$ EA and to the $(1+\lambda)$ RLS. To do this, we
use dynamic programming and, for the $(1+\lambda)$ EA, numeric optimization,
both requiring $\Theta(n^3)$ time for problem dimension $n$. With this in hand,
we compute for all population sizes $\lambda \in \{2^i \mid 0 \le i \le 18\}$
and for problem dimension $n \in \{1000, 2000, 5000\}$ which mutation rates
minimize the expected running time and which ones maximize the expected
progress.
Our results do not only provide a lower bound against which we can measure
common evolutionary approaches, but we also obtain insight into the structure
of these optimal parameter choices. For example, we show that, for large
population sizes, the best number of bits to flip is not monotone in the
distance to the optimum. We also observe that the expected remaining running
time are not necessarily unimodal for the $(1+\lambda)$ EA$_{0 \rightarrow 1}$
with shifted mutation.
- Abstract（参考訳）: また、ハミング距離問題(hamming distance problem)としても知られるonemax問題は、ecアプローチの理論的および経験的解析に高い関連性があるため、しばしば「進化的計算のドロソフィラ (drosophila of evolutionary computation, ec) 」と呼ばれる。
したがって、すべての突然変異に基づくアルゴリズムの最も単純な例であるランダム化局所探索と(1+1) EAにおいて、最適な突然変異率はごく最近になってGECCO 2019のポスターで決定された。
本研究では、最適な突然変異率の分析を、$(1+\lambda)$ EAと$(1+\lambda)$ RLSの2つの変種に拡張する。
これを実現するために、動的プログラミングを使用し、$(1+\lambda)$ EAの数値最適化には$\Theta(n^3)$時間と$n$が必要です。
これにより、全ての集団サイズを$\lambda \in \{2^i \mid 0 \le i \le 18\}$、および問題次元$n \in \{1000, 2000, 5000\}$で計算し、変異率は期待される実行時間を最小化し、期待される進行時間を最大化する。
我々の結果は、共通の進化的アプローチを測定できる下界を提供するだけでなく、これらの最適パラメータ選択の構造についての洞察を得る。
例えば、大きな個体数に対して、フリップするビットの最大数は最適点までの距離において単調ではないことを示す。
また、1+\lambda)$ EA$_{0 \rightarrow 1}$ が変化した場合には、残りのランニング時間は必ずしもunimodalではないことも観察する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - Hardest Monotone Functions for Evolutionary Algorithms [0.0]
自己調整する$(1,lambda)$-EAに対して、Adrial Dynamic BinVal (ADBV) は最適化する最も難しい動的単調関数である。
本稿では,探索点内の残零点数が$n/2$未満である場合に,ADBVと一致する関数スイッチング動的ビンVal(SDBV)を導入する。
論文 参考訳（メタデータ） (2023-11-13T16:13:30Z) - Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions [0.44241702149260353]
Witt は (1+1) 進化的アルゴリズムの標準的なビット変異は任意の線形関数の最適値を見つけるのに時間を必要とすることを示した。
この結果は、標準ビット突然変異が任意の未バイアス突然変異演算子に置き換えられた場合にどのように一般化されるかを検討する。
論文 参考訳（メタデータ） (2023-02-23T21:09:15Z) - Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus [9.853329403413701]
本研究では, 離散フーリエ解析に基づく新しい手法を提案し, 進化的アルゴリズムがプラトーに費やす時間を解析する。
また、この手法を用いて、$(1+1)$進化アルゴリズムのランタイムを、有効サイズ2ell-1$の$n/ell$高原からなる新しいベンチマークで解析する。
論文 参考訳（メタデータ） (2023-02-16T01:46:06Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15: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) - Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function [0.0]
進化的アルゴリズムを動的に研究し、各世代ごとに異なる適合関数が選択される。
特に、最適化の最も難しい領域は最適化の周辺ではない。
論文 参考訳（メタデータ） (2020-10-26T08:55:53Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。