論文の概要: The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis

• arxiv url: http://arxiv.org/abs/2007.08277v2
• Date: Fri, 27 Nov 2020 09:19:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-09 22:41:50.788934
• Title: The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis
• Title（参考訳）: 単変量行列分布アルゴリズムは, 誤認と転移をよく表す
• Authors: Benjamin Doerr and Martin S. Krejca
• Abstract要約: 陰性な発見はUMDAのパラメータの不運な選択によって引き起こされることを示す。 この結果から,UMDAは進化的アルゴリズムよりも局所最適に対処できることが示唆された。
• 参考スコア（独自算出の注目度）: 9.853329403413701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceptiveLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most $\lambda(\frac{n}{2} + 2 e \ln n)$ fitness evaluations. Since an offspring population size $\lambda$ of order $n \log n$ can prevent genetic drift, the UMDA can solve the DLB problem with $O(n^2 \log n)$ fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than $O(n^3)$ is known (which we prove to be tight for the ${(1+1)}$ EA), so our result rather suggests that the UMDA can cope well with deception and epistatis. From a broader perspective, our result shows that the UMDA can cope better with local optima than evolutionary algorithms; such a result was previously known only for the compact genetic algorithm. Together with the lower bound of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
• Abstract（参考訳）: 最近の研究で、Lehre and Nguyen (FOGA 2019) は、認知学習ブロック(DLB)問題を最適化するために、一変量境界分布アルゴリズム (UMDA) が親集団サイズで指数関数的な時間を必要とすることを示した。 彼らはこの結果から、単変量EDAは偽りやてんかんに苦慮していると結論づけた。 本研究では,この否定的な発見は,UMDAのパラメータを不運に選択することに起因することを示す。 集団の大きさが遺伝的ドリフトを防げるほど大きく選択されると、umdaは最大$\lambda(\frac{n}{2} + 2 e \ln n)$の適合評価で高い確率でdlb問題を最適化する。 子孫サイズの$\lambda$ of order $n \log n$は遺伝的ドリフトを防ぐことができるので、UMDAは$O(n^2 \log n)$フィットネス評価でDLB問題を解決することができる。 対照的に、従来の進化的アルゴリズムでは、$o(n^3)$ よりも実行時間が保証されない(${(1+1)$ ea には厳密であることが証明されている)ため、umda は欺きとエピスタティスに対処できることを示唆している。 より広い視点から見れば、UMDAは進化的アルゴリズムよりも局所最適に対処できることが示され、この結果は以前、コンパクトな遺伝的アルゴリズムでのみ知られていた。 Lehre と Nguyen の下位境界とともに、私たちの結果は、遺伝的ドリフトによる政権での EDA の実行が、劇的なパフォーマンス損失をもたらすことを厳格に証明した。

関連論文リスト

• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables [10.165640083594573]
  我々は、遺伝的ドリフトの既知の定量的解析を、多値変数の分布推定アルゴリズムに拡張する。 我々の研究は、バイナリEDAの理解が自然に多値設定にまで拡張されていることを示している。
  論文  参考訳（メタデータ） (2023-02-28T08:52:40Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms [16.904475483445452]
  我々は,分布推定アルゴリズム(EDAs)のためのスマートリスタート機構を開発する。 遺伝的ドリフトのリスクが高い場合、実行を停止することで、適切なパラメーター条件下でEDAを自動的に実行します。 スマートリスタート機構は,文献で示唆されるものよりも,集団サイズに対してはるかに優れた値を見出すことを示す。
  論文  参考訳（メタデータ） (2022-06-18T02:46:52Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
  論文  参考訳（メタデータ） (2022-05-23T17:59:18Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [15.56430085052365]
  OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。 確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。 また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
  論文  参考訳（メタデータ） (2020-12-14T03:07:39Z)
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm [15.56430085052365]
  遺伝的なドリフトのない体制では、実行期間は人口規模にほぼ比例する。 本稿では,遺伝的アルゴリズムのパラメータレスバージョンを提案する。
  論文  参考訳（メタデータ） (2020-04-15T15:12:01Z)
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes [9.853329403413701]
  単変量分布アルゴリズム(UMDA)における実行時間保証の強化を実証する。 より少ない選択率によるランタイムゲインを示す。 同様の仮定の下では、我々の上界と定数因子に一致する境界が高い確率で成り立つことを証明している。
  論文  参考訳（メタデータ） (2020-04-10T10:20:05Z)

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

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