論文の概要: From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm

• arxiv url: http://arxiv.org/abs/2004.07141v3
• Date: Wed, 9 Jun 2021 07:16:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 02:47:35.018817
• Title: From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
• Title（参考訳）: 遺伝的ドリフトの理解からスマートリスタートパラメータレスコンパクト遺伝的アルゴリズムへ
• Authors: Benjamin Doerr and Weijie Zheng
• Abstract要約: 遺伝的なドリフトのない体制では、実行期間は人口規模にほぼ比例する。 本稿では,遺伝的アルゴリズムのパラメータレスバージョンを提案する。
• 参考スコア（独自算出の注目度）: 15.56430085052365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the key difficulties in using estimation-of-distribution algorithms is choosing the population size(s) appropriately: Too small values lead to genetic drift, which can cause enormous difficulties. In the regime with no genetic drift, however, often the runtime is roughly proportional to the population size, which renders large population sizes inefficient. Based on a recent quantitative analysis which population sizes lead to genetic drift, we propose a parameter-less version of the compact genetic algorithm that automatically finds a suitable population size without spending too much time in situations unfavorable due to genetic drift. We prove a mathematical runtime guarantee for this algorithm and conduct an extensive experimental analysis on four classic benchmark problems both without and with additive centered Gaussian posterior noise. The former shows that under a natural assumption, our algorithm has a performance very similar to the one obtainable from the best problem-specific population size. The latter confirms that missing the right population size in the original cGA can be detrimental and that previous theory-based suggestions for the population size can be far away from the right values; it also shows that our algorithm as well as a previously proposed parameter-less variant of the cGA based on parallel runs avoid such pitfalls. Comparing the two parameter-less approaches, ours profits from its ability to abort runs which are likely to be stuck in a genetic drift situation.
• Abstract（参考訳）: 分布推定アルゴリズムを使用する際の重要な難しさの1つは、集団サイズを適切に選択することである。 しかし、遺伝的ドリフトのないシステムでは、ランタイムは人口サイズにほぼ比例しており、大きな人口サイズは非効率である。 近年, 遺伝的ドリフトにつながる個体群の大きさを定量的に分析し, 遺伝的ドリフトによる好ましくない状況に過度に時間を費やすことなく, 適切な個体群サイズを自動的に検出するコンパクト遺伝的アルゴリズムを提案する。 我々は,このアルゴリズムの数学的ランタイム保証を証明し,ガウス後部雑音を加法的に伴わない4つの古典的ベンチマーク問題を広範囲に実験的に解析する。 前者は,本アルゴリズムが自然仮定の下では,最も問題固有の集団サイズから得られるものと非常によく似た性能を有することを示す。 後者は、元のcGAに適切な集団サイズが欠落することは有害であり、それ以前の理論に基づく集団サイズの提案は、適切な値から遠ざかる可能性があることを確認し、また、我々のアルゴリズムは、並列に基づくcGAのパラメータレス変種と同様に、そのような落とし穴を回避していることを示す。 この2つのパラメータレスアプローチを比較すると、遺伝子ドリフト状態にある可能性のあるランを中止する能力から利益が得られます。

関連論文リスト

• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。 特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
  論文  参考訳（メタデータ） (2024-02-01T09:18:34Z)
• Improving genetic algorithms performance via deterministic population shrinkage [9.334663477968027]
  本稿では,遺伝的アルゴリズム(GA)の性能に対する簡易変数集団サイズ法の適用可能性に関する実証的研究について述べる。 それは、所定のスケジュールに従ってGAランの人口を減少させ、速度と重大度パラメータによって構成する。 その結果,SVPS-GAは性能を向上しながら解の質を保ちつつ,性能向上に要する評価回数を削減し,速度重大性の組合せを示した。
  論文  参考訳（メタデータ） (2024-01-22T17:05:16Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms [16.904475483445452]
  我々は,分布推定アルゴリズム(EDAs)のためのスマートリスタート機構を開発する。 遺伝的ドリフトのリスクが高い場合、実行を停止することで、適切なパラメーター条件下でEDAを自動的に実行します。 スマートリスタート機構は,文献で示唆されるものよりも,集団サイズに対してはるかに優れた値を見出すことを示す。
  論文  参考訳（メタデータ） (2022-06-18T02:46:52Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  そこで本研究では,次元に明示的な有界な有限次元設定に最適化を移動させることができる次元削減法を開発した。 この問題を進展させるため、比較的大きな損失関数、すなわちブレグマンの発散によって引き起こされるベイズ的リスクに限定する。
  論文  参考訳（メタデータ） (2022-02-23T16:22:28Z)
• The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis [9.853329403413701]
  陰性な発見はUMDAのパラメータの不運な選択によって引き起こされることを示す。 この結果から,UMDAは進化的アルゴリズムよりも局所最適に対処できることが示唆された。
  論文  参考訳（メタデータ） (2020-07-16T12:07:09Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift [9.853329403413701]
  乗法的ドリフトシナリオに対する単純な負のドリフト定理は既存の解析を単純化できることを示す。 我々は、非エリート変異に基づく進化アルゴリズムのランタイムにおける下位境界を証明するための最も一般的なツールの1つである集団法において、Lehre's emph negative drift in populations法(PPSN 2010)についてより詳細に論じる。
  論文  参考訳（メタデータ） (2020-05-02T15:10:09Z)
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes [9.853329403413701]
  単変量分布アルゴリズム(UMDA)における実行時間保証の強化を実証する。 より少ない選択率によるランタイムゲインを示す。 同様の仮定の下では、我々の上界と定数因子に一致する境界が高い確率で成り立つことを証明している。
  論文  参考訳（メタデータ） (2020-04-10T10:20:05Z)

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

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