ZHANG Daoqing and JIANG Mingyan

School of Information Science and Engineering,Shandong University,Qingdao 266237,China

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

1.Introduction

The classical traveling salesman problem(TSP)has a very intuitive explanation:for a given city group,the traveling salesman needs to find the shortest route through all cities,requiring to pass each city only once and finally return to the starting city.

In the early stage,the exact method was mainly utilized to solve the TSP,including the cutting plane method[1],the dynamic programming method[2],the branch definition method[3].These methods are characterized by traversing the entire solution space at the cost of high complexity to obtain the theoretical optimal solution,not suitable for large-scale TSP.In order to overcome the shortcomings of the exact algorithm,approximation algorithm becomes the mainstream algorithm in the TSP field,such as the Clarke&Wright’s savings(CWS)algorithm[4],the local search algorithm(2-opt,3-opt,Lin and Kernighan’s(LK)algorithm)[5],the Lin-Kernighan heuristic(LKH)algorithm[6]and the heuristic algorithm represented by ant colony(ACO)algorithm[7],the artificial bee colony(ABC)algorithm[8],and the artificial fish swarm algorithm[9].The heuristic algorithm can find the approximate global optimal solution in the nonlinear sophisticated solution space,so it can be utilized in various optimization problems,which is not limited by the convexity and derivability of the optimization problem.In the TSP,a hybrid algorithm combining the local search algorithm with strong local optimization ability and the heuristic algorithm with global optimization ability can obtain a practical solution within an acceptable time,which becomes a new direction to solve the TSP.Kan et al.[10]proposed an improved ACO algorithm,by reducing the processing cost of ant routing and using the individual variation and routing strategy(IVRS).Experiments show that the IVRS has achieved good results. Kefi et al. [11] proposed a hybrid algorithm of ant heuristic-particle swarm optimization-2opt(AS-PSO-2opt).The PSO algorithm optimized the parameters of the ACO.The ACO algorithm searched for the route,then was optimized by the 2-opt operator.Experiments showed this method could achieve better results.Zhou et al.[12]proposed the discrete weed algorithm.Ouaarab et al.[13]proposed the discrete cuckoo search(DCS)algorithm.They are all hybrid algorithms,and the results show the combination of the heuristic algorithm and the local search algorithm is an effective way to solve the TSP.In recent years,in some NP-hard combinatorial optimization problems related to TSP,the discretized heuristic optimization algorithm also performs well.Han[14]et al.proposed the discrete ABC(DABC)algorithm to solve the flow shop scheduling problem;at the same time,the distributed heuristic optimization algorithm has an excellent performance in solving urban search and rescue prob-lems[15],localizing odor sources[16,17].Inspired by the above papers,we extend the original lion swarm optimization(LSO)algorithms to parallel and discrete forms.

Noted that it is still a complicated problem to get the exact solution of the TSP,and how to get an effective solution within a reasonable time has become the focus of the research.In this paper,a discrete LSO(DLSO)algorithm and a parallel DLSO algorithm(PDLSO)for solving the TSPs are proposed.We propose these two algorithms because they have two main advantages:(i)the DLSO algorithm obtains a better solution in a reasonable time;(ii)the PDLSO algorithm significantly shortens the running time.

The article is organized as follows:Section 2 introduces the LSO algorithm and the complete 2-opt(C2-opt)algorithm;Section 3 introduces DLSO algorithms and PDLSO algorithms;Section 4 utilizes symmetric benchmarks TSPs in TSP library(TSPLIB)to validate the effectiveness of the algorithm and analyze the experimental results;Section 5 concludes this paper and proposes future work.

2.Fundamental knowledge

2.1 LSO algorithm

The LSO algorithm[18]is a new swarm intelligence algorithm proposed by Liu et al.in 2018.By simulating the lion hunting behavior,the LSO algorithm performs better than the traditional genetic algorithm(GA)and PSO algorithm in terms of convergence speed and solution accuracy.The main idea of the LSO algorithm is as follows:according to the fitness value,the lion swarm is divided into three categories:lion king,lioness,and lion cubs.Among them,lion king and lioness are adult lions, the proportion of adult lions in a population isβ.

In theDdimensional search space,SNlions form a population,and the position of theith lion in thetth iteration is

The lion king moves around the global optimal in a small range:

whereγis a random number generated according to the standard normal distributionN(0,1);is the optimal historical position of theith lion in the population at thetth generation;gtis the optimal position of thetth generation.

Lioness moves in pair as follows:

