Jakšić Kruger, Tatjana
|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||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:||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 Sep 16, 2022
checked on Sep 15, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.