論文の概要: Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm

• arxiv url: http://arxiv.org/abs/2302.12570v1
• Date: Fri, 24 Feb 2023 10:50:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-27 13:57:07.984717
• Title: Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm
• Title（参考訳）: 遺伝的アルゴリズム$(\mu+1)の持続的多様性と優れたランタイム保証
• Authors: Benjamin Doerr, Aymen Echarghaoui, Mohammed Jamal, Martin S. Krejca
• Abstract要約: 集団サイズが$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
• 参考スコア（独自算出の注目度）: 7.421135890148154
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Most evolutionary algorithms (EAs) used in practice employ crossover. In contrast, only for few and mostly artificial examples a runtime advantage from crossover could be proven with mathematical means. The most convincing such result shows that the $(\mu+1)$ genetic algorithm (GA) with population size $\mu=O(n)$ optimizes jump functions with gap size $k \ge 3$ in time $O(n^k / \mu + n^{k-1}\log n)$, beating the $\Theta(n^k)$ runtime of many mutation-based EAs. This result builds on a proof that the GA occasionally and then for an expected number of $\Omega(\mu^2)$ iterations has a population that is not dominated by a single genotype. In this work, we show that this diversity persist with high probability for a time exponential in $\mu$ (instead of quadratic). From this better understanding of the population diversity, we obtain stronger runtime guarantees, among them the statement that for all $c\ln(n)\le\mu \le n/\log n$, with $c$ a suitable constant, the runtime of the $(\mu+1)$ GA on $\mathrm{Jump}_k$, with $k \ge 3$, is $O(n^{k-1})$. Consequently, already with logarithmic population sizes, the GA gains a speed-up of order $\Omega(n)$ from crossover.
• Abstract（参考訳）: ほとんどの進化的アルゴリズム(EA)はクロスオーバーを採用している。 対照的に、少数の人工的な例でのみ、クロスオーバーによる実行時の利点は数学的手法で証明できる。 最も説得力のある結果は、人口サイズの $(\mu+1)$ 遺伝的アルゴリズム (ga) が、ギャップサイズ $k \ge 3$ in time $o(n^k / \mu + n^{k-1}\log n)$ でジャンプ関数を最適化し、多くの変異ベースの eas の $\theta(n^k)$ ランタイムを上回ることである。 この結果は、GA が時折$\Omega(\mu^2)$の反復数に対して単一の遺伝子型に支配されない集団を持つという証明に基づいている。 この研究において、この多様性は(二次の代わりに)$\mu$で指数関数的に高い確率で持続することを示した。 この集団の多様性をよりよく理解することで、より強力なランタイム保証を得ることができ、中でも、$c\ln(n)\le\mu \le n/\log n$ に対して、$c$ のとき、$(\mu+1)$ ga on $\mathrm{jump}_k$ のランタイムは $k \ge 3$ であり、$o(n^{k-1})$ となる。 その結果、既に対数的な人口規模を持つGAは、クロスオーバーからオーダー$\Omega(n)$のスピードアップを得る。

関連論文リスト

• Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem [10.506038775815094]
  我々は、小さなギャップの場合、$(mu+1)$EAが$O(mu2 m4 log(m))$の期待ランタイムで最大多様性を達成することを示す。 2P-EA_D$はより強力なパフォーマンスを示し、小さなギャップケースは$O(mu2 n2 log(m))$、パスは$O(mu3 m3)$である。
  論文  参考訳（メタデータ） (2024-04-17T22:20:02Z)
• A Tight $O(4^k/p_c)$ Runtime Bound for a ($μ$+1) GA on Jump$_k$ for Realistic Crossover Probabilities [1.8434042562191815]
  人口の多様性は、ほぼ完全な多様性の均衡に収束することを示す。 私たちの仕事は、20年以上開かれてきた問題を部分的に解決します。
  論文  参考訳（メタデータ） (2024-04-10T14:50:43Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• 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)
• 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)
• 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 Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• 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)

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

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