論文の概要: Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity

• arxiv url: http://arxiv.org/abs/2404.07061v2
• Date: Sun, 20 Apr 2025 14:12:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-30 16:02:53.381131
• Title: Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity
• Title（参考訳）: 遺伝的アルゴリズムが人口多様性の最大値に近いことを証明してJump$_k$のランタイム境界を得る
• Authors: Andre Opris, Johannes Lengler, Dirk Sudholt,
• Abstract要約: 我々は、$(mu+1)$-$lambda_c$-GAの集団の多様性が、ほぼ完全な多様性の均衡に収束することを示した。 また、この分析は、JUMP$_k、delta$、HURDLEなどの他のユニタリ化関数にも拡張可能であることを示す。
• 参考スコア（独自算出の注目度）: 1.8434042562191815
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The JUMP$_k$ benchmark was the first problem for which crossover was proven to give a speed-up over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of $O(\text{poly}(n) + 4^k/p_c)$ for the ($\mu$+1) Genetic Algorithm ($(\mu+1)$ GA), but only for unrealistically small crossover probabilities $p_c$. To this date, it remains an open problem to prove similar upper bounds for realistic $p_c$; the best known runtime bound, in terms of function evaluations, for $p_c = \Omega(1)$ is $O((n/\chi)^{k-1})$, $\chi$ a positive constant. We provide a novel approach and analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the $(\mu+1)$ GA on JUMP$_k$. The $(\mu+1)$-$\lambda_c$-GA creates one offspring in each generation either by applying mutation to one parent or by applying crossover $\lambda_c$ times to the same two parents (followed by mutation), to amplify the probability of creating an accepted offspring in generations with crossover. We show that population diversity in the $(\mu+1)$-$\lambda_c$-GA converges to an equilibrium of near-perfect diversity. This yields an improved time bound of $O(\mu n \log(\mu) + 4^k)$ function evaluations for a range of $k$ under the mild assumptions $p_c = O(1/k)$ and $\mu \in \Omega(kn)$. For all constant $k$, the restriction is satisfied for some $p_c = \Omega(1)$ and it implies that the expected runtime for all constant $k$ and an appropriate $\mu = \Theta(kn)$ is bounded by $O(n^2 \log n)$, irrespective of $k$. For larger $k$, the expected time of the $(\mu+1)$-$\lambda_c$-GA is $\Theta(4^k)$, which is tight for a large class of unbiased black-box algorithms and faster than the original $(\mu+1)$ GA by a factor of $\Omega(1/p_c)$. We also show that our analysis can be extended to other unitation functions such as JUMP$_{k, \delta}$ and HURDLE.
• Abstract（参考訳）: JUMP$_k$ベンチマークは、クロスオーバーが突然変異のみの進化アルゴリズムを高速化することを証明した最初の問題である。 Jansen and Wegener (2002) は、$O(\text{poly}(n) + 4^k/p_c)$ for the$\mu$+1) Genetic Algorithm ($(\mu+1)$ GA を証明したが、非現実的に小さなクロスオーバー確率$p_c$に対してのみ証明した。 p_c = \Omega(1)$ is $O((n/\chi)^{k-1})$, $\chi$ a positive constant。 我々は、JUMP$_k$上の$(\mu+1)$ GAの変種に対して、ペアワイズハミング距離の和として測定された、新しいアプローチと人口多様性の進化を分析する。 $(\mu+1)$-$\lambda_c$-GAは、1つの親に突然変異を施すか、同じ2人の親に$\lambda_c$ timesを施すことで、それぞれの世代で1つの子孫を生成する。 我々は、$(\mu+1)$-$\lambda_c$-GAの集団の多様性が、ほぼ完全な多様性の平衡に収束することを示した。 これにより、$O(\mu n \log(\mu) + 4^k)$関数の評価は、緩やかな仮定で$p_c = O(1/k)$と$\mu \in \Omega(kn)$で改善される。 すべての定数$k$に対して、この制限は、ある$p_c = \Omega(1)$に対して満たされ、すべての定数$k$と適切な$\mu = \Theta(kn)$に対する期待ランタイムは、$k$に関係なく$O(n^2 \log n)$で有界であることを意味する。 より大きな$k$の場合、$(\mu+1)$-$\lambda_c$-GAの期待時刻は$\Theta(4^k)$であり、未バイアスのブラックボックスアルゴリズムの大きなクラスに対して厳格であり、$\Omega(1/p_c)$の係数で元の$(\mu+1)$ GAよりも高速である。 また、この解析は JUMP$_{k, \delta}$, HURDLE などの他のユニタリ化関数にも拡張可能であることを示す。

関連論文リスト

• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm [7.421135890148154]
  集団サイズが$mu=O(n)$の遺伝的アルゴリズムは、ギャップサイズが$k ge 3$のジャンプ関数を最適化する。 この多様性は、(二次的ではなく)$mu$で指数関数的に高い確率で持続することを示す。 すべての$cln(n)lemu le n/log n$, with $c$ a suitable constant, the runtime of the $(mu+1)$ GA on $mathrmJump_k$, with $k
  論文  参考訳（メタデータ） (2023-02-24T10:50:24Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• 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)
• Convergence Rate of the (1+1)-Evolution Strategy with Success-Based Step-Size Adaptation on Convex Quadratic Functions [20.666734673282498]
  1+1)-進化戦略(ES)と成功に基づくステップサイズ適応を一般凸二次関数で解析する。 1+1)-ES の収束速度は、一般凸二次函数上で明示的に厳密に導かれる。
  論文  参考訳（メタデータ） (2021-03-02T09:03:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments [9.853329403413701]
  Sutton and Witt (GECCO) が分析した選択自由定常遺伝的アルゴリズムは、特定のターゲット探索点を見つけるために、期待する数$Omega (2n / sqrt n)$を取ることを証明している。 我々の結果は、以前の$Omega(exp(ndelta/2))$の下位境界よりも改善され、人口規模が$muに対して有効である。
  論文  参考訳（メタデータ） (2020-06-08T15:04:51Z)
• 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)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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