論文の概要: Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

• arxiv url: http://arxiv.org/abs/2604.04083v1
• Date: Sun, 05 Apr 2026 12:02:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-07 15:49:18.909669
• Title: Parent Selection Mechanisms in Elitist Crossover-Based Algorithms
• Title（参考訳）: 偏差クロスオーバーアルゴリズムにおける親選択機構
• Authors: Andre Opris, Denis Antipov,
• Abstract要約: そこで本研究では,集団内の個体同士の最大距離と,この距離を達成するペア数の両方をキャプチャする,新しい多様性指標を提案する。 本分析から得られた知見は,遺伝的アルゴリズムの集団動態におけるクロスオーバーの役割の理論的理解に寄与する。
• 参考スコア（独自算出の注目度）: 4.640835690336653
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Parent selection methods are widely used in evolutionary computation to accelerate the optimization process, yet their theoretical benefits are still poorly understood. In this paper, we address this gap by incorporating different parent selection strategies into the $(μ+1)$ genetic algorithm (GA). We show that, with an appropriately chosen population size and a parent selection strategy that selects a pair of maximally distant parents with probability $Ω(1)$ for crossover, the resulting algorithm solves the Jump$_k$ problem in $O(k4^kn\log(n))$ expected time. This bound is significantly smaller than the best known bound of $O(nμ\log(μ)+n\log(n)+n^{k-1})$ for any $(μ+1)$~GA using no explicit diversity-preserving mechanism and a constant crossover probability. To establish this result, we introduce a novel diversity metric that captures both the maximum distance between pairs of individuals in the population and the number of pairs achieving this distance. The crucial point of our analysis is that it relies on crossover as a mechanism for creating and maintaining diversity throughout the run, rather than using crossover only in the final step to combine already diversified individuals, as it has been done in many previous works. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.
• Abstract（参考訳）: 親選択法は、最適化過程を加速するために進化計算で広く用いられているが、その理論的利点はまだよく分かっていない。 本稿では,異なる親選択戦略を$(μ+1)$遺伝アルゴリズム(GA)に組み込むことで,このギャップに対処する。 このアルゴリズムは, 集団サイズが適切に選択され, 親選択戦略により, 1対の最大距離の親を1対の確率$Ω(1)$でクロスオーバーし, 1対の確率$O(k4^kn\log(n))$期待時間でJump$_k$問題を解く。 この境界は、任意の$(μ+1)$~GAに対して最もよく知られた$O(nμ\log(μ)+n\log(n)+n^{k-1})$よりも著しく小さい。 そこで本研究では,集団内の個体同士の最大距離と,この距離を達成するペア数の両方をキャプチャする,新しい多様性指標を提案する。 分析の重要なポイントは、クロスオーバーを、これまで多くの研究で行われてきたように、既に多様化した個人をまとめるために、最終段階にのみクロスオーバーを使用するのではなく、実行中の多様性を創造し維持するためのメカニズムとして、クロスオーバーに依存していることです。 本分析から得られた知見は,遺伝的アルゴリズムの集団動態におけるクロスオーバーの役割の理論的理解に寄与する。

関連論文リスト

• Diversity-Preserving Exploitation of Crossover [0.0]
  我々は,クロスオーバーの多様性保護利用(DiPEC)と呼ばれる,この対立を緩和するクロスオーバーを利用するための新しいパラダイムを導入する。 結果として得られる多様性爆発遺伝的アルゴリズム(DEGA)は、いまだにクロスオーバーの利点を活用できるが、従来のアプローチよりもはるかに多様性を保っている。
  論文  参考訳（メタデータ） (2025-07-02T09:28:06Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [14.309243378538014]
  OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。 確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。 また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
  論文  参考訳（メタデータ） (2020-12-14T03:07:39Z)
• Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable Crossover Probability [4.33419118449588]
  我々は、突然変異またはランダムに選択された2人の親の再結合によって子孫を生成する、$(mu+lambda)$ Genetic Algorithms (GAs)の家系を調査する。 クロスオーバー確率を拡大することにより、完全突然変異のみのアルゴリズムから完全クロスオーバーベースGAへの補間が可能となる。
  論文  参考訳（メタデータ） (2020-06-10T15:22:44Z)

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

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