一种求解TSP的生物信息启发式遗传算法

doi:10.16182/j.issn1004731x.joss.21-0203

摘要/Abstract

摘要：

遗传算法是解决旅行商问题（traveling salesman problem，TSP）的通用路径优化算法之一。为解决传统遗传算法收敛速度慢且解不稳定的问题，提出一种生物信息启发式遗传算法（bioinformation heuristic genetic algorithm，BHGA）。通过优化适应度函数和初始种群，引入生物信息学中的基因序列对比手法进行交叉重组排序，采用基因逆转操作进行变异，对遗传算法进行改进，使算法能够加快收敛速度，得到更优路径解。利用BHGA对TSPLIB数据库中算例进行求解，实验仿真结果表明：该算法在中小型规模的TSP中求解效果好且结果稳定。

关键词: 旅行商问题, 改进遗传算法, 基因序列对比, 适应度函数, 等价矩阵

Abstract:

Genetic algorithm (GA) is one of the universal path optimization algorithms for traveling salesman problem (TSP). Aiming at the slow convergence and unstable solution of the traditional GA, a bioinformation heuristic genetic algorithm (BHGA) is proposed. By optimizing the fitness function and initial population, the gene sequence comparison technique in bioinformatics is introduced to carry out the cross recombination sorting. The gene reversal operation is used to implement mutation, to accelerate the convergence speed and get a better path solution. The numerical examples in TSPLIB database are solved by BHGA and the experimental simulation results show that the algorithm is effective and the solution of the medium and small scale TSP data are stable.

Key words: traveling salesman problem (TSP), improved genetic algorithm, gene sequence comparison, fitness function, equivalence matrix

中图分类号:

TP391.9

徐佳, 韩逢庆, 刘奇鑫, 薛晓霞. 一种求解TSP的生物信息启发式遗传算法[J]. 系统仿真学报, 2022, 34(8): 1811-1819.

Jia Xu, Fengqing Han, Qixin Liu, Xiaoxia Xue. Bioinformation Heuristic Genetic Algorithm for Solving TSP[J]. Journal of System Simulation, 2022, 34(8): 1811-1819.

图/表 11

图1

图2

图3

图4

图5

表1

表2

图6

图7

图8

图9

参考文献 23

1	肖建华, 李雅梦, 杜经国, 等. 电子商务背景下的城市物流共享仓库动态选址研究[J]. 数学的实践与认识, 2020, 50(15): 62-73.
	Xiao Jianhua, Li Yameng, Du Jingguo, et al. The Dynamic Location of Urban Shared Warehouse Under E-Commerce[J]. Mathematics in Practice and Theory, 2020, 50(15): 62-73.
