Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem

doi:10.1007/s12204-019-2039-9

Journal of Shanghai Jiao Tong University (Science) ›› 2019, Vol. 24 ›› Issue (1): 41-47.doi: 10.1007/s12204-019-2039-9

Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem

DONG Ruyi (董如意), WANG Shengsheng *(王生生), WANG Guangyao (王光耀), WANG Xinying (王新颖)

(1. College of Computer Science and Technology, Jilin University, Changchun 130012, China; 2. Jilin Vocational College of Industry and Technology, Jilin 132013, Jilin, China; 3. College of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China)

出版日期:2019-02-28 发布日期:2019-01-28
通讯作者: WANG Shengsheng *(王生生 E-mail:wss@jlu.edu.cn

Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem

DONG Ruyi (董如意), WANG Shengsheng *(王生生), WANG Guangyao (王光耀), WANG Xinying (王新颖)

(1. College of Computer Science and Technology, Jilin University, Changchun 130012, China; 2. Jilin Vocational College of Industry and Technology, Jilin 132013, Jilin, China; 3. College of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China)

Online:2019-02-28 Published:2019-01-28
Contact: WANG Shengsheng *(王生生 E-mail:wss@jlu.edu.cn

摘要/Abstract

摘要： Traveling salesman problem (TSP) is one of the typical NP-hard problems, and it has been used in many engineering applications. However, the previous swarm intelligence (SI) based algorithms for TSP cannot coordinate with the exploration and exploitation abilities and are easily trapped into local optimum. In order to deal with this situation, a new hybrid optimization algorithm based on wolf pack search and local search (WPS-LS) is proposed for TSP. The new method firstly simulates the predatory process of wolf pack from the broad field to a specific place so that it allows for a search through all possible solution spaces and prevents wolf individuals from getting trapped into local optimum. Then, local search operation is used in the algorithm to improve the speed of solving and the accuracy of solution. The test of benchmarks selected from TSPLIB shows that the results obtained by this algorithm are better and closer to the theoretical optimal values with better robustness than those obtained by other methods.

关键词: traveling salesman problem (TSP), swarm intelligence (SI), wolf pack search (WPS), combinatorial optimization

Abstract: Traveling salesman problem (TSP) is one of the typical NP-hard problems, and it has been used in many engineering applications. However, the previous swarm intelligence (SI) based algorithms for TSP cannot coordinate with the exploration and exploitation abilities and are easily trapped into local optimum. In order to deal with this situation, a new hybrid optimization algorithm based on wolf pack search and local search (WPS-LS) is proposed for TSP. The new method firstly simulates the predatory process of wolf pack from the broad field to a specific place so that it allows for a search through all possible solution spaces and prevents wolf individuals from getting trapped into local optimum. Then, local search operation is used in the algorithm to improve the speed of solving and the accuracy of solution. The test of benchmarks selected from TSPLIB shows that the results obtained by this algorithm are better and closer to the theoretical optimal values with better robustness than those obtained by other methods.

Key words: traveling salesman problem (TSP), swarm intelligence (SI), wolf pack search (WPS), combinatorial optimization

中图分类号:

TP 18

DONG Ruyi (董如意), WANG Shengsheng *(王生生), WANG Guangyao (王光耀), WANG Xinying (王新颖). Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem[J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(1): 41-47.

DONG Ruyi (董如意), WANG Shengsheng *(王生生), WANG Guangyao (王光耀), WANG Xinying (王新颖) . Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem[J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(1): 41-47.

参考文献 19

[1]	LAPOTE G. The traveling salesman problem: Anoverview of exact and approximate algorithms [J]. EuropeanJournal of Operational Research, 1992, 59(2):231-247.
[2]	JIANG H, SUN W C, REN Z L, et al. Evolving hardand easy traveling salesman problem instances: Amulti-objective approach [C]//Proceedings of the 10thInternational Conference on Simulated Evolution andLearning. Dunedin, New Zealand: Springer InternationalPublishing, 2014: 216-227.
[3]	URRUTIA S, MILAN′ES A, L?KKETANGEN A. Adynamic programming based local search approach forthe double traveling salesman problem with multiplestacks [J]. International Transactions in OperationalResearch, 2015, 22(1): 61-75.
[4]	JOZEFOWIEZ N, LAPORTE G, SEMET F. A genericbranch-and-cut algorithm for multiobjective optimizationproblems: Application to the multilabel travelingsalesman problem [J]. INFORMS Journal on Computing,2012, 24(4): 554-564.
[5]	QU D P, TU H, FAN T S. Performance analysis of localoptimization algorithms in traveling salesman problem[J]. Advanced Materials Research, 2014, 846/847:1364-1367.
[6]	ZHANG J W. Hybrid particle swarm optimizationalgorithm for large-scale travelling salesman problem[J]. Applied Mechanics and Materials, 2014,513/514/515/516/517: 1773-1778.
[7]	CONTRERAS-BOLTON C, PARADA V. Automaticcombination of operators in a genetic algorithm tosolve the traveling salesman problem [J]. PLoS ONE,2015, 10(9): e0137724.
[8]	YANG J Y, DING R F, ZHANG Y, et al. An improvedant colony optimization (I-ACO) method forthe quasi travelling salesman problem (quasi-TSP) [J].International Journal of Geographical Information Science,2015, 29(9): 1534-1551.
[9]	ZHOU Y Q, LUO Q F, CHEN H, et al. A discrete invasiveweed optimization algorithm for solving travelingsalesman problem [J]. Neurocomputing, 2015, 151(3):1227-1236.
[10]	GARLIA M B. Particle swarm optimization withan improved exploration-exploitation balance[C]//Proceedings of 51st Midwest Symposium onCircuits and Systems. [s.l.]: IEEE, 2008: 759-762.
[11]	YANG C G, TU X Y, CHEN J. Algorithm of marriagein honey bees optimization based on the wolfpack search [C]//Proceedings of International Conferenceon Intelligent Pervasive Computing. [s.l.]: IEEE,2007: 462-467.
[12]	WU H S, ZHANG F M, WU L S. New swarm intelligencealgorithm: Wolf pack algorithm [J]. SystemsEngineering and Electronics, 2013, 35(11): 2430-2438(in Chinese).
[13]	OUYANG X X, ZHOU Y Q, LUO Q F, et al. A noveldiscrete cuckoo search algorithm for spherical travelingsalesman problem [J]. Applied Mathematics & InformationSciences, 2013, 7(2): 777-784.
[14]	PASTI R, DE CASTRO L N. A neuro-immunenetwork for solving the traveling salesman problem[C]//Proceedings of IEEE International Joint Conferenceon Neural Network Proceedings. Vancouver,Canada: IEEE, 2006: 3760-3766.
[15]	MASUTTI T A S, DE CASTRO L N. A self-organizingneural network using ideas from the immune system tosolve the traveling salesman problem [J]. InformationSciences, 2009, 179(10): 1454-1468.
[16]	WU J Q, OUYANG A J. A hybrid algorithm of ACOand delete-cross method for TSP [C]//Proceedings of2012 International Conference on Industrial Controland Electronics Engineering. [s.l.]: IEEE, 2012: 1694-1696.
[17]	DONGGF,GUOWW, TICKLE K. Solving the travelingsalesman problem using cooperative genetic antsystems [J]. Expert Systems with Applications, 2012,39: 5006-5011.
[18]	PEKER M, SEN B, KUMRU P Y. An efficient solvingof the traveling salesman problem: The ant colonysystem having parameters optimized by the Taguchimethod [J]. Turkish Journal of Electrical Engineering& Computer Science, 2013, 21: 2015-2036.
[19]	G¨UND¨UZ M, KIRAN M S, ¨OZCEYLAN E. A hierarchicapproach based on swarm intelligence to solvethe traveling salesman problem [J]. Turkish Journal ofElectrical Engineering & Computer Sciences, 2015, 23:103-117.

Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem

Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献 19

相关文章 15

编辑推荐

Metrics

本文评价

[1]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(3): 402-410.
[2]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(2): 160-167.
[3]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(2): 176-189.
[4]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(2): 190-201.
[5]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(1): 55-69.
[6]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(1): 70-80.
[7]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(1): 81-89.
[8]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(1): 90-98.
[9]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(1): 112-120.
[10]	. [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(6): 757-764.
[11]	MA Guohong (马国红), LI Jian (李健), HE Yinshui (何银水), XIAO Wenbo (肖文波). Weld Geometry Monitoring for Metal Inert Gas Welding Process with Galvanized Steel Plates Using Bayesian Network[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 239-244.
[12]	PENG Pai, CHEN Cong , YANG Yongsheng . Particle Swarm Optimization Based on Hybrid Kalman Filter and Particle Filter [J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 681-688.
[13]	QIN Zhichang, XIN Ying, SUN Jianqiao . Multi-Objective Optimal Feedback Controls for Under-Actuated Dynamical System[J]. Journal of Shanghai Jiao Tong University(Science), 2020, 25(5): 545-552.
[14]	ZHANG Yun, Lü Runyan, CAI Yunze . Missile-Target Situation Assessment Model Based on Reinforcement Learning[J]. Journal of Shanghai Jiao Tong University(Science), 2020, 25(5): 561-568.
[15]	LIU Mingguang, LIAO Yaxuan, LI Xiangshun . Data-Driven Fault Detection of Three-Tank System Applying MWAT-ICA[J]. J Shanghai Jiaotong Univ Sci, 2020, 25(5): 659-664.