On the performance evaluation of synchronous and asynchronous parallel particle swarm optimisation
DOI:
https://doi.org/10.26034/lu.akwi.2024.6220Keywords:
Artificial Intelligence, Optimisation, Search Heuristics, Distributed Computing, PAPSO, PSPSOAbstract
In this work, the efficiency (time) and effectivity (fitness) of two parallel variants of Particle Swarm Optimisation (PSO) have been evaluated, the synchronous PSPSO and the asynchronous PAPSO. In this study, an implementation of PAPSO is utilised, which deviates from the master-slave principle. Instead, all particles function as independent workers, competing for the available computing resources. If a particle discovers a new best position, it shares this information with the other particles. Two well-known test functions, the Rosenbrock function and the Rastigin function, were applied for evaluating the efficiency and effectivity of PSPSO and PAPSO. Firstly, versions of the test functions with 10, 30, and 60 dimensions were used. The population size was increased for each dimensionality from 50 to 100 and finally 200 particles. The results of this set of experiments showed that both variants of PSO performed similar regarding to their effectiveness of finding the optimum solutions. The computing time used by PAPSO, on the other hand, is significantly smaller than the computing time needed by PSPSO. On average the PAPSO was 69.1 % faster than the PSPSO on the Rosenbrock function and 90.3 % faster on the Rastigin function. In a second set of simulations, the maximum waiting time was varied from 5 ms to 1,000 ms. It is shown for both algorithms, that the average computing time rises linearly with the maximum waiting time.
References
Clerc, M., Kennedy, J., 2002. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evol. Computat. 6, 58–73. https://doi.org/10.1109/4235.985692
Engelbrecht, A., 2012. Particle swarm optimization: Velocity initialization, in: 2012 IEEE Congress on Evolutionary Computation. Presented at the 2012 IEEE Congress on Evolutionary Computation, pp. 1–8. https://doi.org/10.1109/CEC.2012.6256112
Gaviano, M., Lera, D., Mereu, E., 2012. A Parallel Algorithm for Global Optimization Problems in a Distribuited Computing Environment. AM 03, 1380–1387. https://doi.org/10.4236/am.2012.330194
Holland, J., 1975. Adaptation in Natural and Artificial Systems.
Jiang, C., Zhang, C., Zhang, Y., Xu, H., 2017. An improved particle swarm optimization algorithm for parameter optimization of proportional–integral–derivative controller. Traitement du signal 34, 93–110. https://doi.org/10.3166/ts.34.93-110
Kennedy, J., Eberhart, R., 1995. Particle swarm optimization, in: Proceedings of ICNN’95-International Conference on Neural Networks. Presented at the Proceedings of ICNN’95-international conference on neural networks, IEEE, pp. 1942–1948.
Kirkpatrick, S., 1984. Optimization by simulated annealing: Quantitative studies. J Stat Phys 34, 975–986. https://doi.org/10.1007/BF01009452
Koh, B.-I., George, A.D., Haftka, R.T., Fregly, B.J., 2006. Parallel asynchronous particle swarm optimization. Int J Numer Methods Eng 67, 578–595. https://doi.org/10.1002/nme.1646
Nolle, L., 2015. On a search strategy for collaborating autonomous underwater vehicles. Mendel 2015, 159–164.
Nolle, L., Werner, J., 2017. Asynchronous Population-Based Hill Climbing Applied to SPICE Model Generation from EM Simulation Data, in: Bramer, M., Petridis, M. (Eds.), Artificial Intelligence XXXIV, Lecture Notes in Computer Science. Springer International Publishing, Cham, pp. 423–428. https://doi.org/10.1007/978-3-319-71078-5_37
Rastrigin, L., 1974. Systems of Extreme Control.
Rosenbrock, H.H., 1960. An Automatic Method for Finding the Greatest or Least Value of a Function. The Computer Journal 3, 175–184. https://doi.org/10.1093/comjnl/3.3.175
Schutte, J.F., Reinbolt, J.A., Fregly, B.J., Haftka, R.T., George, A.D., 2004. Parallel global optimization with the particle swarm algorithm. Int J Numer Methods Eng 61, 2296–2315. https://doi.org/10.1002/nme.1149
Shi, Y., Eberhart, R.C., 1998. Parameter selection in particle swarm optimization, in: Porto, V.W., Saravanan, N., Waagen, D., Eiben, A.E. (Eds.), Lecture Notes in Computer Science. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 591–600. https://doi.org/10.1007/BFb0040810
Tholen, C., Nolle, L., El-Mihoub, T., Dierks, J., Burger, A., Zielinski, O., 2019. Automated Tuning Of A Cellular Automata Using Parallel Asynchronous Particle Swarm Optimisation, in: ECMS 2019 Proceedings Edited by Mauro Iacono, Francesco Palmieri, Marco Gribaudo, Massimo Ficco. Presented at the 33rd International ECMS Conference on Modelling and Simulation, ECMS, pp. 30–36. https://doi.org/10.7148/2019-0030
Tholen, C., Wolf, M., 2023. On the Development of a Candidate Selection System for Automated Plastic Waste Detection Using Airborne Based Remote Sensing, in: Bramer, M., Stahl, F. (Eds.), Artificial Intelligence XL, Lecture Notes in Computer Science. Springer Nature Switzerland, Cham, pp. 506–512. https://doi.org/10.1007/978-3-031-47994-6_45
Umarani, R., Selvi, V., 2010. Particle swarm optimization-evolution, overview and applications. International Journal of Engineering Science and Technology 2.
Venter, G., Sobieszczanski-Sobieski, J., 2006. Parallel Particle Swarm Optimization Algorithm Accelerated by Asynchronous Evaluations. Journal of Aerospace Computing, Information, and Communication 3, 123–137. https://doi.org/10.2514/1.17873
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Christoph Tholen, Lars Nolle
This work is licensed under a Creative Commons Attribution 4.0 International License.
