四点三线遗传算法求解旅行商问题

doi:10.3778/j.issn.1002-8331.1701-0249

计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (14): 148-154.DOI: 10.3778/j.issn.1002-8331.1701-0249

四点三线遗传算法求解旅行商问题

郑明1，2，3，卓慕瑰1，2

1.梧州学院广西高校行业软件技术重点实验室，广西梧州 543002
2.梧州学院信息与电子工程学院，广西梧州 543002
3.吉林大学计算机科学与技术学院，长春 130012

出版日期:2017-07-15 发布日期:2017-08-01

Solution for traveling salesman problem with four vertices and three lines genetic algorithm

ZHENG Ming1，2，3, ZHUO Mugui1，2

1.Guangxi Colleges and Universities Key Laboratory of Professional Software Technology, Wuzhou University, Wuzhou, Guangxi 543002, China
2.College of Information and Electronic Engineering, Wuzhou University, Wuzhou, Guangxi 543002, China
3.College of Computer Science and Technology, Jilin University, Changchun 130012, China

Online:2017-07-15 Published:2017-08-01

摘要/Abstract

摘要： 为解决NP完全的旅行商问题，提出一种四点三线遗传算法。该算法特色在两阶段策略，第一阶段是变异算子优化，将汉密尔顿环中所有大于两点的内部路径倒置，并用新极值代替原极值。第二阶段是四点三线优化，将汉密尔顿环分为n个四点三线局部路径并将每个局部路径转化为最优局部路径，将所有局部路径长度求和除以1/3。交叉算子结束后，如子代含有重复位点，将未交叉部分重复位点与交叉部分重复位点对应的父代等位点交换。通过将该算法与传统遗传算法及只进行第一步优化的遗传算法进行比较，采用TSPLIB数据库实例数据，证明该算法有更高的执行效率，有更强的收敛性，适合寻找最短TSP路径。

关键词: 遗传算法, 旅行商问题, 两阶段策略, 四点三线

Abstract: A Four Vertices and Three Lines Genetic Algorithm （4V3LGA） is proposed to resolve the traveling salesman problem, which is proven to be NP-complete. The special part of the proposed algorithm is two-phase strategies. The first local optimization strategy is the mutation operator, which is executed to reverse every Local Hamiltonian Path （LHP）. Every LHP contains more than 2 vertices and generates the shorter Hamiltonian Cycles （HC）. The second local optimization is HC segmentation, which is executed to divide HC to n four vertices and three lines LHPs to generate the shorter HC. The sum of the LHPs is divided by 1/3. After crossover, if the positions in offspring HCs are the same, the duplicated positions of un-exchanged part are exchanged with the same positions of the father HCs of exchanged part. To prove the efficiency of the 4V3LGA proposed, traditional GA and first-phase GA are used to compare with the proposed algorithm. TSPLIB instances are used in the experiments. The computation results show that the proposed algorithm can find the better approximate solutions than other two algorithms. It can be used to find shorter TSP HC.

Key words: genetic algorithm, traveling salesman problem, two-phase strategies, four vertices and three lines

郑明1，2，3，卓慕瑰1，2. 四点三线遗传算法求解旅行商问题[J]. 计算机工程与应用, 2017, 53(14): 148-154.

ZHENG Ming1，2，3, ZHUO Mugui1，2. Solution for traveling salesman problem with four vertices and three lines genetic algorithm[J]. Computer Engineering and Applications, 2017, 53(14): 148-154.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	李昱奇，刘志乾，程凝怡，王莹莹，朱春丽. 多约束条件下无人机航迹规划[J]. 计算机工程与应用, 2021, 57(4): 225-230.
[4]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[5]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[6]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[7]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[8]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[9]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[10]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[11]	姜良重，雷航，李贞昊，钱伟中，施甘图. 采用自适应优化权重的出库货位优化方法研究[J]. 计算机工程与应用, 2021, 57(15): 271-278.
[12]	贺娇，谭代伦. 基于视野范围和遗传算法的三维地形路径规划[J]. 计算机工程与应用, 2021, 57(15): 279-285.
[13]	冯晓东，黄世荣，戴冠鸥，杨伟家，罗尧治. 天牛须遗传杂交算法的研究与应用[J]. 计算机工程与应用, 2021, 57(15): 90-100.
[14]	苏庆，林华智，黄剑锋，林志毅. 结合CNN和Catboost算法的恶意安卓应用检测模型[J]. 计算机工程与应用, 2021, 57(15): 140-146.
[15]	王秀丽，周鹏，侯静楠，王仕俊，林霞. 面向变电站机器人巡检路径规划中的算法研究[J]. 计算机工程与应用, 2021, 57(14): 245-250.

四点三线遗传算法求解旅行商问题

Solution for traveling salesman problem with four vertices and three lines genetic algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics