Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem

doi:10.23919/JSEE.2020.000050

Abstract

Abstract:

As a typical representative of the NP-complete problem, the traveling salesman problem (TSP) is widely utilized in computer networks, logistics distribution, and other fields. In this paper, a discrete lion swarm optimization (DLSO) algorithm is proposed to solve the TSP. Firstly, we introduce discrete coding and order crossover operators in DLSO. Secondly, we use the complete 2-opt (C2-opt) algorithm to enhance the local search ability. Then in order to enhance the efficiency of the algorithm, a parallel discrete lion swarm optimization (PDLSO) algorithm is proposed. The PDLSO has multiple populations, and each sub-population independently runs the DLSO algorithm in parallel. We use the ring topology to transfer information between sub-populations. Experiments on some benchmarks TSP problems show that the DLSO algorithm has a better accuracy than other algorithms, and the PDLSO algorithm can effectively shorten the running time.

Key words: discrete lion swarm optimization (DLSO) algorithm, complete 2-opt (C2-opt) algorithm, parallel discrete lion swarm optimization (PDLSO) algorithm, traveling salesman problem (TSP)

Daoqing ZHANG, Mingyan JIANG. Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem[J]. Journal of Systems Engineering and Electronics, 2020, 31(4): 751-760.

Figures/Tables 15

Fig 1

Fig 2

Table 1

Table 2

Table 3

Fig 3

Fig 4

Table 4

Table 5

Table 6

Table 7

Fig 5

Table 8

Table 9

Fig 6

References 29

1	HUANG Z, ZHENG Q P, PASILIAO E, et al. A cutting plane method for risk-constrained traveling salesman problem with random arc costs. Journal of Global Optimization, 2019, 74 (4): 839- 859. doi: 10.1007/s10898-018-0708-0
2	BELLMAN R E, DREYFUS S E. Applied dynamic programming. Princeton, New Jersey: Princeton University Press, 2015.
3	CARRABS F, CERULLI R, SPERANZA M G. A branch-and-bound algorithm for the double travelling salesman problem with two stacks. Networks, 2013, 61 (1): 58- 75. doi: 10.1002/net.21468
4	PICHPIBUL T, KAWTUMMACHAI R. An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem. ScienceAsia, 2012, 38 (3): 307- 318. doi: 10.2306/scienceasia1513-1874.2012.38.307
5	KARAPETYAN D, GUTIN G. Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem. European Journal of Operational Research, 2011, 208 (3): 221- 232.
6	HELSGAUN K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 2000, 126 (1): 106- 130.
7	UCHIDA A, ITO Y, NAKANO K. An efficient GPU implementation of ant colony optimization for the traveling salesman problem. Proc. of the 3rd IEEE International Conference on Networking and Computing, 2012, 94- 102.
8	JIANG M Y, YUAN D F. Artificial bee colony algorithm and its application. Beijing: Science Press, 2014.
9	JIANG M Y, YUAN D F. Artificial fish swarm algorithm and its application. Beijing: Science Press, 2012.
10	KAN J M, ZHANG Y. Application of an improved ant colony optimization on generalized traveling salesman problem. Energy Procedia, 2012, 17, 319- 325. doi: 10.1016/j.egypro.2012.02.101
11	KEFI S, ROKBANI N, KR{O}MER P, et al. Ant supervised by PSO and 2-opt algorithm, AS-PSO-2Opt, applied to traveling salesman problem. Proc. of the IEEE International Conference on Systems, Man, and Cybernetics, 2016, DOI: 10.1109/SMC.2016.7844999.
12	ZHOU Y, LUO Q, CHEN H, et al. A discrete invasive weed optimization algorithm for solving traveling salesman problem. Neurocomputing, 2015, 151, 1227- 1236. doi: 10.1016/j.neucom.2014.01.078
13	OUAARAB A, AHIOD B, YANG X S. Discrete cuckoo search algorithm for the travelling salesman problem. Neural Computing and Applications, 2014, 24 (7/8): 1659- 1669.
14	HAN Y Y, GONG D W, SUN X. A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking. Engineering Optimization, 2015, 47 (7): 927- 946. doi: 10.1080/0305215X.2014.928817
15	GENG N, MENG Q, GONG D W, et al. How good are distributed allocation algorithms for solving urban search and rescue problems? A comparative study with centralized algorithms. IEEE Trans. on Automation Science and Engineering, 2018, 16 (1): 478- 485.
16	ZHANG J H, GONG D W, ZHANG Y. A niching PSO-based multi-robot cooperation method for localizing odor sources. Neurocomputing, 2014, 123, 308- 317. doi: 10.1016/j.neucom.2013.07.025
17	GONG D W, ZHANG Y, QI C L. Localising odour source using multi-robot and anemotaxis-based particle swarm optimisation. IET Control Theory & Applications, 2012, 6 (11): 1661- 1670.
18	LIU S J, YANG Y, ZHOU Y Q. A swarm intelligence algorithm—lion swarm optimization. Pattern Recognition and Artificial Intelligence, 2018, 31 (5): 431- 441.
19	MAHDAVI S, RAHNAMAYAN S, DEB K. Opposition based learning: a literature review. Swarm and Evolutionary Computation, 2018, 39, 1- 23. doi: 10.1016/j.swevo.2017.09.010
20	UMBARKAR A J, SHETH P D. Crossover operations in genetic algorithms: a review. ICTACT Journal on Soft Computing, 2015, 6 (1): 1083- 1092.
21	ABDOUN O, ABOUCHABAKA J. A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem. International Journal of Computer Applications, 2011, 31 (11): 49- 57.
22	LALWANI S, SHARMA H, SATAPATHY S C, et al. A survey on parallel particle swarm optimization algorithms. Arabian Journal for Science and Engineering, 2019, 44 (4): 2899- 2923. doi: 10.1007/s13369-018-03713-6
23	NALEPA J, BLOCHO M. Co-operation in the parallel memetic algorithm. International Journal of Parallel Programming, 2015, 43 (5): 812- 839. doi: 10.1007/s10766-014-0343-4
24	FRAHNOW C, KOTZING T. Ring migration topology helps bypassing local optima. Proc. of the International Conference on Parallel Problem Solving from Nature, 2018, 129- 140.
25	REINELT G. TSPLIB—a traveling salesman problem library. ORSA Journal on Computing, 1991, 3 (4): 376- 384.
26	GUTIN G, PUNNEN A. The traveling salesman problem and its variations. Dordrecht: Kluwer Academic Publishers, 2002.
27	GUNDUZ M, KIRAN M S, OZCEYLAN E. A hierarchic approach based on swarm intelligence to solve the traveling salesman problem. Turkish Journal of Electrical Engineering & Computer Sciences, 2015, 23 (1): 103- 117.
28	AMDAHL G M. Validity of the single processor approach to achieving large scale computing capabilities. Proc. of the Spring Joint Computer Conference, 1967, 483- 485.
29	GUSTAFSON J L. Reevaluating Amdahl's law. Communications of the ACM, 1988, 31 (5): 532- 533. doi: 10.1145/42411.42415

