基于组合变异和分组优化的单亲遗传算法求解旅行商问题  

Partheno-Genetic Algorithm based on Combined Mutation and Grouped Optimization for Solving Traveling Salesman Problem

作　　者：周琴[1] 谭代伦[1] Zhou Qin;Tan Dailun(School of Mathematics and Information,China West Normal University,Nanchong 637009,China)

机构地区：[1]西华师范大学数学与信息学院,四川南充637009

出　　处：《六盘水师范学院学报》2024年第3期45-54,共10页Journal of Liupanshui Normal University

基　　金：四川省科技计划项目资助“基于车载视频图像的铁路轨道异物侵限检测关键技术研究”(2019YFG0299);教育部产学合作协同育人项目“基于超融合的产学合作师资培训”(202102454008);四川省教育厅重点教改项目“教赛相融的优质本科课程数学建模的建设与实践”(JG2021-959)。

摘　　要：针对遗传算法求解旅行商问题存在收敛速度慢、容易陷入局部最优等问题,提出了基于组合变异和分组优化的单亲遗传算法。算法设计了由双侧倒序、近邻交换、跳跃基因构成的组合变异算子,用于扩大搜索范围,增强种群的多样性;经过精英优选后,将种群按适应度优劣分为两组作局部优化,对优质互异组依次采用插入和2opt算子,加快进化收敛速度;对普通组用倒序算子,增强其跳出局部最优的能力。仿真实验表明,对于中小型规模的旅行商问题,该算法在收敛速度和求解能力上得到明显改善和增强。Aiming at the problems of slow convergence speed and falling easily into local optimum in solving Traveling Salesman Problem,Partheno-Genetic Algorithm based on Combined Mutation and Grouped Optimization is proposed.Combined mutation is designed to be composed of two-sided reverse order,nearest neighbor exchange and jumping gene,which is used to expand the search range and enhance the diversity of population.After elite selection,the populations are divided into two groups according to their fitness for local optimization,and insertion and 2opt are used successively for the high-quality and different group to accelerate the evolutionary convergence speed.The reverse order operator is used for the ordinary group to enhance its ability to jump out of the local optimum.Experiments show that the proposed algorithm has significantly improved in convergence speed and solving ability for small and medium-sized traveling salesman problem.

关 键 词：旅行商问题 单亲遗传算法 组合变异策略 精英优选 分组局部优化策略 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]