Keywords: metaheuristics, parallel computing, high-performance computing, ant colony optimization, message passing interface, combinatorial optimization problems.

Parallelization of metaheuristics using High-Performance Computing (HPC) provides a suitable environment to approximate large NP-hard combinatorial optimization problems (COPs). The Ant Colony Optimization (ACO) is a population metaheuristic with outstanding time and performance results. This algorithm mimics the indirect communication and self-organization capabilities of ants. In ACO, each ant is an autonomous construction procedure, and builds partial solutions to share with the rest of the colony. The combination of ants results in inherent parallel behaviour that enables the evaluation of complex problems. This behaviour has motivated the creation of algorithms that exploit parallel architectures. This paper accelerates ACO using Message Passing Interface (MPI) and HPC infrastructure. The MPI-ACO parallelization follows the master-slave model with coarse granularity. The algorithm divides the number of ants into different processors that simultaneously create local solutions and iteratively approximate the optimal solution. We evaluate the algorithm using three COPs, the travelling salesman problem (TSP), the job shop scheduling problem (JSP), and image segmentation. Each problem is encoded in MPI-ACO using the appropriate heuristic information and selection policies. The speedup, efficiency, and Karp-Flatt metric are used to evaluate the acceleration of the MPI-ACO using up to 32 cores, demonstrating the scalability of the MPI-ACO algorithm.

download the full-text of this paper (PDF, 7 pages, 232 Kb)

go to the previous paper
go to the next paper
return to the table of contents
return to the volume description