Bioinformation Heuristic Genetic Algorithm for Solving TSP

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 11

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Table 2

Fig. 6

Fig. 7

Fig. 8

Fig. 9

References 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]	Miao Yu, Manru Li, Yu Zhao. Joint Shift Scheduling Method for Call Center with Mechanism of Delay Information [J]. Journal of System Simulation, 2022, 34(7): 1651-1661.
[2]	Zhang Yanan, Yang Huizhong. RVM Soft Sensing Model Based on Optimized Combined Kernel Function [J]. Journal of System Simulation, 2018, 30(1): 272-277.
[3]	Wang Xianlun, Yu Yang, Cui Yuxia. Research on Robot Processing Path Optimization for Multi-contour [J]. Journal of System Simulation, 2017, 29(2): 355-359.
[4]	Wang Dayong, Wang Hui. Study on Comprehensive Performance of Roadheader Shovel Based on Simulation Optimization Method [J]. Journal of System Simulation, 2016, 28(2): 434-441.