一种求解TSP问题的改进遗传算法

• 作者: 刘瑞敏 朱阳光 王枭 王震
• 来源期刊: 电子测量技术
• 学科: 工学
• 关键词: TSP问题 遗传算法 距离矩阵方差最小法 双向三交叉算子 2-opt优化
• 年，卷（期）: 2019,（23）
• 所属期刊栏目: 理论与算法
• 页码范围: 91-96
• 页数: 6页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19651/j.cnki.emt.1903077

摘要

旅行商问题(traveling salesman problem,TSP)是一个易于描述但难于解决的著名难题之一.利用距离矩阵方差最小法(minimizing variance of distance matrix,MVODM)改进的贪婪算法得到遗传算法的初始种群;结合具有贪婪算法和淘汰机制的启发交叉算子引入双向三交叉的贪婪算子,对选择的父代进行充分交叉以提高种群多样性;变异算子采用2-opt局部优化算法,对基因进行改造,使变异子代向更优的方向进化.最后加入精英个体保留策略,使得最优基因结构得以延续.实验表明,该改进遗传算法在高质量的初始种群下进行充分的交叉,可以在较小的迭代次数内以及较小的种群数量下得到质量更高的全局最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王震		12	59	4.0	7.0
2	刘瑞敏		25	32	3.0	5.0
3	王枭		11	18	2.0	4.0
4	朱阳光		5	1	1.0	1.0