Abstract

Although Ant Colony Systems (ACS) have gained much attention in last two decades but slow execution and convergence speed are still two challenges for these meta-heuristic algorithms. Many parallel implementations have been proposed for faster execution. However, most of available implementations use coarse-grained synchronization mechanisms that are not efficient and scalable. In this work, we have taken a fine-grained (ant-level) approach that is more efficient and scalable. We have used traveling salesman problem as a test case and have presented a parallel fine-grained implementation for shared-memory multi-core systems. Our experimental results show that our proposed parallel implementation can achieve considerably higher speedup values on modern multicore processors.

References

• M. Dorigo and L. M. Gambardella, "Ant colony system: A cooperative learning approach to the traveling salesman problem," Evolutionary Computation, IEEE Transactions on, vol. 1, no. 1, pp. 53–66, 1997.
• M. Pedemonte, S. Nesmachnow, and H. Cancela, "A survey on parallel ant colony optimization," Applied Soft Computing, vol. 11, no. 8, pp. 5181–5197, 2011.
• M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 26, no. 1, pp. 29–41, 1996.
• I. Ellabib, P. Calamai, and O. Basir, "Exchange strategies for multiple ant colony system," Information Sciences, vol. 177, no. 5, pp. 1248–1264, 2007.
• S. P. Tseng, C. W. Tsai, M. C. Chiang, and C. S. Yang, "A fast ant colony optimization for traveling salesman problem," in Evolutionary Computation (CEC), IEEE Congress on, pp. 1–6, 2010.
• M. Pedemonte and H. Cancela, "A cellular ant colony optimisation for the generalised Steiner problem," International Journal of Innovative Computing and Applications, vol. 2, no. 3, pp. 188–201, 2010.
• M. Randall and A. Lewis, "A parallel implementation of ant colony optimization," Journal of Parallel and Distributed Computing, vol. 62, no. 9, pp. 1421–1432, 2002.
• P. Delisle, M. Gravel, M. Krajecki, C. Gagné, and W. Price, "Comparing parallelization of an ACO: message passing vs. shared memory," in Second International Workshop on Hybrid Metaheuristics, 2005.
• P. Delisle, M. Krajecki, M. Gravel, and C. Gagné, "Parallel implementation of an ant colony optimization metaheuristic with OpenMP," in Proceedings of the 3rd European Workshop on OpenMP (EWOMP'01), Barcelona, Spain, 2001.
• M. S. F. Catalano and F. Malucelli, "Parallel randomized heuristics for the set covering problem," International Journal of Practical Parallel Computing, vol. 10, no. 4, pp. 113–132, 2001.
• E. G. Talbi, O. Roux, C. Fonlupt, and D. Robillard, "Parallel ant colonies for the quadratic assignment problem," Future Generation Computer Systems, vol. 17, no. 4, pp. 441–449, 2001.
• E. Alba, G. Leguizamon, and G. Ordonez, "Two models of parallel ACO algorithms for the minimum tardy task problem," International Journal of High Performance Systems Architecture, vol. 1, no. 1, pp. 50–59, 2007.
• H. Bai, D. OuYang, X. Li, L. He, and H. Yu, "MAX-MIN ant system on GPU with CUDA," in Innovative Computing, Information and Control (ICICIC), 2009 Fourth International Conference on, 2009, pp. 801–804.
• M. Rahoual, R. Hadji, and V. Bachelet, "Parallel ant system for the set covering problem," Ant Algorithms, pp. 249–297, 2002.
• M. Middendorf, F. Reischle, and H. Schmeck, "Multi colony ant algorithms," Journal of Heuristics, vol. 8, no. 3, pp. 305–320, 2002.
• R. Michel and M. Middendorf, "An island model based ant system with lookahead for the shortest supersequence problem," in Parallel Problem Solving from Nature—PPSN V, pp. 692–701, 1998.
• R. Michel and M. Middendorf, "An ACO algorithm for the shortest common supersequence problem," in New ideas in optimization, 1999, pp. 51–62.
• D. A. L. Piriyakumar and P. Levi, "A new approach to exploiting parallelism in ant colony optimization," in Micromechatronics and Human Science, 2002. MHS 2002. Proceedings of 2002 International Symposium on, pp. 237–243, 2002.
• C. Twomey, T. Stützle, M. Dorigo, M. Manfrin, and M. Birattari, "An analysis of communication policies for homogeneous multi-colony ACO algorithms," Information Sciences, vol. 180, no. 12, pp. 2390–2404, 2010.
• Q. Lv, X. Xia, and P. Qian, "A parallel aco approach based on one pheromone matrix," Ant Colony Optimization and Swarm Intelligence, pp. 332–339, 2006.
• J. Fu, L. Lei, and G. Zhou, "A parallel ant colony optimization algorithm with gpu-acceleration based on all-in-roulette selection," in Advanced Computational Intelligence (IWACI), 2010 Third International Workshop on, pp. 260–264, 2010.
• K. D. Nguyen and A. G. Bourgeois, "Ant colony optimal algorithm: fast ants on the optical pipelined r-mesh," in Parallel Processing, 2006. ICPP 2006. International Conference on, pp. 347–354, 2006.
• D. Merkle and M. Middendorf, "Fast ant colony optimization on runtime reconfigurable processor arrays," Genetic Programming and Evolvable Machines, vol. 3, no. 4, pp. 345–361, 2002.
• B. Scheuermann, K. So, M. Guntsch, M. Middendorf, O. Diessel, H. ElGindy, and H. Schmeck, "FPGA implementation of population-based ant colony optimization," Applied Soft Computing, vol. 4, no. 3, pp. 303–322, 2004.
• Q. Tan, Q. He, and Z. Shi, "Parallel Max-Min Ant System Using MapReduce," in Advances in Swarm Intelligence, vol. 7331, Y. Tan, Y. Shi, and Z. Ji, Eds. Springer Berlin / Heidelberg, pp. 182–189, 2012.
• Y. Yang, X. Ni, H. Wang, and Y. Zhao, "Parallel Implementation of Ant-Based Clustering Algorithm Based on Hadoop," in Advances in Swarm Intelligence, vol. 7331, Y. Tan, Y. Shi, and Z. Ji, Eds. Springer Berlin / Heidelberg, pp. 190–197, 2012.
• E. L. Lawler, "The traveling salesman problem: a guided tour of combinatorial optimization," WILEY-INTERSCIENCE SERIES IN DISCRETE MATHEMATICS, 1985.
• C. Blum, J. Puchinger, G. R. Raidl, and A. Roli, "Hybrid metaheuristics in combinatorial optimization: A survey," Applied Soft Computing, 2011.