2	程昶运, 熊瑞平, 王波, 等. 壳体曲面的机械臂喷涂路径规划方法研究[J]. 组合机床与自动化加工技术, 2020(3): 49-54.
	Cheng Changyun, Xiong Ruiping, Wang Bo, et al. Research on Spray Path Planning Method of Shell Surface for Manipulator[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2020(3): 49-54.
3	刘涛. 基于动态规划的大学周边外卖配送路径优化分析[J]. 物流工程与管理, 2020, 42(6): 125-126.
	Liu Tao. Optimization Analysis of Takeout Delivery Path Around University Based on Dynamic Programming[J]. Logistics Engineering and Management, 2020, 42(6): 125-126.
4	严炜, 龙长江, 李善军. 基于差分量子退火算法的农用无人机路径规划方法[J]. 华中农业大学学报, 2020, 39(1): 186-192.
	Yan Wei, Long Changjiang, Li Shanjun. A Path Planning Method for Agricultural UAV Based on DEQA Algorithm [J]. Journal of Huazhong Agricultural University, 2020, 39(1): 186-192.
5	李智慧. 非对称TSP问题下界的研究[J]. 数学的实践与认识, 2019, 49(5): 261-266.
	Li Zhihui. The Research of Optimal Down Bound of Asymmetrical TSP[J]. Mathematics in Practice and Theory, 2019, 49(5): 261-266.
6	Hougardy S, Zaiser F, Zhong X. The Approximation Ratio of the 2-Opt Heuristic for the Metric Traveling Salesman Problem [J]. Operations Research Letters(S0167-6377), 2020, 48(4): 401-404.
7	Adamo T, Ghiani G, Guerriero E. An Enhanced Lower Bound for the Time-Dependent Travelling Salesman Problem [J]. Computers & Operations Research(S0305-0548), 2020, 113 (1): 104795.
8	Gao Zhihan. On the Metric s-t Path Traveling Salesman Problem [J]. Siam Journal on Discrete Mathematics(S0895-4801), 2018, 60(2): 409-426.
9	李玲玉, 张昆. 用分枝定界算法求解旅行商问题的插件开发[J]. 测绘科学, 2020, 45(11): 185-190.
	Li Lingyu, Zhang Kun. Development of Plugin to Solve Travelling Salesman Problem with Branch and Bound Algorithm [J]. Science of Surveying and Mapping, 2020, 45(11): 185-190.
10	Peng W, Guo S, Li H. Research on Picking Route Optimization of Multi-Zone Warehouse Based on Traveling Salesman Problem and Simulated Annealing Algorithm[J]. Journal of Physics: Conference Series(S1742-6596), 2021, 1861(1): 012031.
11	邱媛. 基于一种改进的禁忌搜索算法的时间相关电动车车辆路径问题研究[D]. 南京: 南京大学, 2020.
	Qiu Yuan. Study on Time-Dependent EV Vehicle Routing Problem Based on an Improved Tabu Search Algorithm [D]. Nanjing: Nanjing University, 2020.
12	黄辰. 基于智能优化算法的移动机器人路径规划与定位方法研究[D]. 大连: 大连交通大学, 2018.
	Huang Chen. Research on Path Planning and Localization Method of Mobile Robot Based on Intelligent Optimization Algorithm [D]. Dalian: Dalian Jiaotong University, 2018.
13	孙滢. 若干最优化问题的粒子群算法及应用研究[D]. 合肥: 合肥工业大学, 2020.
	Sun Ying. Research on Particle Swarm Optimization Algorithm and Its Application for Some Optimization Problems[D]. Hefei: Hefei University of Technology, 2020.
14	朱大奇, 朱婷婷, 颜明重. 基于改进神经网络的多AUV全覆盖路径规划[J]. 系统仿真学报, 2020, 32(8): 1505-1514.
	Zhu Daqi, Zhu Tingting, Yan Mingzhong. Multi-AUV Complete Coverage Path Planning Based on Improved Neural Network [J]. Journal of System Simulation, 2020, 32(8): 1505-1514.
15	陈科胜, 鲜思东, 郭鹏. 求解旅行商问题的自适应升温模拟退火算法[J]. 控制理论与应用, 2020, 38(2): 245-254.
	Chen Kesheng, Xian Sidong, Guo Peng. Adaptive Temperature Rising Simulated Annealing Algorithm for Traveling Salesman Problem [J]. Control Theory & Applications, 2020, 38(2): 245-254.
16	叶多福, 刘刚, 何兵. 一种多染色体遗传算法解决多旅行商问题[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.
17	王震, 刘瑞敏, 朱阳光, 等. 一种求解TSP问题的改进遗传算法[J]. 电子测量技术, 2019, 42(23): 91-96.
	Wang Zhen, Liu Ruimin, Zhu Yangguang, et al. Improved Genetic Algorithm for Solving TSP Problem [J]. Electronic Measurement Technology, 2019, 42(23): 91-96.
18	张立毅, 高杨, 费腾. 求解旅行商问题的萤火虫遗传算法[J]. 计算机工程与设计, 2019, 40(7): 1939-1944.
	Zhang Liyi, Gao Yang, Fei Teng. Firefly Genetic Algorithm for Traveling Salesman Problem [J]. Computer Engineering and Design, 2019, 40(7): 1939-1944.
19	宋彦杰, 王沛, 张忠山, 等. 面向多星任务规划问题的改进遗传算法[J]. 控制理论与应用, 2019, 36(9): 1391-1397.
	Song Yanjie, Wang Pei, Zhang Zhongshan, et al. An Improved Genetic Algorithm for Multi-Satellite Mission Planning Problem [J]. Control Theory & Applications, 2019, 36(9): 1391-1397.
20	Panwar K, Deep K. Discrete Grey Wolf Optimizer for Symmetric Travelling Salesman Problem[J]. Applied Soft Computing (S1568-4946), 2021, 105: 107298.
21	王凌. 智能优化算法及其应用[M]. 北京: 清华大学出版社, 2001: 36-37.
	Wang Ling. Intelligent Optimization Algorithm and Its Application [M]. Beijing: Tsinghua University Press, 2001: 36-37.
22	孙啸, 陆祖宏, 谢建明. 生物信息学基础[M]. 北京: 清华大学出版社, 2005.
	Sun Xiao, Lu Zuhong, Xie Jianming. Fundamentals of Bioinformatics [M]. Beijing: Tsinghua University Press, 2005.
23	Qiao W B, Créput Jean-Charles. Multiple K-Opt Evaluation Multiple K-Opt Moves With GPU High Performance Local Search to Large-Scale Traveling Salesman Problems [J]. Annals of Mathematics and Artificial Intelligence (S1012-2443), 2020, 88(4): 347-365.

集合类型	官方数据的最优路径长度	实验所得最优路径长度				实验所得路径长度的均值
集合类型	官方数据的最优路径长度	NN	SA	GA	BHGA	NN	SA	GA	BHGA
att48	33 522	39 237	34 012	33 990	33 522	40 900	34 903	34 019	33 545
pr76	108 159	137 355	120 549	111 170	107 973	142 183	127 562	110 380	109 210
eil101	629	703	669	676	644	726	670	686	651
Berlin52	7 544	8 439	8 291	8 302	7 544	8 694	8 419	8 450	7 695

集合类型	NN	SA	GA	BHGA
att48	17.04	1.46	1.40	0
pr76	21.25	11.45	2.78	-0.17
eil101	11.82	6.31	7.45	2.35
Berlin52	11.86	9.89	10.04	1.96

[1]	于淼, 李曼茹, 赵愈. 考虑等待提示机制的呼叫中心联合排班方法[J]. 系统仿真学报, 2022, 34(7): 1651-1661.
[2]	唐婕, 曹瑾鑫. 共享汽车联合调度优化研究[J]. 系统仿真学报, 2021, 33(8): 1959-1968.
[3]	叶多福, 刘刚, 何兵. 一种多染色体遗传算法解决多旅行商问题[J]. 系统仿真学报, 2019, 31(1): 36-42.
[4]	张亚男, 杨慧中. 基于RVM组合核优化的软测量模型研究[J]. 系统仿真学报, 2018, 30(1): 272-277.
[5]	徐小平, 朱秋秋, 王峰. 求解圆排列问题的粒子群蚁群优化算法[J]. 系统仿真学报, 2017, 29(2): 248-254.
[6]	王宪伦, 喻洋, 崔玉霞. 面向多轮廓的机器人加工路径优化研究[J]. 系统仿真学报, 2017, 29(2): 355-359.
[7]	王大勇, 王慧. 基于仿真优化的掘进机铲板综合性能研究[J]. 系统仿真学报, 2016, 28(2): 434-441.