論文の概要: Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
- arxiv url: http://arxiv.org/abs/2302.08021v2
- Date: Mon, 24 Apr 2023 14:39:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-25 20:57:11.984091
- Title: Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
- Title（参考訳）: Fourier Analysisがランタイム分析に到達 - プラトー上の精密ランタイム
- Authors: Benjamin Doerr, Andrew James Kelley
- Abstract要約: 本研究では, 離散フーリエ解析に基づく新しい手法を提案し, 進化的アルゴリズムがプラトーに費やす時間を解析する。
また、この手法を用いて、$(1+1)$進化アルゴリズムのランタイムを、有効サイズ2ell-1$の$n/ell$高原からなる新しいベンチマークで解析する。
- 参考スコア（独自算出の注目度）: 9.853329403413701
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new method based on discrete Fourier analysis to analyze the
time evolutionary algorithms spend on plateaus. This immediately gives a
concise proof of the classic estimate of the expected runtime of the $(1+1)$
evolutionary algorithm on the Needle problem due to Garnier, Kallel, and
Schoenauer (1999).
We also use this method to analyze the runtime of the $(1+1)$ evolutionary
algorithm on a new benchmark consisting of $n/\ell$ plateaus of effective size
$2^\ell-1$ which have to be optimized sequentially in a LeadingOnes fashion.
Using our new method, we determine the precise expected runtime both for
static and fitness-dependent mutation rates. We also determine the
asymptotically optimal static and fitness-dependent mutation rates. For $\ell =
o(n)$, the optimal static mutation rate is approximately $1.59/n$. The optimal
fitness dependent mutation rate, when the first $k$ fitness-relevant bits have
been found, is asymptotically $1/(k+1)$. These results, so far only proven for
the single-instance problem LeadingOnes, are thus true in a much broader
respect. We expect similar extensions to be true for other important results on
LeadingOnes. We are also optimistic that our Fourier analysis approach can be
applied to other plateau problems as well.
- Abstract（参考訳）: 本研究では, 離散フーリエ解析に基づく新しい手法を提案し, 進化的アルゴリズムがプラトーに費やす時間を解析する。
これはすぐに、garnier, kallel, schoenauer (1999) による針問題に対する$(1+1)$進化アルゴリズムの期待実行時間の古典的な推定の簡潔な証明を与える。
また、この手法を用いて、$(1+1)$の進化的アルゴリズムのランタイムを、$n/\ell$の有効サイズの2^\ell-1$からなる新しいベンチマークで解析する。
そこで,本手法では,静的および適合度に依存した変異率を推定する。
また、漸近的に最適な静的および適合依存的な突然変異率も決定する。
$\ell = o(n)$の場合、最適な静的突然変異率はおよそ1.59/n$である。
最初の$k$の適合ビットが見つかったとき、最適な適合依存突然変異率は漸近的に1/(k+1)$である。
これらの結果は、これまでのところ、シングルインスタンス問題のLeadingOnesでのみ証明されている。
LeadingOnesの他の重要な結果に対して、同様の拡張が真であると期待しています。
また、フーリエ解析アプローチが他の高原問題にも適用可能であることも楽観的です。
関連論文リスト
- Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic
Algorithm to Overcome the Noise [76.24156145566425]
進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。
我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
論文 参考訳（メタデータ） (2023-05-08T08:49:01Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - Runtime Analysis for Permutation-based Evolutionary Algorithms [9.044970217182117]
ビットストリングの場合のように、スクランブル演算子の重み付きバージョンは、ジャンプサイズが$m$のジャンプ関数において、$mTheta(m)$の順序の高速化につながることを示す。
短い経験的分析によりこれらの知見が裏付けられるが、また、ヴォイド突然変異率のような小さな実装の詳細が重要な違いをもたらすことも明らかである。
論文 参考訳（メタデータ） (2022-07-05T15:49:29Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - 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) - 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) - A new regret analysis for Adam-type algorithms [78.825194932103]
理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。
最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-21T19:19:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。