一种多染色体遗传算法解决多旅行商问题

doi:10.16182/j.issn1004731x.joss.17-0046

系统仿真学报 ›› 2019, Vol. 31 ›› Issue (1): 36-42.doi: 10.16182/j.issn1004731x.joss.17-0046

一种多染色体遗传算法解决多旅行商问题

叶多福, 刘刚, 何兵

火箭军工程大学,陕西西安 710025

收稿日期:2017-01-10 修回日期:2017-05-04 出版日期:2019-01-08 发布日期:2019-04-16
作者简介:叶多福(1992-),男,安徽阜阳,硕士生,研究方向为多无人机协同任务规划;刘刚(1963-),男,安徽阜阳,博士,教授,研究方向为任务规划。
基金资助:
国家自然科学基金(61403399)

Multi-chromosome Genetic Algorithm for Multiple Traveling Salesman Problem

Ye Duofu, Liu Gang, He Bing

Rocket Force University of Engineering, Xi’an 710025, China

Received:2017-01-10 Revised:2017-05-04 Online:2019-01-08 Published:2019-04-16

摘要/Abstract

摘要： 建立带时间窗口的多旅行商问题模型,设计旅行商数量和旅行时间总和主次两个目标函数,设计一种多染色体编码的编码方式,开发复杂突变算子树进化操作,克服了传统遗传算法搜索空间大的问题。仿真比较了算法的性能,仿真结果表明带复杂突变树的多染色体遗传算法均衡了旅行商数量与旅行时间总和两个目标函数,提高了算法的运行速度,减少旅行时间总和15.8%。

关键词: 多旅行商问题, 时间窗口, 编码, 多染色体遗传算法, 突变算子树

Abstract: A multi-traveling salesman model with time window is established, and two objective functions for the number of traveling salesmen and the sum of travel time are designed. A multi - chromosome coding method is designed to develop complex mutation operator tree, which overcomes the problem of large searching space of traditional genetic algorithms. The performances of algorithms are compared by simulation, and the simulation results show that the genetic algorithm with complex multi-chromosome mutation tree can balance the two objective functions of the number of TSP and total travel time well, improve the algorithm of travel speed, and reduce the total travel time by 15.8%.

Key words: multi-traveling salesman problem, time window, coding, multi-chromosome genetic algorithm, mutation operator tree

中图分类号:

TP18

叶多福, 刘刚, 何兵. 一种多染色体遗传算法解决多旅行商问题[J]. 系统仿真学报, 2019, 31(1): 36-42.

Ye Duofu, Liu Gang, He Bing. Multi-chromosome Genetic Algorithm for Multiple Traveling Salesman Problem[J]. Journal of System Simulation, 2019, 31(1): 36-42.

参考文献

[1] 王勇臻, 陈燕, 于莹莹. 求解多旅行商问题的改进分组遗传算法[J]. 电子与信息学报, 2017, 39(1):198-205. doi: 10.11999/JEIT160211.
Wang Y Z, Chen Y, Yu Y Y.Improved Grouping Genetic Algorithm for Solving Multiple Traveling Salesman Problem[J]. Journal of Electronics & Information Technology, 2017, 39(1): 198-205. doi:10.11999/ JEIT160211.
[2] KASHAN A H, AKBARI A A, OSTADI B.Grouping Evolution Strategies: an Effective Approach for Grouping Problems[J]. Applied Mathematical Modelling (S0307-904X), 2015, 39(9): 2703-2720. doi: 10.1016/ j.apm.2014.11.001.
[3] BEKTAS T.The Multiple Traveling Salesman Problem: an Overview of Formulations and Solution Procedures[J]. Omega (S0305-0483), 2006, 34(3): 209-219. doi: 10.1016/j.omega.2004.10.004.
[4] SINGH A, BAGHEL A S.A New Grouping Genetic Algorithm Approach to the Multiple Traveling Salesperson Problem[J]. Soft Computing (S1432-7643), 2009, 13(1): 95-101. doi: 10.1007/s00500-008-0312-1.
[5] 于宏涛, 高立群, 田卫华. 求解TSP的离散人工蚁群算法[J]. 东北大学学报(自然科学版), 2015, 36(8): 1074-1079. doi: 10.3969/j.issn.1005-3026.2015.08.003.
Yu H.T, Gao L. Q and Tian W. H, Discrete Artificial Bee Colony Algorithm for TSP[J], Journal of Northeastern University (Natural Science), 2015, 36(8): 1074-1079. doi: 10.3969/j.issn.1005-3026.2015.08.003.
[6] 贾燕花. 蚁群算法在旅行商问题(TSP)中的应用研究[J]. 计算机与数字工程, 2016, 44(9): 1664-1667.
Jia Yanhua.Application of the Ant Algorithm in TSP[J]. Computer and Digital Engineering, 2016, 44(9): 1664-1667.
[7] Tang L, Liu J, Rong A, et al.A Multiple Traveling Salesman Problem Model for Hot Rolling Scheduling in Shangai Baoshan Iron & Steel Complex[J]. European Journal of Operational Research (S0377-2217), 2000, 124(2): 267-282.
[8] Zhao F, Dong J, Li S, et al.An Improved Genetic Algorithm for the Multiple Traveling Salesman Problem[C]// Chinese Control and Decision Conference. Yantai, China: IEEE Press, 2008: 1935-1939.
[9] Koh S P, Aris I B, Ho C K, et al.Design and Performance Optimization of a Multi-TSP (Traveling Salesman Problem) Algorithm[J]. AIML Journal (S1687-4846), 2006, 6(3): 29-33.
[10] 刘明, 张培勇. 求解多旅行商问题的新混合遗传算法: 以应急物资配送为例[J]. 系统管理学报, 2014, 23(2): 247-254.
Liu M, Zhang P Y.New hybrid Genetic Algorithm for Solving the Multiple Traveling Salesman Problem: an Example of Distribution Emergence Materials[J]. Systems Engineering Theory Methodology Applications, 2014, 23(2): 247-254.
[11] SINGH A, BAGHEL A S.A New Grouping Genetic Algorithm Approach to the Multiple Traveling Salesperson Problem[J]. Soft Computing (S1432-7643), 2009, 13(1): 95-101.
[12] Kara I, Bektas T.Integer Linear Progra1ng Formulations of Multiple Salesman Problems and its Variations[J]. European Journal of Operational Research (S0377-2217), 2006, 174(3): 1449-1458.
[13] Andras K, Janos A.Redesign of the Supply of Mobile Mechanics based on a novel Genetic Optimization Algorithm using Google Maps API[J]. Engineering Applications of Artificial Intelligence (S0952-1976), 2015, 38(2): 122-130.

