Monday , December 17 2018

Parallelized Multiple Swarm Artificial Bee Colony
Algorithm (MS-ABC) for Global Optimization

Milos SUBOTIC, Milan TUBA
Faculty of Computer Science, Megatrend University,
29, Bulevar Umetnosti, Belgrade, 11070, Serbia
milos.subotic@gmail.com; tuba@ieee.org

Abstract: Swarm intelligence metaheuristics have been successfully used for hard optimization problems. After the initial introduction phase such algorithms are further improved by modifications and hybridizations. Parallelization is usually introduced for performance improvement and better resources utilization. In this paper we present an improved parallelized artificial bee colony (ABC) algorithm with multiple swarm inter-communication and learning that not only significantly improves computational time, but also improves the results. Proposed algorithm was tested on large set of standard benchmark functions and it outperformed the state-of-art ABC algorithm.

Keywords: Artificial bee colony, Optimization metaheuristics, Swarm intelligence, Parallelized algorithms, Nature inspired algorithms.

>>Full text
CITE THIS PAPER AS:
Milos SUBOTIC, Milan TUBA, Parallelized Multiple Swarm Artificial Bee Colony Algorithm (MS-ABC) for Global Optimization, Studies in Informatics and Control, ISSN 1220-1766, vol. 23 (1), pp. 117-126, 2014. https://doi.org/10.24846/v23i1y201412

  1. Introduction

Swarm intelligence algorithms became very popular in the past 20 years for efficiently finding suboptimal solutions to intractable optimization problems. Swarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. Swarm is defined as any loosely structured collection of agents that interact among each other. Swarm intelligence algorithms are trying to model social behaviour of real life agents such as viruses, birds, fish, ants, honeybees etc. Among the oldest swarm intelligence algorithm is the Ant Colony Optimization (ACO) inspired by behaviour of ants in the colony that was proposed by Dorigo [1] and is still being investigated and improved [2], [3], [4]. Also very successful and very well researched among older algorithms is Particle Swarm Optimization (PSO) that simulates social behaviour of ?ock of birds or school of ?sh. PSO was a start-up point for honey bee based optimization algorithms where Artificial Bee Colony (ABC) introduced by Karaboga [5] is a relatively new, but very successful [6], [7] optimization metaheuristics. Many new algorithms are introduced regularly like Firefly Algorithm (FA) [8], [9], Seeker Optimization Algorithm (SOA) [10], [11], [12] etc. as the research area continues to be active.

We are witnessing a dramatic change in computer architecture due to the multicore paradigm shift and every electronic device from cell phones to supercomputers confronts parallelism of unprecedented scale [13]. In general, a system of n parallel processors, each of speed k, is less efficient than one processor of speed n * k. However, the parallel system is usually much cheaper to build and its’ power consumption is significantly smaller. Problems caused by higher clock speeds are excessive power consumption, heat dissipation and current leakage. Power consumption and heat dissipation problems are critical for mobile devices, which are getting more important every year. To that end research in parallelization is of great importance. Seymour Cray used to say: “Would you rather plough a field with two strong oxen or 1024 chicken?”, but today’s hardware looks more like chicken. It has increasing number of low power cores.

Swarm intelligence algorithms have excessive potential for parallelization, either in terms of better results, faster convergence or shorter time for completing the run of an algorithm. Swarm intelligence algorithms always had long execution times since complex functions with large number of parameters are optimized. Every swarm unit has to evaluate objective function multiple times, so this makes them very appropriate for parallelization. By dividing the population into several processing threads, parallel implementations of population based algorithms produce quality results in a reasonable computational time. Since bio-inspired algorithms are not-deterministic, it is advisable to run them multiple times in order to get more accurate results. Any shortening of execution time of an algorithm that usually takes long to execute and that should be run multiple times, is welcome.

Algorithm can be parallelized in different manners. Pedemonte [14] provided the following taxonomy for parallel ant colony optimization (Table 1).

Table 1. Parallelization approaches taxonomy

Parallel approach
no. colonies One Many
cooperation no yes no yes
model master slave cellular parallel independent runs multi-colony

Very similar taxonomy can be applied to all population based heuristics. Speeding up the search is not the only incentive for parallelization of those algorithms; parallelization also provides a new search form often exceeding result quality of serial implementation of the same algorithm. Basically, approaches with built-in cooperation are aiming at better quality of results, while approaches without cooperation are aiming at shorter execution time of an algorithm.

