Research On Parallel Multiple Ant Colony Optimization

Ant Colony optimization (ACO) is a meta-heuristic algorithm which designed from thereal-world behavior of ants. In nature, wayfinding process of single ant presents randomness,and when the ant populations constitute, wayfinding process will exist a clear-oriented.According to this phenomenon, M.Dorigo designed the ACO algorithm. According to thecharacteristics of ant pathfinding process, this algorithm was first applied to solve the travelingsalesman problem. Currently, ACO has been widely used to solve various combinatorialoptimization problems, such as: scheduling, assignment problem, etc.Since ACO proposed, numerous work has been committed to improving the performanceof ACO. Early work ACO is committed to improve the basic ant system (AS) algorithm, inorder to reduce the time to explore the path algorithm, and increase the stability of the algorithm.These works focused on adding restrictions and constraints on the algorithm, effectivelyenhance the performance of the algorithm.On the other hand, for the ACO algorithm, the strength which heuristic impact thealgorithm depends on the parameter settings. These studies can be broadly divided into twocategories: online tuning and offline tuning. ACO algorithm for each parameter affects theresult is an important issue since the ant colony algorithm to create. Statistics show that themajority of studies have chosen the parameters α, β and0as the research object, and theseworks studies how parameters control the pheromone update.However, such work is still a lack of a clear direction parameter modification. In this paper,we analyzed parameters of two improved ACO algorithm--Max-Min Ant System (MMAS)and ant colony system (ACS). To verify the validity of the modified parameters and providecontrast, for MMAS and ACS were increased2-opt, a total of four groups correction algorithmparameters analyzed. In this paper, the analysis of parameters include:(1) how the best-so-farsolution improved when parameters are modified;(2) to find a parameter setting, you can make at any stage in the path of exploring ants, can obtain a relatively high quality of the currentoptimal solution. According to the ACS algorithm analysis， we conclude that in all stages ofthe search path of ants there is always a parameter setting is more conducive to the developmentof higher quality solution ants. Meanwhile, in ACS, always there is not a constant parametersetting mode allows the ants to make the most appropriate path to build in the entire run of thealgorithm. On the other hand, for the MMAS research, we conclude that when algorithmrunning time is limited, MMAS algorithm parameters has a significant impact on anytimebehavior. This effect was stronger than the effect of ACS parameters on the algorithm. Moreover,to parameter β and m, the introduction of appropriate modification strategy can effectivelyimprove the anytime behavior of MMAS.Based on the basis of this study, we propose a combination of several parallel technologyparameter modification strategies: parallel pre-schedule MMAS (P-PSMMAS), parallel-collaborative correction MMAS (P-CCMMAS). Parallel optimization strategy has been tofocus on the exchange of populations, according to some information, pheromone matrixpartially shared. This paper argues that, through a multi-colony "trial and error" process, analgorithm for optimizing the parameters of the problem set and achieve oriented modifypheromone matrix algorithm can improve performance, accelerate convergence, and the burdenof smaller computing and communications. Experimental results show that the parallelparameter modifying strategy, the stability of the optimal solution maintain a high performance,and anytime behavior of the algorithm obtain a greater degree of improvement.