whereαf=step·expis the disturbance factor of the lioness movement,taking the step length step=whereandare the minimum mean and maximum mean values of each dimension in the lion activity space;is the optimal historical position of a lioness randomly selected from thetth generation lioness population.

To increase the global optimization ability,lion cubs have three movement modes:follow the lion king to move,follow the lioness to move,and move by elite oppositionbased learning[19]:

whereqis a random fraction generated according to the uniform distributionU(0,1);αc=stepis the disturbance factor of the cub movement,whereTis the maximum number of iterations;is the optimal historical position of the lioness at thetth generation;indicates the position where the cubs are expelled.

From the above introduction,we know that the LSO algorithm has three main control parameters:the disturbance factor of the lioness movementαf,the disturbance factor of the cub movementαc,and the percentage of adult lionsβ.The values ofαfandαcare based on step which is determined by the optimization problem itself,and the value ofβin the original paper is 0.3.

The algorithm flow is as follows:

Step 1Initialization:Initialize parametersTandβ.Randomly generateSNlion swarm individualsxti(i=1,2,...,SN).First,sort according to the fitness value of the individual,and then determine the initial positions of the lion king,lioness,and cubs.

Step 2Lions move:According to(1),(2)and(3),complete the movement of the lion king,lioness and lion cubs.

Step 3Lions update:Update the fitness value;updateandgt.

Algorithm termination:Repeat steps 2 to 3 untilt=T;record the optimal fitness value and the optimal individual of the population.

2.2C2-opt algorithm

The 2-opt algorithm is a branch of the local search K-opt algorithm,and it is the most basic method in the local search algorithm.The basic idea is to delete two edges in the original route and replace them with two other shorter edges.As shown in Fig.1,the left route is the original route.Two edges AB and CD are selected randomly.If the sum of the edge length of AB and CD is larger than that of AC and BD,edges AB and CD are deleted and replaced by shorter edges AC and BD.

Fig.1The 2-opt schematic algorithm

The convergence of the 2-opt algorithm using the random selection method requires a long computation time,so the C2-opt algorithm is utilized in this paper.The C2-opt performs a C2-opt operation on a route to obtain local optimum so that it can converge in a short time[12].

3.Proposed methods(DLSO and PDLSO)

3.1 DLSO algorithm

The original LSO algorithm is only suitable for the continuous functions.In order to make the LSO applicable to the TSP,a DLSO algorithm is proposed,the specific improvement methods are as follows:

(i)Discrete coding:The lion population changes from the traditional real value coding to integer discrete coding.For the TSP withncities,the lion individual is represented as an array of lengthn,and the value of each element in the array is a positive integer between 1 andn,representing the corresponding city;in order to satisfy the Hamiltonian loop condition,there are no elements with the same value in the array.

(ii)Individual crossover: The lion movement of the LSO algorithm is completed by(1),(2)and(3),and the core of formulas is to adjust the numerical value of elements in the individual.If a discretely coded individual is directly substituted into formulas,a non-integer will be obtained,although it can be converted to an integer by rounding,modulo,etc.However,the TSP focuses on the sequential structure of the elements in the individual rather than the numerical value of the element,these methods cannot guarantee that the newly generated individual will inherit the structure of the parent individual.The crossover operator introduced in the GA can enable the offspring to retain the structural information of the parent,making the movement of individuals more effective.Standard crossover operators in GAs include partially-mapped crossover(PMX),shuffle crossover,order crossover(OX),cycle crossover(CX)and uniform crossover[20].According to the experiment,we can see the OX operator will achieve a better solution in GA[21],so we utilize the OX operator in DLSO.

The OX was proposed by Oliver et al..It generates the offspring by choosing a sub-tour from one parent and preserving the relative order of cities of the other parent.The OX works as follows:

I m sorry! That s not what I wanted to hear. What about Everything s going to be fine? or It s nothing serious! Blood clots in the lungs? That was serious!

Randomly select two cut points marked with“|”on parentsPAR1andPAR2:

Generate offspring in the following way: first,the subtour between the two cut points are coppied into offsprings:

Then,starting from the second cut point of a parent,the bits from another parent are coppied in the same order,and the existing bits are omitted.Take generatingO1as an example.The sequence of bits inPAR2from the second cut point is(4 7 2 5 6 1 3),removing bits(3 4 5)that already exist inO1,we get a new sequence(7 2 6 1).Starting from the second cut point,place this sequence inO1,we get

Again,we can get

In summary,the movements of the lion king,lioness and cubs are completed according to

