六盘水师范学院学报2024，Vol.36Issue(3)：55-64,10.DOI:10.16595/j.1671-055X.2024.03.007
基于策略池-扩张机制的改进遗传算法求解旅行商问题
On the Improved Genetic Algorithm Based on the Strategy Pool and Expansion Mechanism for Solving Traveling Salesman Problem
摘要
Abstract
Addressing the issues of low optimization efficiency and premature convergence encountered by the traditional ge-netic algorithm(GA)in solving the Traveling Salesman Problem(TSP),which are caused by the loss of population diversity and weakened local search capabilities,an improved genetic algorithm based on the strategy pool and expansion mechanism(SPEM-IGA)is proposed.Two sets of strategy pools are designed for different purposes.A local search strategy pool,consisting of 2-opt,heuristic insertion,and greedy operator,is constructed to enhance the search depth of solutions.To broaden the search scope of solutions,a global search strategy pool is formed by combining operators such as the nearest neighbor insertion,flip,seg-ment exchange,and circular left shift.Considering the level of population diversity,a random selection mechanism is designed based on the strategy pool,which dynamically expands the population,effectively improves its diversity and balances its capability for both global and local search.Superior individuals in the population are retained through elite selection to accelerate the conver-gence speed of the algorithm.Simulation experiments show that the improved genetic algorithm based on the strategy pool and ex-pansion mechanism has better solution accuracy and stability compared to the existing literature.关键词
旅行商问题/改进遗传算法/策略池/扩张机制/精英优选Key words
Traveling Salesman Problem/Improved Genetic Algorithm/The Strategy Pool/Expansion Mechanism/Elite Selec-tion分类
信息技术与安全科学引用本文复制引用
李香薏,谭代伦..基于策略池-扩张机制的改进遗传算法求解旅行商问题[J].六盘水师范学院学报,2024,36(3):55-64,10.基金项目
教育部产学合作协同育人项目"基于超融合的产学合作师资培训"(202102454008) （202102454008）
四川省教育厅教改项目"教赛相融的优质本科课程数学建模的建设与实践"(JG2021-959). （JG2021-959）
