School of Business Administration,South China University of Technology,Guangzhou 510641,China

Efficienc improvement of ant colony optimization in solving the moderate LTSP

Munan Li*

School of Business Administration,South China University of Technology,Guangzhou 510641,China

In solving small-to medium-scale travelling salesman problems(TSPs)of both symmetric and asymmetric types,the traditional ant colony optimization(ACO)algorithm could work well,providing high accuracy and satisfactory efficienc.However, when the scale of the TSP increases,ACO,a heuristic algorithm, is greatly challenged with respect to accuracy and efficienc.A novel pheromone-trail updating strategy that moderately reduces the iteration time required in real optimization problem-solving is proposed.In comparison with the traditional strategy of the ACO in several experiments,the proposed strategy shows advantages in performance.Therefore,this strategy of pheromone-trail updating is proposed as a valuable approach that reduces the time-complexity and increases its efficienc with less iteration time in real optimization applications.Moreover,this strategy is especially applicable in solving the moderate large-scale TSPs based on ACO.

ant colony optimization(ACO);travelling salesman problem(TSP);time-complexity of algorithm;pheromone-trail updating.

1.Introduction

The ant colony optimization(ACO)algorithm,an abstraction of ant colony foraging behavior,embodies the distributed-computing and self-organization features of group behavior.Since Dorigo firs used the ACO algorithmtosolvethe travellingsalesmanproblem(TSP),there have been many attempts to apply ACO to different combinational optimization problems,such as the job-shop scheduling problem,quadratic assignment problem,path planning,network routing optimization,and optimization of control parameters[1–6].In recent years,some scholars have extended ACO to continuous function optimization and achieved relatively satisfactory results[7].

Large-scale TSP is a typical NP-C problem[8,9].At present,algorithms for solving TSP can be divided into two categories:accuracy algorithms and heuristic algorithms[9].Usually,a structural algorithm is used to solve small TSPs by findin the optimal solution;while a heuristic algorithm is adopted to solve medium and large TSPs. Several heuristic algorithms for solving the TSP come from nature-inspired swarm intelligence,such as the ACO model,PSO model,and evolutionary computation model [9–11].A heuristic algorithm model generally follows simple control rules,attempting to obtain a satisfactory solution through multiple iterations and random walk strategies.To accelerate the convergence rate and accuracy of the algorithm,quite a few scholars used hybrid algorithms to improve the current heuristic calculation mode[12–14].Generally speaking,in TSPs,an object with 100–1 000 nodes is define as a medium-scale TSP(MTSP), while objects with over1 000 nodesbelongto a large-scale TSP(LTSP).So far,the largest recorded LTSP has been the large-scale very large scale integration(VLSI)solder joint path optimization with 85 900 nodes.Current single heuristic algorithms have the disadvantages of slow convergence and poor accuracy in solving LTSP.Thus,when dealing with LTSP,currently available single heuristic algorithms need to be further mixed and improved[15–17].

Overall,there are many research works on the applications of ACO and other heuristic algorithms,but the literature on efficien y and reducing the time-complexity of ACO algorithms is relatively few.Mohammed compared the performances of the foraging algorithm and the evolution algorithm,but the benchmark for this test was only the set of continuous functions,and the comparison did not consider combination or discrete optimization field[18].Zhou discussed the runtime of ACO based on a constrained-modelmax-min ant algorithm(MMAA)andthought that the efficien y of ACO could be observed and measured under constrained situations[19].

From the current literature,there is a common view that ACO has certain advantages in solving the small-scale TSP,but with an increasing number of TSP nodes,the algorithm accuracy and efficien y decreases rapidly.Therefore,the basic ACO must be combined with other algorithms to solve real application problems[20].In fact, many issues pertaining to basic ACO remain secret and are waiting to be unveiled,e.g.the convergence,efficien yand complexity of ACO.In this paper,we attempt to explore the time-complexity of ACO and fin an efficien strategy to reduce the run-time of basic ACO in a real discrete optimization process.

2.Basic ACO algorithm in solving large-scale TSP

