基于策略池-扩张机制的改进遗传算法求解旅行商问题

摘要：

针对传统遗传算法(GA)在求解旅行商问题(TSP)时,因种群多样性丢失、局部搜索能力减弱导致算法寻优效率低、易早熟等问题,提出了一种基于策略池-扩张机制的改进遗传算法(SPEM-IGA).根据不同目的设计了两组策略池,为增强解的搜索深度,构造由2-opt、启发式插入、贪婪算子组成的局部搜索策略池;为扩大解的搜索范围,再将近邻插入、翻转、片段交换、循环左移算子组成全局搜索策略池.根据种群多样性水平,设计了基于策略池的随机选择机制,并使种群动态扩张,能有效改善种群的多样性,平衡算法的全局与局部搜索能力.通过精英优选保留种群中的优质个体,以加快算法收敛速度.仿真实验表明,与现有文献相比,基于策略池-扩张机制的改进遗传算法具有更好的求解精度和稳定性.

关键词：旅行商问题、改进遗传算法、策略池、扩张机制、精英优选

所属期刊栏目：36

分类号：TP391(计算技术、计算机技术)

资助基金：教育部卓越工程师教育培养计划项目产学合作协同育人项目;四川省教育厅教改项目

在线出版日期：2024-09-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：55-64