where the meanings of the symbolare the same as those in(1),(2)and(3);OX indicates the OX operation.

(iii)Introduction of C2-opt operator:The lion swarm algorithm guarantees strong global optimization ability by dividing the population into three categories—lion king,lioness and lion cub;but it converges slowly in the TSP and has poor local optimization ability.However,by combining with the C2-opt operator with strong local optimization ability,the ideal solution can be obtained.The specific method is that in each iteration,C2-opt operation is performed on the lion king,the two optimal lionesses,and the optimal lion cub.

(iv)Fitness function:The graph theory gives an accurate mathematical description of the TSP—giving a weighted directed graphG=(V,E,W),vertex setV={v1,v2,v3,...,vn},wherevirepresents theith city;the edge setE={?vi,vj?|i,j∈N+;i,j?n};the weight setW={di,j|i,j∈N+;i,j?n;di,j∈R+},wheredi,jrepresents the length corresponding to the edge?vi,vj?.The loop that passes through each vertex once and only once in the graphGis called a Hamiltonian loop.As we mentioned in discrete coding,the individual coding in the population satisfies the Hamiltonian loop condition,so the individualxcan be decoded into a Hamiltonian loop?vx1,vx2,vx3,...,vxn,vx1?.The sum of the weights of this loop is the fitness value,so the fitness function can be expressed by

The pseudo-code of DLSO is as follows:

Algorithm 1DLSO algorithm

InputPopulation sizeSN;percentage of adult lionsβ;maximum iteration numberT.

3.2 PDLSO algorithm

The DLSO algorithm consumes a lot of computing time in solving large-scale TSPs.In order to obtain a solution with the same quality as the DLSO algorithm in a shorter time,the PDLSO algorithm is proposed in this paper.

The idea of the PDLSO algorithm is as follows:SetSNas the total population size,the population is divided intoNsub-populations.Therefore,the population size of each sub-populationSNsubcan be derived from

Then,each sub-population runs the DLSO algorithm independently,and exchanges information with each other until the algorithm terminates,the optimal solution of all sub-populations is the final solution of the algorithm.The topological structure and the parallel strategy have a great influence on the PDLSO algorithm;common topologies are shown in Fig.2,including the star topology,ring topology,and fully connected topology[22].

Fig.2Three topologies

Nalepa and Blocho’s[23]experiments show the star topology distributes the best individuals between subpopulations,so it converges relatively fast;the ring topology converges slower than the star topology,but it can benefit from broader search space exploration and give the best asymptotic results.Frahnow et al.[24]proved that the convergence rate of the ring topology is faster than the fully connected topology,and the ring topology can be preferable over the fully connected topology in terms of maintaining diversity. Because the DLSO algorithm has a strong local optimization ability,the ring topology with the global optimization ability is more suitable for the PDLSO algorithm,so we choose the ring topology.

The parallel strategy which is mainly determined by the migration rate,the migration periodR,and the migration rules,determines the information exchange between subpopulations and increases the global information of the algorithm.The migration rate determines the number of individuals that undergo migration in every exchange;the migration periodRrepresents the number of iterations between two migrations; the migration rule determines which individuals are migrated and which individuals in the target sub-population are replaced.Combined with the ring topology,the parallel strategy utilized in this paper is as follows:when the migration periodRis satisfied,the lion kinggkin thekth sub-population is migrated to its neighboring(k+1)th sub-population,replacing the worst individual in the(k+1)th sub-population.With the above pa-rallel strategy,the number of communication times between sub-populations comm can be derived from(9),whereTis the maximum number of iterations.

The pseudo-code of PDLSO is as follows:

Algorithm 2PDLSO algorithm

InputTotal population sizeSN;percentage of adult lionsβ;maximum iteration numberT;sub-population numberN;migration intervalR.

4.Experiments and results

The specifications of the testing platform utilized in the experiments are shown in Table 1.Seventeen symmetric TSPs(Eil51,Berlin52,St70,Pr76,KroA100,KroB100,Lin105,Ch130,Ch150,D198,KroA200,KroB200,Tsp225,A280,Lin318,Pcb442,Pr1002)in TSPLIB[25]are selected as cases to test the DLSO algorithm;ten TSPs of different scales(Eil51,Berlin52,Eit70,KroA100,Ch150,D198,Dp225,A280,Lincb318,Pcb442)are selected as cases to test the PDLSO algorithm.Each instance runs 20 times independently.

Table 1Specifications of the experimental platform

4.1Experimental analysis of DLSO algorithm