Level of granularity can vary from finer grained parallelization such as the one where every agent has its dedicated thread, up to a very course, where whole population is divided into just few threads. Too fine grained implementation has one major disadvantage. There is a rather small portion of work for each agent, so extensive use of CPU time for creating threads and their synchronizations exceeds the benefits of parallel execution of the algorithm.

Master-slave models have one central process (master) that controls and delegates tasks to several other processes (slaves). Complexity of the tasks depends on the granularity of an approach, and can vary from evaluation of objective function and constraints to applying algorithm to the part of search space.

Historically, cellular models were initially designed for massively parallel computers and only latter, with popularization of multicore devices, adapted for execution on those devices. Cellular model has a very fine granularity; usually one population unit is assigned to one execution thread. In order to avoid high excess in communications and synchronization, all interaction between individual population units happens between neighbours.

Parallel independent runs approach is trying to speed up multiple execution of an algorithm. In this approach, there is no collaboration or communication between colonies. In independent parallel run approach, every run of an algorithm is independent thread, so in multicore environment, algorithm is running almost n times faster where n is the number of cores.

This approach has no influence on the quality of results. There is no communication between runs in this method of implementation.

Multi-colony approach is much different from previous approaches. Execution time reduction is not the aim of this approach, although it can occur. Main goal is to improve quality of the results. In this approach, every colony has dedicated process. Multiple processes are running same serial version of the algorithm at the same time and at some point, communication among colonies occurs. Depending on the migration policy, colonies exchange some of the results (best, worst, random or combination), and then continue with algorithm execution containing results from other colonies. It has been shown that n colonies with k agents, with different random seeds for each colony, produce better results than one population that has n x k agents. We can observe synergetic effect in this way.

With growing popularity of multi-core computers, many of the population-based algorithm ware parallelized like Ant Colony Optimization [14], [15], [16], Particle Swarm Optimization [17], [18], [19], and Differential Evolution. There are several papers on parallelization of Artificial Bee Colony algorithm, some of which aimed on shortening execution times [21], [22] while others showed application of parallelized ABC algorithm [23]. Researchers in [24], [25] used multi colony model to obtain better quality of results. The latest analysis of coarse-graded parallelized ABC algorithm is [26].