The basic ACO algorithmhas the advantagesof quickconvergenceandhighaccuracywhensolvingsmallscaleproblems.However,when the node number of the TSP reaches or exceeds 100,the basic ACO algorithm can only fin a local optimization solution most of the time,and its rate of convergence decreases as the number of nodes increases, which makes it very difficul to meet the requirements of combinatorial optimization.

2.1Basic concept and steps of ACO algorithm

The ACO algorithm’s basic conceptual computation steps are described[1,2]as follows.

Definitio1TSP:SupposeC={c1,c2,...,cn}is a set ofNnodes,L={lij|ci,cj∈C}is the set of connections between every two nodes in setC,anddij(i,j=1,2,...,n)is theEuclideandistance oflij,then

G=(C,L)is a directed graph.The TSP for this problem is to fin the shortest Hamiltonian ring,i.e.the shortest closed circle that traversesNelements amongConly once.The TSP can be divided into symmetric and asymmetric types,according to whether the distance between any two nodes is the same or not.Here,we study only the symmetric TSP.

It is assumed thatfi(t)is the number of ants at nodeiat momentt,τijis the pheromone value of path(i,j)at momentt,nis the node scale of TSP,andmis the total number of ants,then

The path residual information of nodes at momenttis given by the following formula:

During the search procedure,antk(k=1,2,...,m) calculates the transition probability based on the information amount of each path and its heuristic function information,as shown by

In(4),allowedk={C-tabuk}indicates the city node set fromwhich antkcan chooseelements for the next step,αis the pheromone information factor or weight,representing the relative importance of pheromone in the path, andβis the expectation factor,representing the influenc ofdistance betweentwo nodeson the decisionmade byantk.The general form of the heuristic function is shown as

To avoid the impact of residual information in the path thatwouldoverwhelmthe heuristicfunctioncompletely,in everyiterativeprocess,itis necessarytoupdatetheresidual pheromone trail when all ants finis traversing all nodes. The pheromoneupdate strategy refers to a characteristic of human memory by which,as time passes,old memories fade away or are even forgotten.Therefore,the pheromone evaporation rateρis added to ACO,and the pheromone update rule is given by(6)and(7).

Dorigo and other scholars proposed three different models identifie by their different pheromone updating strategies:the ant-cycle model,ant-quantity model,and ant-density model,whose updating formulae are given respectively by

In most research works on ACO algorithms and their applications,the ant-cycle model is selected as the most favorable pheromone trail updating strategy[2,21,22]. Therefore,we also chose the ant-cycle model as the object of the control experiment.

2.2Time complexity analysis of ACO algorithm

The complexity of an algorithm is frequently mentioned in the literature,and this term actually includes both time complexityand space complexity.Time-complexityanalysis aims to determine the computing time scale,which is usually used to explain the number of program execution steps and,thus,to estimate the algorithm’s efficien y.

Assume thatnis the node scale of TSP,mis the number of ants,and the maximum iteration isImax.Then,the time complexity analysis of the ACO algorithm for the solution of the TSP is shown in Table 1.

Table 1 Time complexity analysis of ACO algorithm

From the algorithm steps in Table 1,it can be seen that afterImaxgenerations,the time complexityof the standard ACO algorithm can be estimated by

Under a similar method of estimation,the space complexity of the ACO algorithm seems simpler,shown as

From(11)and(12),if we choose a more appropriate iteration and ant number,the space complexity and time complexity of the algorithm can be partially decreased in real optimization applications.Although the time complexity and space complexity may be only slightly reduced,there is a positive significanc and practical value for solving LTSP.For example,when dealing with the large-scale welding path optimization problem with over 10 000 solder joints in VLSI,if the iteration time can be reducedunder some situations,the real runningtime of the algorithm may decrease somewhat.

Methods to reduce ACO running time include discovering the appropriate iteration time and identifying the minimum population size of the ant colony.For basic ACO, Dorigo proposed three pheromone trail updating models. In practical applications,most scholars choose the antcycle model recommended by Dorigo because the antcycle model has better performance compared with the othertwo updatingstrategies[1,2].We asked the following question:can a better pheromonetrail updatingstrategy be found?A better pheromone updating model means that under the same environment,the ACO convergence rate can be increased,while the algorithm accuracy remains unchangedor the loss of accuracy can be ignored.This updating strategy seems to be of little significanc to smallto medium-scale TSP problems.However,in solving the large-scale combination optimization problem,when the iteration number of the running algorithm can be reduced from 1 000 to 500 with almost unchanged accuracy,in a sense,the time complexity of the algorithm actually has decreased by 50%.

