Metaheuristics approximate solutions of NP-hard combinatorial optimization problems (COP) that require significant computing resources due to the exponential growth of the search space. A parallel algorithm provides an efficient approach to solve large COPs and leverage parallel high-performance computing (HPC) environments. The Ant Colony Optimization (ACO) is a population-based metaheuristic with an inherently parallel nature with outstanding time and performance results.

• Prerequisites

  • MPI library (OpenMPI)

• Install
  

conda install -c conda-forge openmpi gxx_linux-64 gcc_linux-64 

• Compile
  

mpicc -lstdc++ -lm -lpthread mpi_aco.cpp -o aco-mpi

• Run
  

mpirun -n 4 ./aco-mpi rl1889

• Prerequisites

  • CUDA-capable GPU.
  • NVIDIA CUDA Toolkit.

• Compile
  

nvcc -arch=sm_80 aco-tsp.cu -o aco-cuda

• Run

./aco-cuda

The instances folder contain several TSP benchmark instances from the TSPLIB benchmark library:

• rat575
• rat783
• pr1002
• rl1889
• fl3795

@article{ 
author  = {Jorge Banda-Almeida, Israel Pineda},
title   = {Parallel Ant Colony Optimization Using High Performance Computing with CUDA and MPI},
year    = {2021},
}