通过选择最远亲本加速遗传算法求解跳跃问题
Parent Selection Mechanisms in Elitist Crossover-Based Algorithms
- 优先选取距离最远的个体进行交叉，主动维持种群多样性
- 在合理种群规模下，求解Jump_k问题期望时间降至O(k4^kn log n)
- 适合关注遗传算法理论机制与交叉作用的研究者
亲本选择方法广泛用于进化计算以加速优化过程，但其理论优势仍不清晰。本文针对(μ+1)遗传算法提出一种新策略：优先选择最大距离的亲本进行交叉。我们证明，在适当选择种群规模时，该算法求解Jump_k问题的期望时间为O(k4^kn log n)，显著优于现有无显式多样性保持机制且交叉概率恒定的(μ+1)GA的最佳已知界O(nμ log μ + n log n + n^{k-1})。为实现此结果，我们引入一种新型多样性度量，同时捕捉种群中个体间最大距离及达到该距离的个体对数量。分析核心在于将交叉视为持续生成和维持多样性的机制，而非仅在最后一步组合已有多样化个体。该研究深化了对交叉在遗传算法种群动态中作用的理论理解。
原文摘要 · Abstract (English)
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 proposing a parent selection strategy for the $(μ+1)$ genetic algorithm (GA) that prioritizes the selection of maximally distant parents for crossover. We show that, with an appropriately chosen population size, 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 main novelty 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. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。