新染色体模式让遗传算法更快找到最优解
Genetic Algorithm with Innovative Chromosome Patterns in the Breeding Process
- 引入新型染色体模式提升搜索多样性
- 复杂调度问题下性能提升8倍，收敛速度达10倍
- 适合大规模组合优化问题，尤其擅长处理千比特级数据
本文提出一种改进的遗传算法GAB（Genetic Algorithm with Border Trades），通过在繁殖过程中引入创新染色体模式，显著增强探索能力，有效缓解早熟收敛问题并提高搜索多样性。实验表明，在复杂作业调度问题上，GAB相比标准遗传算法，最高可实现8倍的适应度提升和10倍的收敛速度提升，20秒内平均适应度达888，而标准算法仅106。在经典的Flip-Flop问题中，即使输入规模扩展至数千比特，GAB仍能在更少代数内稳定找到最优或近优解。结果表明，GAB是求解大规模组合优化问题的一种高效且计算高效的替代方案。
原文摘要 · Abstract (English)
This paper proposes Genetic Algorithm with Border Trades (GAB), a novel modification of the standard genetic algorithm that enhances exploration by incorporating new chromosome patterns in the breeding process. This approach significantly mitigates premature convergence and improves search diversity. Empirically, GAB achieves up to 8x higher fitness and 10x faster convergence on complex job scheduling problems compared to standard Genetic Algorithms, reaching average fitness scores of 888 versus 106 in under 20 seconds. On the classic Flip-Flop problem, GAB consistently finds optimal or near-optimal solutions in fewer generations, even as input sizes scale to thousands of bits. These results highlight GAB as a highly effective and computationally efficient alternative for solving large-scale combinatorial optimization problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。