In this section,we first analyze the results of DLSO in the TSP problem and then verify the effectiveness of the DLSO algorithm by comparing it with other algorithms.The parameters of the DLSO algorithm are shown in Table 2.Table 3 show the experimental results.In Table 3,the first column contains 16 specific TSPs,the column OPT represents the known optimal value,the column Best represents the optimal value obtained by the DLSO algorithm in 20 independent runs,the column Average represents the mean value of solutions,the column Std represents the standard deviation,the column Time represents the average running time of the DLSO algorithm,and the column Error represents the relative deviation between the average value of the DLSO algorithm and the known optimal value.Relative deviation is a general index in the TSP[26],which is calculated by

Table 2 DLSO parameters setting

As can be seen from Table 3,for the problem of the city size within 100,the DLSO algorithm can get the error of[0.03%,0.9%]in 1 min,and the deviation of solutions is small,for example,the Berlin52 problem’s standard deviation is 0, indicating the algorithm is robust. For the problem of 100 to 300 cities,the error of solution is between[0.4%,2.7%],and the running time is between 1 min and 12 min,which does not increase rapidly.For the problem of 300 to 500 cities,the running time can be limited within 50 min,and the error is less than4%.For the problem of over1 000cities,although the running time increases rapidly,the error is about 6%,which has not increased rapidly.With the increase of the city scale,the error of the algorithm becomes more massive,but in this experiment,the maximum number of iterationsTis 150,and a more accurate solution can be obtained by increasing the value ofTappropriately.

Table 3Experimental results of DLSO algorithm for 17 TSP problems of TSPLIB

Fig.3 shows the fitness curve,and it can be seen from the figure that the algorithm can converge in shorter iterations,indicating the DLSO algorithm has a strong local optimization ability;while the algorithm can still further optimize in the late iterations,indicating the DLSO algorithm has a strong global optimization ability,not easy to fall into local extremes.Fig.4 shows the route obtained by the DLSO algorithm in the Pcb442 problem.

The IVRS+2opt[10],ACO+2opt and ACO+ABC[27]algorithms with good results in recent years were selected as comparisons to verify the effectiveness of the DLSO algorithm.Table 4 gives the comparison results on six TSPs.“—”means that there is no data in the literature,and boldface numbers mean the best value among the four algorithms.It can be seen from Table 4 that the DLSO algorithm is superior to other three algorithms in the optimal value and the average value.For the ACO+ABC algorithm,the DLSO algorithm can improve the accuracy of solution in the range of[1%,5%];for the ACO+2opt algorithm,DLSO can significantly improve the accuracy of solution on Eil51,KroA100 and D198 problems,especially for KroA100,the DLSO algorithm can improve about 10%;for the improved AC algorithm IVRS+2opt,DLSO improves the accuracy of solution about 0.5%on Eil51,KroA100 and D198.

Fig.3Curve evolution diagram of DPLO in Pcb442

Fig.4Tours obtained by DLSO in Pcb442

Table 4Comparison of the DLSO algorithm with other algorithms for six TSPs

4.2Experimental analysis of PDLSO algorithm

Because different computing devices will affect the acceleration performance of parallel algorithms,we divide the experiment into two cases according to different computing devices.Case 1:single computer with multi-process;Case 2:double computers of the same configuration with multi-process.Case 2 can be divided into two situations:wired connection and wireless connection according to the way two computers establish local area network(LAN).We first compare the results of the PDLSO and DLSO algorithms to verify the effectiveness of the PDLSO algorithm,then analyze the acceleration performance of the PDLSO algorithms in Case 1 and Case 2.The parameters of the PDLSO algorithm are shown in Table 5.

Table 5 PDLSO parameters setting

Case 1Single computer with multi-process

Table 6 shows the experimental results of a single computer,gives the results of serial DLSO,2-process PDLSO,3-process PDLSO and 4-process PDLSO,including the time of algorithms,mean value and standard deviation of the solution.In terms of time of the algorithm,PDLSO can significantly reduce the running time of the DLSO algorithm and achieve an approximately linear acceleration ratio.The mean and standard deviations of the solution are important criteria for measuring the quality of the solution,it can be seen from Table 6 that the PDLSO algorithm of 2-process and 3-process is basically consistent with the serial DLSO algorithm in terms of the quality of the solution,the accuracy of 4-process PDLSO solutions decreases due to fewer individuals in the sub-population,but the difference between 4-process PDLSO solutions and DLSO solutions is less than 0.5%.

