論文の概要: Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable Crossover Probability

• arxiv url: http://arxiv.org/abs/2006.05889v1
• Date: Wed, 10 Jun 2020 15:22:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-23 04:57:09.362362
• Title: Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable Crossover Probability
• Title（参考訳）: 構成可能なクロスオーバー確率を持つ$(\mu+\lambda)$遺伝的アルゴリズムのベンチマーク
• Authors: Furong Ye and Hao Wang and Carola Doerr and Thomas B\"ack
• Abstract要約: 我々は、突然変異またはランダムに選択された2人の親の再結合によって子孫を生成する、$(mu+lambda)$ Genetic Algorithms (GAs)の家系を調査する。 クロスオーバー確率を拡大することにより、完全突然変異のみのアルゴリズムから完全クロスオーバーベースGAへの補間が可能となる。
• 参考スコア（独自算出の注目度）: 4.33419118449588
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate a family of $(\mu+\lambda)$ Genetic Algorithms (GAs) which creates offspring either from mutation or by recombining two randomly chosen parents. By scaling the crossover probability, we can thus interpolate from a fully mutation-only algorithm towards a fully crossover-based GA. We analyze, by empirical means, how the performance depends on the interplay of population size and the crossover probability. Our comparison on 25 pseudo-Boolean optimization problems reveals an advantage of crossover-based configurations on several easy optimization tasks, whereas the picture for more complex optimization problems is rather mixed. Moreover, we observe that the ``fast'' mutation scheme with its are power-law distributed mutation strengths outperforms standard bit mutation on complex optimization tasks when it is combined with crossover, but performs worse in the absence of crossover. We then take a closer look at the surprisingly good performance of the crossover-based $(\mu+\lambda)$ GAs on the well-known LeadingOnes benchmark problem. We observe that the optimal crossover probability increases with increasing population size $\mu$. At the same time, it decreases with increasing problem dimension, indicating that the advantages of the crossover are not visible in the asymptotic view classically applied in runtime analysis. We therefore argue that a mathematical investigation for fixed dimensions might help us observe effects which are not visible when focusing exclusively on asymptotic performance bounds.
• Abstract（参考訳）: 遺伝的アルゴリズム (gas) は、突然変異またはランダムに選択された2つの親を組み換えることで子孫を発生させる。 クロスオーバー確率を拡大することにより、完全突然変異のみのアルゴリズムから完全クロスオーバーベースGAへの補間が可能となる。 実証的な方法により,人口規模と交叉確率の相互関係によってパフォーマンスがどう変わるかを分析する。 25個の疑似ボアリーン最適化問題の比較により,複数の簡単な最適化タスクにおけるクロスオーバーベースの構成の利点が明らかになった。 さらに, <fast'' 変異方式は, クロスオーバーと組み合わせた複雑な最適化タスクにおいて, 標準的なビット突然変異よりも優れるが, クロスオーバーの欠如によりさらに悪化する。 次に、よく知られたLeadingOnesベンチマーク問題に関して、クロスオーバーベースの$(\mu+\lambda)$ GAの驚くほど優れたパフォーマンスを詳しく見ていきます。 人口増加に伴い最適クロスオーバー確率が増加することが観測された。 同時に、問題次元の増大とともに減少し、古典的にランタイム分析に適用される漸近的観点では、クロスオーバーの利点が見えないことを示す。 したがって、固定次元に対する数学的調査は、漸近的な性能境界にのみ焦点をあてるときに目に見えない効果を観察するのに役立つと論じる。

関連論文リスト

• Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
  GOMEAは、リンク学習を利用して問題構造を効率的に活用する進化的アルゴリズムである。 GOMEAは確率の高い$O(m32k)$で解くことができ、$m$はサブファンクションの数、$k$はサブファンクションの長さである。 これは (1+1) 進化的 EA と比較して大きなスピードアップであり、これは$O(ln(m)(mk)k)$期待される評価を必要とする。
  論文  参考訳（メタデータ） (2024-07-11T09:37:21Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Dynastic Potential Crossover Operator [2.908482270923597]
  最適組換え作用素は、2つの親解を含む最小の超平面において最適である。 本稿では,Dynastic Potential Crossover (DPX) と呼ばれる組換え演算子を提案する。
  論文  参考訳（メタデータ） (2024-02-06T11:38:23Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。 本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
  論文  参考訳（メタデータ） (2023-12-19T01:52:13Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation [4.212663349859165]
  本稿では,よく知られたEMOアルゴリズムGSEMOとNSGA-IIの理論的解析を行う。 免疫刺激による過変異は指数的最適化時間を回避することはできない。
  論文  参考訳（メタデータ） (2023-01-31T15:03:34Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• A Rank based Adaptive Mutation in Genetic Algorithm [0.0]
  本稿では,染色体ランクを用いた突然変異確率生成の代替手法を提案する。 単純な遺伝的アルゴリズム(SGA)と一定の突然変異確率と限られた資源制約内での適応的アプローチとの比較実験を行った。
  論文  参考訳（メタデータ） (2021-04-18T12:41:33Z)
• 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)
• Fast Mutation in Crossover-based Algorithms [8.34061303235504]
  Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 実験的な研究は、ランダムに満足できるMax-3SATインスタンスにも高速突然変異の有効性を示す。
  論文  参考訳（メタデータ） (2020-04-14T14:16:42Z)

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

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