Authors: Davidović, Tatjana 
Jakšić Kruger, Tatjana 
Ramljak, Dušan
Šelmić, Milica
Teodorović, Dušan
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Parallelization strategies for bee colony optimization based on message passing communication protocol
Journal: Optimization
Volume: 62
Issue: 8
First page: 1113
Last page: 1142
Issue Date: 1-Aug-2013
Rank: M22
ISSN: 0233-1934
DOI: 10.1080/02331934.2012.749258
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: distributed memory multiprocessors | meta-heuristics | parallel execution | scheduling problems | swarm intelligence
Publisher: Taylor & Francis
Project: Advanced Techniques of Cryptology, Image Processing and Computational Topology for Information Security 
Mathematical Modelas and Optimization Methods on Large-Scale Systems 
Graph theory and mathematical programming with applications in chemistry and computer science 
Computational Intelligence Techniques in Transportation and Communication Planning and Traffic Control 

Show full item record


checked on Jul 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.