REFERENCES

  1. DORIGO, M., V. MANIEZZO, A. COLORNI, Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 26, no. 1, 1996, pp. 29-41.
  2. JOVANOVIC, R., M. TUBA, An Ant Colony Optimization Algorithm with Improved Pheromone Correction Strategy for the Minimum Weight Vertex Cover Problem, Applied Soft Computing, vol. 11, no. 8, 2011, pp. 5360-5366.
  3. JOVANOVIC, R., M. TUBA, Ant Colony Optimization Algorithm with Pheromone Correction Strategy for the Minimum Connected Dominating Set Problem, Computer Science and Information Systems, vol. 10, no. 1, 2013, pp. 133-149.
  4. TUBA, M., R. JOVANOVIC, Improved Ant Colony Optimization Algorithm with Pheromone Correction Strategy for the Traveling Salesman Problem, International Journal of Computers, Communications and Control, vol. 8, no. 3, 2013, pp. 477-485.
  5. KARABOGA, D., An Idea Based on Honey Bee Swarm for Numerical Optimization, Erciyes University, Kayseri, Turkey, Technical Report-TR06, 2005, p. 10.
  6. BRAJEVIC, I., M. TUBA, An Upgraded Artificial Bee Colony (ABC) Algorithm for Constrained Optimization Problems, Journal of Intelligent Manufacturing, vol. 24, no. 4, 2013, pp. 729-740.
  7. BACANIN, N., M. TUBA, Artificial Bee Colony (ABC) Algorithm for Constrained Optimization Improved with Genetic Operators, Studies in Informatics and Control, vol. 21, no. 2, 2012, pp. 137-146.
  8. YANG, X.-S., Firefly Algorithms for Multimodal Optimization, Proceedings of the 5th international conference on Stochastic algorithms: foundations and applications, 2009, pp. 169-178.
  9. TUBA, M., N. BACANIN, B. PELEVIC, Framework for Constrained Portfolio Selection by the Firefly Algorithm, International Journal of Mathematical Models and Methods in Applied Sciences, vol. 7, no. 10, 2013, pp. 888-896.
  10. BRAJEVICI, I., M. TUBA, Cuckoo Search and Firefly Algorithm Applied to Multilevel Image Thresholding, Cuckoo Search and Firefly: Theory and Applications, ed. Xin-She Yang, Studies in Computational Intelligence, vol. 516, 2014, pp. 115-139.
  11. DAI, C., W. CHEN, Y. SONG, Y. ZHU, Seeker Optimization Algorithm: A Novel Stochastic Search Algorithm for Global Numerical Optimization, Journal of Systems Engineering and Electronics, vol. 21, no. 2, 2010, pp. 300-311.
  12. TUBA, M., I. BRAJEVIC, R. JOVANOVIC, Hybrid Seeker Optimization Algorithm for Global Optimization, Applied Mathematics and Information Sciences, vol. 7, no. 3, 2013, pp. 867-875.
  13. DEMMEL, J., Optimization of sparse matrix-vector multiplication on emerging multicore platforms, Parallel Computing, vol. 35, no. 3, 2009, pp. 178-194.
  14. PEDEMONTE, M., S. NESMACHNOW, H. CANCELA, A Survey on Parallel Ant Colony Optimization, Applied Soft Comp., vol. 11(8), 2011, pp. 5181-5197.
  15. NICOARA, E. S., F. G. FILIP, N. PARASCHIV, Simulation-based Optimization using Genetic Algorithms for Multi-objective Flexible JSSP, Studies in Informatics and Control, vol. 20, no. 4, 2011, pp. 333-344.
  16. SECUI, C. D., S. DZITAC, G. V. BENDEA, I. DZITAC, An ACO Algorithm for Optimal Capacitor Banks Placement in Power Distribution Networks, Studies in Informatics and Control, vol. 18, no. 4, 2009, pp. 305-314.
  17. KARABOGA, D., B. AKAY, A Comparative Study of Artificial Bee Colony Algorithm, Applied Mathematics and Computation, vol. 214, no. 1, 2009, pp. 108-132.
  18. KALIVARAPU, V., E. WINER, Asynchronous Parallelization of Particle Swarm Optimization through Digital Pheromone Sharing, Structural and Multidisciplinary Optimization, vol. 39, no. 3, 2009, pp. 263-281.
  19. FARMAHINI-FARAHANI, A., S. VAKILI, S. M. FAKHRAIE, S. SAFARI, C. LUCAS, Parallel Scalable Hardware Implementation of Asynchronous Discrete Particle Swarm Optimization, Eng. Applications of Artificial Intelligence, vol. 23, no. 2, 2010, pp. 177-187.
  20. TU, K.-Y., LIANG Z.-C., Parallel Computation Models of Particle Swarm Optimization Implemented by Multiple Threads, Expert Systems with Applications, vol. 38, no. 5, 2011, pp. 5858-5866.
  21. PARPINELLI, R., C. BENITEZ, H. LOPES, Parallel Approaches for the Artificial Bee Colony Algorithm, Handbook of Swarm Intelligence, Springer series Adaptation, Learning, and Optimization, vol. 8, 2010, pp. 329-345.
  22. BASTURK, A., R. AKAY, Parallel Implementation of Synchronous Type Artificial Bee Colony Algorithm for Global Optimization, Journal of Optimization Theory and Applications, vol. 155, no. 3, 2012, pp. 1095-1104.
  23. VARGAS BENÍTEZ, C., H. LOPES, Parallel Artificial Bee Colony Algorithm Approaches for Protein Structure Prediction Using the 3DHP-SC Model, Intelligent Distributed Computing IV, vol. 315, 2010, pp. 255-264.
  24. RUHAI, L., Parallelized Artificial Bee Colony with Ripple-communication Strategy, International Conference on Genetic and Evolutionary Computing, 2010, pp. 350-353.
  25. CHRISTOPHER COLUMBUS, C., SIMON S. P., Profit based Unit Commitment: A Parallel ABC Approach using a Workstation Cluster, Computers and Electrical Engineering, vol. 38, no. 3, 2012, pp. 724-745.
  26. BASTURK, A., AKAY, R., Performance Analysis of the Coarse-Grained Parallel Model of the Artificial Bee Colony Algorithm, Information Sciences, vol. 253, 2013, pp. 34-55.