A Research On Parallelization Of Ant Colony Optimization

ACO(Ant Colony Optimization), as a meta-heuristic approach, although it has not got any solid theoretical foundation, has exhibited it's excellent performance and efficiency on solving a great lot of NP-hard problems. ACO appeals to many researchers extending and improving it, and it is in its boosting stage.Based on investigation about ACO and it's parallelization literature, this article presents and implements some new parallelization strategies of ACO, whose idea is that multiple ant colonies share and utilize only one pheromone matrix during solution construction and pheromone update. We apply this idea to some extension of ACO algorithms, such as MMAS and ACS.In this paper, as an example, we mainly discuss ACS and MMAS's parallelization and describe the algorithm's design and programming. Further more, we present a lot of results of applying to mass symmetric traveling salesman problems, and give comparisons with the relevant sequential version when running under the same computing environment. Finally we show some comparisons among the parallel ACO algorithms.The experimental results indicate, relative to sequential ACO algorithms and existing parallel ones, at a certain extent, the strategies discussed in this article has an advantage and therefore can be viewed as powerful ways to combination and optimization problems.