Table 7 gives a more detailed description of the parallel performance of PDLSO in a single computer,whereSrepresents the parallel speedup ratio,which is obtained by(11);EFF represents the parallel efficiency,which is obtained by(12)[28].Among them,Tserialrepresents the running time of the serial algorithm,Tparallelrepresents the running time of the parallel algorithm,andPNrepresents the process number of the parallel algorithm.

Table 6 Comparison of the PDLSO in a single computer with serial DLSO for nine TSP problems

Taking line St70 in Table 7 as an example,the efficiency of the 2-process is 0.94,the 3-process is 0.91,and the 4-process is 0.84.It can be seen that for a fixed problem,as the number of processesPNincreases,the parallel efficiency EFF decreases.This is because the larger the processesPN,the greater the number of communication times comm,that is,the number of non-parallel parts of the algorithm increases,andTparallelincreases accordingly,however,the increase of processes has not brought about drastic changes in parallel efficiency EFF,because forTparallel,the time consumed by communication is relatively small.Taking the column 2-process PDLSO in Table 7 as an example,it can be seen that as the scale of the TSP increases,the speedup ratio and efficiency increase.Gustafson’s law[29]can give an intuitive explanation:as the size of the problem increases,the proportion of the communication part of the DLSO algorithm decreases.Fig.5 shows the parallel efficiency comparison of three TSPs with different city sizes.The above conclusion can be seen intuitively from Fig.5.It can be seen from the above analysis that PDLSO algorithm has a good parallel performance on the TSPs.

Table 7 Performance of PDLSO in a single computer of nine TSP problems

Fig.5Parallel efficiency comparison of St70,Ch150 and Lin318

Case 2Double computers of the same configuration with multi-process

In Case 1,we have proved that the results of PDLSO and DLSO are basically the same.Since different computing devices do not change the results of the PDLSO algorithm,we mainly analyze the impact of different computing devices on the acceleration performance of the PDLSO algorithm in Case 2.We utilize a router to establish an LAN between two computers.According to the connection mode,it can be divided into wired connection and wireless connection.The wired connection utilizes IEEE 802.3 protocols,and the wireless connection utilizes IEEE 802.11g protocols.The maximum transmission rate is 54 Mbps.The results of the PDLSO algorithm have been given in Case 1,here we mainly focus on the parallel acceleration of PDLSO on the double computers platform.The performance of double computers wired connection is shown in Table 8,the performance of double computers wireless connection is shown in Table 9.From Table 8 and Table 9,we can draw the same conclusion as that in Case 1:for a fixed problem,as the number of processesPNincreases,the parallel efficiency EFF decreases;as the scale of the TSP increases,the speedup ratio and efficiency increase.

Comparing Table 8 with Table 9,we find the acceleration performance of wireless connection and wired connection is basically the same.Comparing Table 7,Table 8,and Table 9,and taking the acceleration ratioSof the row D198 in the tables as an example,we obtain the parallel speedup ratio comparison in Fig.6.From Fig.6,it can be seen intuitively that the acceleration ratio of the double computers is lower than that of the single computer,but still achieves effective acceleration.According to the experiments in Case 1 and Case 2,we can see that in different computing devices,the PDLSO algorithm can significantly reduce the running time while ensuring the same accuracy as the DLSO algorithm.

Table 8Performance of PDLSO in double computers wired connection of nine TSP problems

Table 9Performance of PDLSO in double computers wireless connection of nine TSP problems

Fig.6 Parallel speedup ratio comparison of D198 in different platforms

5.Conclusions

This paper proposes the DLSO algorithm and the PDLSO algorithm for solving the TSP.The LSO algorithm is transformed into the DLSO algorithm that can solve the TSP by discrete coding,order crossover operator and C2-opt operator.The PDLSO algorithm divides the population into multiple sub-populations.Sub-populations run the DLSO algorithm in parallel through message passing interface(MPI),and connected by ring topological structure.Sub-populations transfer the optimal individuals between neighborhoods.Experiments on several benchmarks TSPs of different scales are carried out to test DLSO’s performance.The statistical results indicate that the DLSO algorithm can find the route close to the theoretical optimal in a reasonable time.The performance of the PDLSO algorithm is tested on a single computer with multi-process and double computers with multiprocess platforms respectively.By comparing the results with DLSO,we find the PDLSO algorithm can reduce the running time of the DLSO algorithm in an approximate linear acceleration way while ensuring that the quality of the solution is consistent with the DLSO algorithm.How to apply DLSO and PDLSO to larger scale TSPs and other combinatorial optimization problems is our future work.