Performance Analysis and Tuning for Parallelization of Ant Colony Optimization Using Open MP
Ahmed A. Abouelfarag · International Journal of Swarm Intelligence and Evolutionary Computation · 2015
Abstract. Ant colony optimization algorithm (ACO) is a soft computing metaheuristic that belongs to swarm intelligence methods. ACO has proven a well performance in solving certain NP-hard problems in polynomial time. This paper proposes the analysis, design and implementation of ACO as a parallel metaheuristics using the OpenMP framework. To improve the efficiency of ACO parallelization, different related aspects are examined, including schedul-ing of threads, race hazards and efficient tuning of the effective number of threads. A case study of solving the traveling salesman problem (TSP) using different configurations is presented to evaluate the performance of the pro-posed approach. Experimental results show a significant speedup in execution time for more than 3 times over the sequential implementation.