Specification	Value
Operating system	Ubuntu 18.04LTS
CPU	Core i7 4 GHz
Memory	30 GB
Python version	Python 3.6
MPI version	Mpi4py

Variable	Value	Meaning
$SN$	96	Population size
$\beta$	0.2	Percentage of adult lions
$T$	150	Maximum iteration number

Problem	OPT	Best	Average	Error/%	Std	Time/s
Eil51	426	428.87	429.70	0.87	1.61	8.51
Berlin52	7 542	7 544.37	7544.37	0.031	0	8.92
St70	675	677.11	678.78	0.56	3.38	17.89
Pr76	108 159	108 159.43	108 572.35	0.38	341.96	22.12
KroA100	21 282	21 285.44	21 370.09	0.41	44.66	61.02
KroB100	22 141	22 142.07	22 270.58	0.58	95.52	45.08
Lin105	14 379	14 383.0	14 433.33	0.38	34.23	50.55
Ch130	6 110	6 158.08	6 201.98	1.50	30.96	93.33
Ch150	6 528	6 530.90	6 597.83	1.07	38.83	164.09
D198	15 780	15 808.93	15 896.48	0.74	35.21	284.53
KroA200	29 368	29 519.83	29 766.27	1.37	118.37	288.19
KroB200	29 437	29 652.94	29 994.08	1.89	226.62	285.06
Tsp225	3 916	3 929.51	3 977.53	1.57	21.05	397.92
A280	2 579	2 609.54	2 650.49	2.77	33.83	768.44
Lin318	42 029	42 744.96	43 172.51	2.72	235.18	1 113.98
Pcb442	50 778	52 330.24	52 841.26	4.06	230.75	2 883.50
Pr1002	259 045	273 696.03	275 825	6.47	1 189.80	34 456.31

Problem	OPT	IVRS+2opt			ACO+2opt			ACO+ABC			DLSO+2opt
Problem	OPT	Best	Average	Error/%	Best	Average	Error/%	Best	Average	Error/%	Best	Average	Error/%
Eil51	426	429.12	431.11	1.20	431.26	439.26	3.11	431.74	443.39	4.08	$\textbf{428.98}$	$\textbf{429.70}$	$\textbf{0.87}$
Berlin52	7 542	7 544.37	7 547.24	0.07	7 549.53	7 556.59	0.19	7 544.37	7 544.37	3.14	$\textbf{7 544.37}$	$\textbf{7 544.37}$	$\textbf{0.031}$
St70	675	—	—	—	—	—	—	687.24	700.58	3.79	$\textbf{677.11}$	$\textbf{678.78}$	$\textbf{0.56}$
KroA100	21 282	21 309.43	21 498.62	1.02	22 006.40	23 441.80	10.15	22 122.75	22 435.31	5.42	$\textbf{21 285.44}$	$\textbf{21 370.09}$	$\textbf{0.41}$
Eil101	629	$\textbf{631.29}$	$\textbf{648.67}$	$\textbf{3.13}$	654.50	672.38	6.90	672.71	683.39	8.65	642.53	649.05	3.19
Ch150	6 528	—	—	—	—	—	—	6 641.69	6 677.12	2.28	$\textbf{6 530.90}$	$\textbf{6 597.83}$	$\textbf{1.07}$
D198	15 780	15 842.52	15 972.47	1.22	16 054.47	16 252.93	2.30	—	—	—	$\textbf{15 808.93}$	$\textbf{15 896.48}$	$\textbf{0.74}$

Variable	Value	Meaning
$SN$	96	Total population size
$\beta$	0.2	Percentage of adult lions
$T$	150	Maximum iteration number
$N$	2/3/4	Sub-population number
$R$	10	Migration interval