Parallelization strategies for bee colony optimization based on message passing communication protocol
- 29 January 2013
- journal article
- research article
- Published by Taylor & Francis in Optimization
- Vol. 62 (8) , 1113-1142
Abstract
The Bee Colony Optimization (BCO) algorithm is a meta-heuristic that belongs to the class of biologically inspired stochastic swarm optimization methods, based on the foraging habits of bees in nature. BCO operates on a population of solutions, and therefore, it represents a good basis for parallelization. The main contribution of this work is the development of new and efficient parallelization strategies for BCO. We propose two synchronous and two asynchronous parallelization strategies for a distributed memory multiprocessor architecture under the Message Passing Interface (MPI) communication protocol. The first synchronous strategy involves independent execution of several BCO algorithms, while the second one implements cooperation between these algorithms. The asynchronous strategies are implemented in two ways: with centralized and non-centralized communication controls. The presented experimental results, addressing the problem of static scheduling independent tasks on identical machines, show that our parallel BCO algorithms provide excellent performance. As for the case of independent execution, a significant speedup is obtained while preserving the solution quality. Compared to the sequential execution, cooperative strategy leads to better quality solutions within the same amount of wall-clock time, as long as it is applied to a modest number of processors engaged in parallel BCO execution. As this number increases, asynchronous strategies outperform the other ones with respect to both solution quality and running time.Keywords
This publication has 37 references indexed in Scilit:
- A survey on parallel ant colony optimizationApplied Soft Computing, 2011
- Bee colony optimization for the p-center problemComputers & Operations Research, 2011
- A parallel improved ant colony optimization for multi-depot vehicle routing problemJournal of the Operational Research Society, 2011
- Locating inspection facilities in traffic networks: an artificial intelligence approachTransportation Planning and Technology, 2010
- Honey-bee mating optimization (HBMO) algorithm for optimal reservoir operationJournal of the Franklin Institute, 2007
- Parallel variable neighbourhood search algorithms for job shop scheduling problemsIMA Journal of Management Mathematics, 2007
- A Parallel Ant Colony Algorithm for Bus Network OptimizationComputer-Aided Civil and Infrastructure Engineering, 2006
- Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systemsComputers & Operations Research, 2006
- Parallel Metaheuristics Applications2005
- Parallelization strategies for Ant Colony Optimization1998