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

作     者：李香薏 谭代伦 Li Xiangyi;Tan Dailun

作者机构：西华师范大学数学与信息学院四川南充637000 

基　　金：教育部产学合作协同育人项目“基于超融合的产学合作师资培训”(202102454008) 四川省教育厅教改项目“教赛相融的优质本科课程数学建模的建设与实践”(JG2021-959) 

出 版 物：《六盘水师范学院学报》 (Journal of Liupanshui Normal University)

年 卷 期：2024年第36卷第3期

页      码：55-64页

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

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

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

D　O　I：10.16595/j.1671-055X.2024.03.007

馆 藏 号：203140230...