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

doi:10.1007/s12204-019-2039-9

Abstract

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

摘要： 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

CLC Number:

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.

References 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.