A Distributed Sailfish Optimizer Based on Multi-Agent Systems for Solving Non-Convex and Scalable Optimization Problems Implemented on GPU

Shadravan, S.; Naji, H.; Khatibi, V.

doi:10.22044/jadm.2020.9389.2075

Document Type : Original/Review Paper

Authors

¹ Department of Computer Engineering, Kerman Branch, Islamic Azad University, Kerman, Iran

² Department of Computer Engineering, Graduate University of Advanced Technology, Kerman, Iran.

³ Department of Computer Engineering, Kerman Branch, Islamic Azad University, Bardsir, Iran.

https://doi.org/10.22044/jadm.2020.9389.2075

Abstract

The SailFish Optimizer (SFO) is a metaheuristic algorithm inspired by a group of hunting sailfish that alternates their attacks on group of prey. The SFO algorithm takes advantage of using a simple method for providing the dynamic balance between exploration and exploitation phases, creating the swarm diversity, avoiding local optima, and guaranteeing high convergence speed. Nowadays, multi agent systems and metaheuristic algorithms can provide high performance solutions for solving combinatorial optimization problems. These methods provide a prominent approach to reduce the execution time and improve of the solution quality. In this paper, we elaborate a multi agent based and distributed method for sailfish optimizer (DSFO), which improves the execution time and speedup of the algorithm while maintaining the results of optimization in high quality. The Graphics Processing Units (GPUs) using Compute Uniﬁed Device Architecture (CUDA) are used for the massive computation requirements in this approach. In depth of the study, we present the implementation details and performance observations of DSFO algorithm. Also, a comparative study of distributed and sequential SFO is performed on a set of standard benchmark optimization functions. Moreover, the execution time of distributed SFO is compared with other parallel algorithms to show the speed of the proposed algorithm for solving unconstrained optimization problems. The final results indicate that the proposed method is executed about maximum 14 times faster than other parallel algorithms and shows the ability of DSFO for solving non-separable, non-convex and scalable optimization problems.

Keywords

20.1001.1.23225211.2021.9.1.7.8

References

[1] C. Blum et al., "Hybrid metaheuristics in combinatorial optimization: A survey" Applied Soft Computing, vol.11, no. 6, pp. 4135 – 4151, 2011.

[2] I. Boussaid et al., "A survey on optimization metaheuristics" Information Sciences, vol. 237, pp. 82–117, 2013.

[3] M.B. Ayhan et al., "A multi-agent based approach for change management in manufacturing enterprises" Journal of Intelligent Manufacturing, vol. 26, no. 5, pp. 975-988, 2015.

[4] M.A. Hale and J. Craig, "Preliminary development of agent technologies for a design integration framework" Proc. 5th Symp. Multidisciplinary Analysis and Optimization, Panama City, FL, 1994.

[5] N. Jennings and M. Wooldridge, "Intelligent Agents: Theory and Practice" The Knowledge Eng. Rev, vol. 10, no. 2, pp. 115–152, 1995.

[6] J. M Vidal et al., "Inside an Agent"IEEE Internet Computing, 2001.

[7] S. Shadravan et al., "The Sailfish Optimizer: A novel nature-inspired metaheuristic algorithm for solving constrained engineering optimization problem" Engineering Applications of Artificial Intelligence, vol. 88, pp. 20–34, 2019.

[8] M. E. Aydin, "Meta-heuristic agent teams for job shop scheduling problems" Lecture Notes in Artiﬁcial Intelligence, vol. 4659, pp. 185-194, 2007.

[9] M. Hammami and K. Ghediera, "COSATS, X-COSATS: Two multi-agent systems cooperating simulated annealing, tabu search and X-over operator for the K-Graph Partitioning problem" Lecture Notes in Computer Science, vol. 3684, pp. 647-653, 2005.

[10] S. Talukdar et al., "Asynchronous teams: Cooperation schemes for autonomous agents" Journal of Heuristics, vol. 4, no. 4, pp. 295–321, 1998.

[11] S. Talukdar, S. Murthy and R. Akkiraju "Asynchronous teams. In Handbook of Metaheuristics, ser. International Series in Operations Research & Management Science" Springer US, vol. 57, pp. 537–556, 2013.

[12] Maria Amélia Lopes Silva et al. "A Multiagent Metaheuristic Optimization Framework with Cooperation" Brazilian Conference on Intelligent Systems IEEE, pp. 104-109, 2015.

[13] H. R. Naji, M. Sohrabi, and E. Rashedi, "A High Speed and Performance Optimization Algorithm Based on Gravitational Approach" IEEE Journal of Computing in Science and Engineering, vol. 14, no. 5, pp. 56-62, 2013.