[1]	聂凯, 曾科军, 孟庆海. 基于深度贝叶斯网络学习的不确定性建模方法[J]. 系统仿真学报, 2022, 34(1): 79-85.
[2]	秦婉亭, 老松杨, 汤俊, 卢聪. 基于变分自编码器的飓风轨迹异常检测方法[J]. 系统仿真学报, 2021, 33(9): 2191-2201.
[3]	唐婕, 曹瑾鑫. 共享汽车联合调度优化研究[J]. 系统仿真学报, 2021, 33(8): 1959-1968.
[4]	林硕, 安磊, 高治军, 单丹, 尚文利. 结合栈式自编码及长短时记忆的入侵检测研究[J]. 系统仿真学报, 2021, 33(6): 1288-1296.
[5]	吴定会, 祝志超, 韩欣宏. 基于BO-SDAE多源信号的风电机组轴承故障诊断[J]. 系统仿真学报, 2021, 33(5): 1148-1156.
[6]	董书琴, 张斌. 面向不平衡数据的网络流量异常检测方法[J]. 系统仿真学报, 2021, 33(3): 679-689.
[7]	陆嘉波, 程培星, 黄羿, 姚进强, 杨雪梦, 马新强, 刘勇. 用于时敏目标打击链快速构建的智能方法[J]. 系统仿真学报, 2021, 33(2): 346-357.
[8]	郭业才, 张浩然. 基于改进LDA和自编码器的调制识别算法[J]. 系统仿真学报, 2021, 33(2): 494-500.
[9]	刘长良, 王梓齐. 基于严格二叉树编码和GA的模糊树结构学习[J]. 系统仿真学报, 2020, 32(8): 1473-1480.
[10]	轩华, 秦莹莹, 王薛苑, 张百林. 带恶化工件的不相关并行机调度优化[J]. 系统仿真学报, 2019, 31(5): 919-924.
[11]	李炜, 葛振福, 申富媛, 龚建兴. 基于FDRE的3D威亚编码器故障检测与容错控制[J]. 系统仿真学报, 2019, 31(4): 740-749.
[12]	陈发堂, 杨康, 付永莉, 李孟杰. 预编码辅助广义正交空间调制的低复杂度检测[J]. 系统仿真学报, 2019, 31(10): 2078-2084.
[13]	刘芳, 路丽霞, 王洪娟, 王鑫. 基于稀疏自动编码器和支持向量机的图像分类[J]. 系统仿真学报, 2018, 30(8): 3007-3014.
[14]	李珂, 王艳, 纪志成. 基于混合策略的入侵杂草算法的FJSP问题研究[J]. 系统仿真学报, 2018, 30(5): 1918-1926.
[15]	郭圣明, 贺筱媛, 吴琳, 胡晓峰. 基于强制稀疏自编码神经网络的作战态势评估方法研究[J]. 系统仿真学报, 2018, 30(3): 772-785.

一种多染色体遗传算法解决多旅行商问题

Multi-chromosome Genetic Algorithm for Multiple Traveling Salesman Problem

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价