Although the literature comparing the three traditional pheromone updating models(ant-cycle,ant-quantity and ant-density)is limited,experientially,it appears that it is possible to speed up the convergence of ACO when the greedy philosophy,a classic global pheromone updating model,is added to the ant-cycle model;the accuracy may also be satisfying.Therefore,a novel strategy for global pheromone updating,named ant-cycle-quantity,is proposed as given by(13),which is a hybrid model combing the global and local updating pheromone trail approaches in ACO.

In(13),Qhas the same meaning as those traditional strategies of pheromone updating,representing one constant of the total pheromone.Lkrepresents the passing length of thekth ant.Thedijis the distance between theith point and thejth point.λis a constant or a random function that is greater than 1.In the traditional antcycle model,the pheromone trail is updated evenly in theKth(t)path,without considering the local path information,while the ant-quantity model only considers the local path weight,depending on the greedy algorithm instead of thewhole-pathinformation.Based onwhole-pathinformation,the ant-cycle-quantity model takes the local path information into consideration,implementing this conside-ration in the pheromone trail updating computational step of the basic ACO algorithm.

3.Control experiments solving the TSP based on the ant-cycle-quantity model

3.1 Experimental design

First,we chose the benchmark data from TSPLIB95 and select(pr1002,d1291,fl1400 as the test set for the LTSP. At the same time,to observe the possible fluctuatio in efficien y when going from small scale to large scale,we chose(bays29,ctsp31,ch130)as the test set for the solution of the small-to medium-scale TSP.The simulation softwarefor the experimentis Matlab 7.0and the hardware is a LENOVA laptop(CPU:M460,2.53 MHZ,Memory: 4 GB)and a TOSHIBA laptop(CPU:M370,2.40 MHZ, Memory:2GB).Theparameterschosenforthe basicACO algorithm are shown in Table 2.

Table 2 Experimental parameters

The iteration number of the ant-cycle-quantity model is half that of the typical ant-cycle model.In the small-to medium-scale TSP solution experiment,the iteration number of the ant-cycle model was set to 100,and the iteration number of the ant-cycle-quantity model was 50.To solve the LTSP,the iteration number of ant-cycle was set to 200, and the iteration number of ant-cycle-quantity was equal to 100.The results of the experiment with the model of ant-cycle-quantityare shown in Fig.1–Fig.12.

Fig.1 The shortest length vs average length of path(Bays29,iteration=50,ant-cycle-quantity)

Fig.2 Path planning of Bays29 based on ant-cycle-quantity(iteration=50)

Fig.3 Shortest length vs average length of path(Ctsp31,iteration=50,ant-cycle-quantity)

Fig.4 Path planning of Ctsp31 based on ant-cycle-quantity(iteration=50)

Fig.5 The shortest length vs average length of path(ch130,iteration=50,ant-cycle-quantity)

Fig.6 Path planning of ch130 based on ant-cycle-quantity(iteration=50)

Fig.7 The shortest length vs average length of path(fr1400,iteration=100,ant-cycle-quantity)

Fig.8 Path planning of fr1400 based on ant-cycle-quantity(iteration=100)

Fig.9 The shortest length vs average length of path(d1291,iteration=100,ant-cycle-quantity)

Fig.10 Path planning of d1291 based on ant-cycle-quantity(iteration=100)

Fig.11 The shortest length vs average length of path(pr1002,iteration=100,ant-cycle-quantity)

Fig.12 Path planning of pr1002 based on ant-cycle-quantity(iteration=100)

3.2 Analysis of the comparison experiments between the two models

Results of the control experiments are shown in Table 3 and Table 4.

From Table 3,while solving the selected small-to medium-size TSPs,the ant-cycle-quantity model shortens the running time of basic ACO by 50%with accuracy almost unchanged.

From the experimental results shown in Table 4,we could easily reach the same conclusion that the ant-cyclequantity model requires fewer iterations than the traditional ant-cycle model to achieve similar accuracy in solving LTSPs.When solving LTSPs based on basic ACO,the global optimization solution is very difficul to reach. Under the same situation,except for the iteration number, these two distinct strategies can achieve very similar optimal results,equivalent to approximately 80%of the theoretical optimal value.In fact,whether the basic ACO algorithm can eventually reach the theoretical optimal value in solving the large-scale,or even the medium-scale,TSP remains to be proven[21,22].

To further validate the results of the control experiments,the statistical product and service solutions(SPSS) tool was used for the one-way analysis of variance on the simulation results shown in Table 3 and Table 4.

Table 3 Result of solving small-to medium-scale TSP(ant-cycle&ant-cycle-quantity)

Table 4 Result of solving lTSP(ant-cycle&ant-cycle-quantity)

The analysis of variance for the experimental results for the solution of small-to medium-size TSPs,as shown in Table 3,is given below.

(i)All experimentaldata(bays29,ctsp31,ch130)shown in Table3 canpass thenormalityandhomogeneityhypothesis test.Therefore,the analysis of varianceis conceivable.

(ii)With a significanc level of 0.05(α=0.05),the results of the analysis of variance(ANOVA)are shown in Table 5,Table 6 and Table 7.

Table 5 ANOVA(Bays29)

Table 6 ANOVA(ctsp31)

Table 7 ANOVA(ch130)

From the ANOVA results in Table 5,Table 6 and Table 7,the actual significanclevels are higher than the given significanc level.Therefore,the results of thesecontrol experiments show that the control experiment passes the test of significance From these results,the antcycle-quantity model seems to be more efficien in solving small-to medium-scaleTSPs than the classic ant-cycle model.

The conclusions from the analysis of variance regarding the solution of LTSPs,shown in Table 4,are as follows.

(i)All data from the comparative experiments(pr1002, d1291,fl1400 showninTable4canpassthenormalityand homogeneity hypothesis test;therefore,analysis of variance could be undertaken.

(ii)With a significanc level of 0.05(α=0.05),the results of the analysis of variance are shown in Table 8, Table 9 and Table 10.

Table 8 ANOVA(pr1002)

Table 9 ANOVA(d1291)

Table 10 ANOVA(fl1400

From ANOVA results in Table 8,Table 9 and Table 10, in solving the selected LTSPs,the ant-cycle-quantity model can reach similar accuracy to the ant-cycle model in half the running time.In a sense,the results of the control experiments show that the ant-cycle-quantity model seems to be more efficien than the classic ant-cycle model in solving TSPs and,in particular,more useful and valuable in solving LTSPs,requiring fewer iterations to reach similar optimal values,even when only the local optimal solution is reached.

4.Theoretical analysis of ant-cycle-quantity model

4.1Global convergence analysis of ant-cycle-quantity model

Gutjahr firs provedthe convergenceof ACO from the perspective of directed graph theory under a set of predefine situations[23].St¨uezle and Dorigo proposed a new MAXMIN model of the ACO algorithm and proved that the algorithm could reach the optimum solution when the computation time sequence of the ACO algorithm became infi nite[24].Duan define the firs reaching-time conceptual frameworkforthe ACO algorithmand suggestedthat if the ACOalgorithmwas usedforoptimumsolutiongtimes,the probability of the optimum solution being touched at least once before the moment wasg?T0,and the probability of that having happenedwas no less than(1?1/c),whereT0represented the time for the basic ACO algorithm to finis one iteration[25].

Theorem 1When the path vectorC(t)of an individualant nearlyapproachestheoptimumpathvectorC?(t) everywhere in the search periodt,and ift→∞,its evolutionary process can be taken as the inhomogeneous Markov chain,and the residual pheromone vectorτ(t) tends toward the optimal valueτ?(A.S.),whereA.S.means almost surely,shown as

ProofIn a sense,the distribution of search paths in iteration(t?1)only depends onignoring the influenc of the heuristic function based on the distance matrix.However,it is easy to reason thatare the determinants of the distribution ofby the rule of pheromone trail updating. Therefore,the probability distribution ofwholly depends onWhen the set of the path vector belongs to the finitset,the optimal path vector also belongs to the finitset.Then,whencan be considered equivalent to

This theorem can partly explain why the convergence speedofthe ant-cycle-quantitymodelis faster thanthe antcycle model.However,the upper and lower bounds of the convergence speed on this new model remain difficul to define so the model must be further explored in a subsequent study.

4.2Regarding the full path adjustment factorλ

The full path adjustment factor introduced in this paper is an empirical valueλ,and it is difficul to comprehensively analyze the impact of this factor on the model.The value range ofλis calculated by

From(15),after each iteration,the update amplitude of the pheromone track is adjusted byλ;thus,it is called thefull path adjustment factor.Whenλ＞Lmax,the amplitude of pheromone updating is less than that of the antcycle model.Thus,a general and empirical recommendation range ofλis[1,Lmax).

In addition,if we relax the restrictions of(λ≥1)and allowλ∈(0,+∞),then when(16)is constructed,the ant-cycle-quantity model can be approximated as the traditional ant-quantity model.

Similarly,when(17)is constructed,the ant-cyclequantity model can be approximatedby another traditional model:the ant-density model.

From the above reasoning,the new strategy of pheromone trail updating sounds better in terms of the generalization ability,and the three traditional models of pheromonetrail updatingin the ACO algorithm(ant-cycle, ant-quantity and ant-density)can be summarized as special cases of the new strategic model.Although there have been many improved models for pheromone trail updating,e.g.the elitist ant system(EAS),reinforcement learning approach,MAX-MIX ant system,strong local search, fruit fl optimization[2,21,26–28],the ant-cycle-quantity model may still be helpful to deeply understand the timecomplexityof the basic ant colonyoptimization algorithm.

5.Conclusions

Solving large-scale combinatorial optimization problems is the common challenge for all natural heuristic algorithms.In this paper,we explore the computational efficien y of the basic ACO and propose a novel strategy of pheromone trail updating,called the ant-cycle-quantity model.Through several simulation experiments,the new model shows better performance compared with the traditional ant-cycle model.In fact,the three models of pheromone trail updating in traditional ACO—ant-cycle, ant-quantity and ant-density—can be regarded as the special cases of the new model.Therefore,the ant-cyclequantity model seems to have better generalization ability. Although the results of comparison experiments are somewhat exciting and even somewhat amazing,the theory for the analysis of ant-cycle-quantityis still not strong enough andrequiresfurtherexplorationinfuturework.Inaddition, more comparisons and combinations with other improved ACO models and heuristic algorithms should be considered in the next work.

[1]M.Dorigo,V.Maniezzo,A.Colorni.Ant system:Optimization by a colony of cooperating agents.IEEE Trans.on Systems,Man and Cybernetics—Part B,1996,26(1):29–41.

[2]M.Dorigo,T.Sti¨utzle.Ant colony optimization.Cambridge: MIT Press,2004.

[3]J.B.K.Michael,B.Jean-Bernard,K.Laurent.Ant-like task and recruitment in cooperative robots.Nature,2000, 406(6799):992–995.

[4]G.F.Deng,W.T.Lin.Ant colony optimization-based algorithmfor airlinecrew scheduling problem.Expert Systems with Applications,2011,38(5):5787–5793.

[5]Z.G.Ren,Z.R.Feng,A.M.Zhang.Using ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem.Information Sciences, 2012,182(1):15–29.

[6]H.Ergezer,K.Leblebicioglu.Pathplanning for UAVs for maximum information collection.IEEE Trans.on Aerospace and Electronic Systems,2013,49(1):502–520.

[7]K.Socha,M.Dorigo.Ant colony optimization for continuous domains.European Journal of Operational Research,2008, 185(3):1155–1173.

[8]B.Manthey.On approximating multicriteria TSP.ACM Trans. on Algorithms,2012,8(2):1–17.

[9]M.Osca,D.F.Javier,etal.Combinatorial complexity problem reduction by the use of artificia vaccines.Expert Systems with Applications,2013,40(5):1871–1879.

[10]T.K¨otzing,F.Neumann,H.R¨oglin,et al.Theoretical analysis of two ACO approaches for the traveling salesman problem.Swarm Intelligence,2012,6(1):1–21.

[11]Y.Marinakisa,M.Marinaki.A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem.Computers&Operations Research,2012, 37:432–442.

[12]N.Yuichi,K.Shigenobu.A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem.INFORMS Journal on Computing,2012,25(2):346–363.

[13]G.F.Dong,W.W.Guo,T.Kevin.Solving the traveling salesman problem using cooperative genetic ant systems.Expert Systems with Applications,2012,39(5):5006–5011.

[14]N.Zhao,Z.L.Wu,Y.Q Zhao,et al.Ant colony optimization algorithm with mutation mechanism and its applications.Expert Systems with Applications,2012,37(7):4805–4810.

[15]M.C.Pintea.Parallel ACO with a ring neighborhood for dynamic TSP.Journal of Information Technology Research, 2012,5(4):1–13.

[16]M.Mavrovouniotis,S.X.Yang.A memetic ant colony optimization algorithm for the dynamic travelling salesman problem.Soft Computing,2011,15(7):1405–1425.

[17]X.F.Zhou,R.L.Wang.Self-evolving ant colony optimization and its application to traveling salesman problem.International Journal of Innovative Computing,Information and Control,2012,8(12):8311–8321.

[18]E.A.Mohammed.Performance assessment of foraging algorithms vs.evolutionary algorithms.Information Sciences, 2012,182(1):243-263.

[19]Y.R.Zhou.Runtime analysis of an ant colony optimization algorithm for TSP instances.IEEE Trans.on Evolutionary Com-putation,2009,13(5):1083–1092.

[20]Y.Zhang,M.Zhang,X.Q.Li,etal.Some practicalsolutions to the uncertainties of the ant colony optimization.International Journal of Computer Applications in Technology,2012,43(4): 327–334.

[21]M.Dorigo,C.Blum.Antcolony optimizationtheory:asurvey.Theoretical Computer Science,2005,344(2/3):243–278.

[22]M.B.Chandra,R.Baskaran.A survey:ant colony optimization based recent research and implementation on several engineering domain.Expert Systems with Applications,2012, 39(4):4618–4627.

[23]W.J.Gutjahr.ACO algorithm with guaranteed convergence to the optimal solution.Information Processing Letters,2002, 82(3):145–153.

[24]T.St¨utzle,M.Dorigo.A short convergence proof for a class of ant colony optimization algorithms.IEEE Trans.on Evolutionary Computation,2002,6(4):358–365.

[25]H.B Duan,D.B.Wang.Research and improvement on the global convergence of ant colony algorithm.Systems Engineering and Electronics,2004,26(10):1506–1509.(in Chinese)

[26]T.St¨utzle,H.H.Hoos.MAX-MIN ant system.Future Generation Computer Systems,2000,16(8):53–66.

[27]M.N.Li.Three-dimensional path planning of robots in virtual situations based on an improved fruit floptimization algorithm.Advances in Mechanical Engineering,2014,314797: 1–12.(DOI:10.1155/2014/314797)

[28]L.M.Gambardella,R.Montemanni,D.Weyland.Coupling ant colony systems with strong local searches.European Journal of Operational Research,2012,220(3):831–843.

Biographies

Munan Liwas born in 1974.He received his B.S. degree from North China University of Technology in 1997,M.S.degree and Ph.D degree from South China University of Technology in 2002 and 2006,respectively.He is now working in South China University of Technology.His current research interests include operation management,information technology etc.

E-mail:limn@scut.edu.cn

10.1109/JSEE.2015.00142

Manuscript received September 28,2014.

*Corresponding author.

This work was supported by the Fundamental Research Funds for the Central Universities(2015XZD15),the Soft Science Research Project of Guangdong Province(2015A070704015),the Guangdong Province Key Laboratory Open Foundation(2011A06090100101B),and the Technology Trading System and Science&Technology Service Network Construction Project of Guangdong Province(2014A040402003).