e-space
Manchester Metropolitan University's Research Repository

Decentralized Parallel Ant Colony Optimization for Distributed Memory Systems

Lloyd, Huw (2019) Decentralized Parallel Ant Colony Optimization for Distributed Memory Systems. In: IEEE Scalable Computing and Communications Conference (ScalCom) 2019, 20 August 2019 - 23 August 2019, Leicester, UK. (In Press)

[img]
Restricted to Repository staff only

Download (1MB)

Abstract

Ant Colony System (ACS) is a well-established variant of the Ant Colony Optimization (ACO) nature inspired metaheuristic for solving combinatorial optimization problems. We present the DMACS (Distributed Memory Ant Colony System) algorithm, which is a parallelization of ACS for distributed memory architectures. The system is decentralized, with each processor running an identical agent process which administers a part of the pheromone matrix used to record the movements of simulated ants over a graph. We evaluate a Message Passing Interface (MPI) implementation of the algorithm on the well-known Travelling Salesman Problem (TSP), running on a distributed memory cluster. The results show that the algorithm scales at least as well as previous agent-based distributed implementations of ACS, without the need to sacrifice core features of the algorithm such as local search. However, our results also demonstrate that scaling the ACS algorithm to large numbers of processes in distributed memory architectures remains a significant challenge.

Impact and Reach

Statistics

Downloads
Activity Overview
4Downloads
38Hits

Additional statistics for this dataset are available via IRStats2.

Actions (login required)

Edit Item Edit Item