論文の概要: Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function

• arxiv url: http://arxiv.org/abs/2010.13428v2
• Date: Thu, 8 Jul 2021 06:56:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-02 18:31:27.680880
• Title: Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function
• Title（参考訳）: 動的BinVal関数上の(mu+1)-EAの実行時解析
• Authors: Johannes Lengler, Simone Riedi
• Abstract要約: 進化的アルゴリズムを動的に研究し、各世代ごとに異なる適合関数が選択される。 特に、最適化の最も難しい領域は最適化の周辺ではない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study evolutionary algorithms in a dynamic setting, where for each generation a different fitness function is chosen, and selection is performed with respect to the current fitness function. Specifically, we consider Dynamic BinVal, in which the fitness functions for each generation is given by the linear function BinVal, but in each generation the order of bits is randomly permuted. For the (1+1)-EA it was known that there is an efficiency threshold $c_0$ for the mutation parameter, at which the runtime switches from quasilinear to exponential. A previous empirical evidence suggested that for larger population size $\mu$, the threshold may increase. We prove that this is at least the case in an $\varepsilon$-neighborhood around the optimum: the threshold of the (\mu+1)-EA becomes arbitrarily large if the $\mu$ is chosen large enough. However, the most surprising result is obtained by a second order analysis for $\mu=2$: the threshold INcreases with increasing proximity to the optimum. In particular, the hardest region for optimization is NOT around the optimum.
• Abstract（参考訳）: 本研究では,各世代ごとに異なる適合関数が選択され,現在の適合関数に対して選択が行われる動的環境下での進化的アルゴリズムについて検討する。 具体的には、各世代に対する適合関数が線形関数 BinVal によって与えられる動的 BinVal を考えるが、各世代においてビットの順序はランダムに置換される。 1+1)-eaでは、突然変異パラメータに対する効率の閾値 $c_0$ があることが知られており、ランタイムは準線形から指数関数に切り替える。 以前の実証的な証拠は、人口がより大きい場合、その閾値が増加することを示唆している。 これは少なくとも、最適値の周りの$\varepsilon$-neighborhoodのケースである:$\mu+1)-eaのしきい値が、$\mu$が十分大きく選択されると、任意に大きくなる。 しかし、最も驚くべき結果は$\mu=2$の2次解析によって得られる: しきい値が最適値に近づくにつれて増加する。 特に、最適化の最も難しい領域は最適化の周辺ではない。

関連論文リスト

• 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)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus [9.853329403413701]
  本研究では, 離散フーリエ解析に基づく新しい手法を提案し, 進化的アルゴリズムがプラトーに費やす時間を解析する。 また、この手法を用いて、$(1+1)$進化アルゴリズムのランタイムを、有効サイズ2ell-1$の$n/ell$高原からなる新しいベンチマークで解析する。
  論文  参考訳（メタデータ） (2023-02-16T01:46:06Z)
• 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)
• 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)
• An Extended Jump Function Benchmark for the Analysis of Randomized Search Heuristics [4.38301148531795]
  幅のフィットネスが低い谷を含むジャンプ関数の拡張クラス $textscJump_k,delta$ を提案します。 この新しいクラスは、特にグローバルな最適点から遠く離れている場合に、より広いフィットネスバレーでの実験を可能にすることを示す。
  論文  参考訳（メタデータ） (2021-05-07T07:21:10Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• 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)
• Large Population Sizes and Crossover Help in Dynamic Environments [0.0]
  動的線形関数の極端形式である動的 BinVal に対するより大きな集団サイズの影響について検討する。 人口が適度に増加すると、効率的なアルゴリズム構成の範囲が広がる。
  論文  参考訳（メタデータ） (2020-04-21T12:26:39Z)

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

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