論文の概要: Fast Mutation in Crossover-based Algorithms

• arxiv url: http://arxiv.org/abs/2004.06538v4
• Date: Tue, 1 Mar 2022 11:42:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 09:16:05.757547
• Title: Fast Mutation in Crossover-based Algorithms
• Title（参考訳）: クロスオーバーに基づくアルゴリズムの高速突然変異
• Authors: Denis Antipov, Maxim Buzdalov, Benjamin Doerr
• Abstract要約: Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 実験的な研究は、ランダムに満足できるMax-3SATインスタンスにも高速突然変異の有効性を示す。
• 参考スコア（独自算出の注目度）: 8.34061303235504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The heavy-tailed mutation operator proposed in Doerr, Le, Makhmara, and Nguyen (GECCO 2017), called \emph{fast mutation} to agree with the previously used language, so far was proven to be advantageous only in mutation-based algorithms. There, it can relieve the algorithm designer from finding the optimal mutation rate and nevertheless obtain a performance close to the one that the optimal mutation rate gives. In this first runtime analysis of a crossover-based algorithm using a heavy-tailed choice of the mutation rate, we show an even stronger impact. For the $(1+(\lambda,\lambda))$ genetic algorithm optimizing the OneMax benchmark function, we show that with a heavy-tailed mutation rate a linear runtime can be achieved. This is asymptotically faster than what can be obtained with any static mutation rate, and is asymptotically equivalent to the runtime of the self-adjusting version of the parameters choice of the $(1+(\lambda,\lambda))$ genetic algorithm. This result is complemented by an empirical study which shows the effectiveness of the fast mutation also on random satisfiable Max-3SAT instances.
• Abstract（参考訳）: Doerr, Le, Makhmara, and Nguyen (GECCO 2017) で提案された重尾突然変異演算子は、以前に使用されていた言語と一致するために 'emph{fast mutation} と呼んだ。 これにより、アルゴリズムデザイナが最適な突然変異率を見つけることを緩和でき、なおかつ、最適な突然変異率を与えるものに近い性能が得られる。 変異率の重み付き選択を用いたクロスオーバーに基づくアルゴリズムの最初の実行時解析では、さらに強い影響を示す。 1maxベンチマーク関数を最適化する1+(\lambda,\lambda)$の遺伝的アルゴリズムについて、重み付き突然変異率で線形ランタイムを実現できることを示す。 これは静的な突然変異率で得られるものよりも漸近的に高速であり、パラメータの自己調整バージョンのランタイムと漸近的に等価であり、$(1+(\lambda,\lambda))$の遺伝的アルゴリズムの選択である。 この結果は、ランダムに満足できるMax-3SATインスタンスでも高速突然変異の有効性を示す実証的研究によって補完される。

関連論文リスト

• A Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive [2.07180164747172]
  我々は、$k$-bitのフリップ突然変異を用いた進化的アルゴリズムの突然変異率を動的に維持する新しいフレキシブルなアプローチを提案する。 試行錯誤の回数がしきい値を超えた場合のレートは終了し、現在アーカイブに存在しないレートは2つの方法で入力できる。 最小選択確率について、重み付き分布を含む様々な選択肢を提案する。
  論文  参考訳（メタデータ） (2024-04-05T10:51:40Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• A Rank based Adaptive Mutation in Genetic Algorithm [0.0]
  本稿では,染色体ランクを用いた突然変異確率生成の代替手法を提案する。 単純な遺伝的アルゴリズム(SGA)と一定の突然変異確率と限られた資源制約内での適応的アプローチとの比較実験を行った。
  論文  参考訳（メタデータ） (2021-04-18T12:41:33Z)
• Optimal Static Mutation Strength Distributions for the $(1+\lambda)$ Evolutionary Algorithm on OneMax [1.0965065178451106]
  人口が十分に大きくなると、このような最適な分布は驚くほど複雑で直感に反する可能性がある。 人口が十分に大きくなると、このような最適な分布は驚くほど複雑で直感に反する可能性がある。
  論文  参考訳（メタデータ） (2021-02-09T16:56:25Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable Crossover Probability [4.33419118449588]
  我々は、突然変異またはランダムに選択された2人の親の再結合によって子孫を生成する、$(mu+lambda)$ Genetic Algorithms (GAs)の家系を調査する。 クロスオーバー確率を拡大することにより、完全突然変異のみのアルゴリズムから完全クロスオーバーベースGAへの補間が可能となる。
  論文  参考訳（メタデータ） (2020-06-10T15:22:44Z)
• The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
  我々は、$(lambda,lambda)$の遺伝的アルゴリズムが、$O(n2)$のフィットネスクエリで最適であることを示す。 また,Hamと呼ばれる置換に基づく問題に対して,このアルゴリズムの最初の解析を行った。
  論文  参考訳（メタデータ） (2020-04-18T17:04:57Z)

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

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