Affiliations: AGH University of Science and Technology, Krakow, Poland
Correspondence:
[*]
Corresponding author. Aleksander Byrski, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krakow, Poland. E-mail: olekb@agh.edu.pl.
Abstract: Solving difficult, usually NP-hard problems, requires metaheuristic-based approach. Such algorithms are very often demanding from the point of view of computational power. Therefore various approaches to parallelize or distribute such systems were made. Many of such algorithms are structurally very easy to parallelize, e.g. evolutionary ones. However, swarm computing algorithms, in particular ACO (Ant Colony Optimization), in order to be implemented properly must use a significant amount of global knowledge (pheromones matrix). Therefore strict parallelization/distribution strategies for ACO are difficult to work-out. In the presented paper we propose a novel approach for parallelization and distribution of the most important element of ACO, namely the pheromone table. Our prototype implementation is tested on a real-world HPC (High Performance Computing) infrastructure, with good observed scalability. At the end of this paper we present actual experimental results focusing on two class of problems, namely TSP (Travelling Salesman Problem) and VRPTW (Vehicle Routing Problem with Time Windows), using popular benchmarks.
Keywords: parallel and distributed computing, ant colony optimization, swarm intelligence, high performance computing