[14] H. R. Naji, "Solving Large Computational Problems using Multi-Agents Implemented in Hardware" Computing in Science and Engineering, IEEE CS and American Institute of Physics, vol. 10, no. 5, pp. 54-63, 2008.

[15] H.R. Naji and B.E. Wells, " On incorporating multi-agents in combined hardware/software based reconfigurable systems, a general architectural framework" Symposium on System Theory, Huntsville, AL, 2002.

[16] G. Binetti et al., "Distributed consensus-based economic dispatch with transmission losses" IEEE Trans. Power Syst., vol. 29, no. 4, pp. 1711–1720, 2014.

[17] Z. Qiu, S. Liu and L. Xie, " Distributed constrained optimal consensus of multi-agent systems" Automatica, vol. 68, pp. 209–215, 2016.

[18] R. Carli et al., "Analysis of newton-raphson consensus for multi-agent convex optimization under asynchronous and lossy communications" in IEEE 54th Annual Conference on Decision and Control (CDC). IEEE, pp. 418–424, 2015.

[19] H. Zhang et al., "Adaptive consensus-based distributed target tracking with dynamic cluster in sensor network" IEEE Trans. Cybern., vol. 49, no. 5, pp. 1580–1591, 2019.

[20] R. Yarinezhad and A, Sarabi, "A New Routing Algorithm for Vehicular Ad-hoc Networks based on Glowworm Swarm Optimization Algorithm" Journal of AI and Data Mining, vol. 7, no. 1, pp. 69-76, 2019.

[21] Sh. Lotfi and F. Karimi, "A Hybrid MOEA/D-TS for Solving Multi-Objective Problems" Journal of AI and Data Mining, vol. 5, no. 2, pp. 183-195, 2017.

[22] M. Essaid et al., " GPU parallelization strategies for metaheuristics: a survey" International Journal of Parallel, Emergent and Distributed Systems, vol. 34, no. 5, pp. 497-522, 2018.

[23] P. Krömer, J. Platoš and V. Snášel. "Nature-inspired meta-heuristics on modern GPUs: state of the art and brief survey of selected algorithms" Int J Parallel Program, vol. 42, no. 5, pp. 681–709, 2014.

[24] E. Alba, G. Luque and S. Nesmachnow, " Parallel metaheuristics: recent advances and new trends" International Trans OperRes, vol. 20, no. 1, pp. 1–48, 2013.

[25] Z. Yang, Y. Zhu and Y. Pu, " Parallel image processing based on CUDA" In: 2008 International Conference on ComputerScience and Software Engineering, pp. 198–201, 2008.

[26] W. Fang et al., "Parallel data mining on graphics processors" Technical Report HKUST-CS08-07. Hong Kong, China: Hong Kong University of Science and Technology, 2008.

[27] Z.W. Luo et al., "Artiﬁcial Neural Network Computation on Graphic Process Unit" IEEE International Joint Conference on Neural Networks, pp. 622–626, 2005.

[28] R.A. Patel et al., "Parallel lossless data compression on the GP" San Jose (CA): IEEE, 2012.

[29] A. Brodtkorb et al., "State-of-the-art in heterogeneous computing" Sci. Program, vol. 18, no. 1, pp. 1-33, 2012.

[30] NVIDIA, NVIDIA CUDA Programming version 6.0, 2014.

[31] DB. Kirk, WH. Wen-Mei, "Programming massively parallel processors: a hands-on approach" Morgan kaufmann, 2016.

[32] NVIDIA: CURAND Library 7.5., 2015. http://docs.nvidia.com/cuda/pdf/CURAND Library.pdf.

[33] A. Zarrabi et al., "Gravitational search algorithm using CUDA: a case study in high-performance metaheuristics" Springer Science+Business Media New York, vol. 71, no. 4, pp. 1277-1296, 2014.

[34] R.V. Krishna and S.S. Reddy, "Performance Evaluation of Particle Swarm Optimization Algorithms on GPU using CUDA" I J C S S E I T, vol. 5, no. 1, pp. 65-81, 2012.

[35] A.K. Qin et al., "An Improved CUDA-Based Implementation of Differential Evolution on GPU" ACM New York, NY, USA, pp. 991-998, 2012.

A Distributed Sailfish Optimizer Based on Multi-Agent Systems for Solving Non-Convex and Scalable Optimization Problems Implemented on GPU

References

References

Volume 9, Issue 1January 2021Pages 59-71

Volume 9, Issue 1
January 2021
Pages 59-71