An Extension of Particle Swarm Optimization to Identify Multiple Peaks using Re-diversification in Static and Dynamic Environments
Abstract
We propose an extension of the particle swarm optimization (PSO) algorithm for each particle to store multiple global optima internally for identifying multiple (top-k) peaks in static and dynamic environments. We then applied this technique to search and rescue problems of rescuing potential survivors urgently in life-threatening disaster scenarios. With the rapid development of robotics and
computer technology, aerial drones can be programmed to implement search algorithms that locate potential survivors and relay their positions to rescue teams. We model an environment of a disaster area with potential survivors using randomized
bivariate normal distributions. We extended the Clerk-Kennedy PSO algorithm as top-k PSO by considering individual drones as particles, where each particle remembers a set of global optima to identify the top-k peaks. By comparing several other
algorithms, including the canonical PSO, Clerk-Kennedy PSO, and NichePSO, we evaluated our proposed algorithm in static and dynamic environments. The experimental results show that the proposed algorithm was able to identify the top-k
peaks (optima) with a higher success rate than the baseline methods, although the rate gradually decreased with increasing movement speed of the peaks in dynamic environments.
References
Ollero A. Control and perception techniques for aerial robotics. In 7th IFAC Symposium on Robot Control, pages 717–725, 2003.
Ekkarat Adsawinnawanawa and Boontee Kruatrachue. Mutation variations in improving local optima problem of pso. 2020.
Linus Bengtsson, Xin Lu, Anna Ekeus Thorson, Richard Garfield, and Johan von Schreeb. Improved response to disasters and outbreaks by tracking population movements with mobile phone network data: A post-earthquake geospatial study in haiti. PLoS Medicine, 8, 2011.
Tim M. Blackwell. Particle swarm optimization in dynamic environments. In Evolutionary Computation in Dynamic and Uncertain Environments, 2007.
Tim M. Blackwell and Peter John Bentley. Dynamic search with charged swarms. In GECCO, 2002.
R. Brits, A. Engelbrecht, and F. van den Bergh. A niching particle swarm optimizer. In Proceedings of the Fourth Asian-Pacific Conference on Simulated Evolution and Learning, pages 692–696, 2002.
R. Brits, A.P. Engelbrecht, and F. van den Bergh. Solving systems of unconstrained equations using particle swarm optimization. In IEEE Conference on Systems, Man, and Cybernetics, Tunisia, 2002.
Shuang Cao, Yulong Wang, Xiaoxiang Wang, and Qi Li. A rapid assessment method for seismic intensity area and affecting field direction using mobile phone base stations. 2020 5th International Conference on Computer and Comunication Systems (ICCCS), pages 623–627, 2020.
M. Clerk and J. Kennedy. The particle swarm: explosion, stability, and con- vergence in a multi-dimensional space. IEEE transactions on Evolutionary Computation, 6, 2000.
Tyler Crane, Beatrice M. Ombuki-Berman, and Andries Petrus Engelbrecht. Nichepso and the merging subswarm problem. 2020 7th International Conference on Soft Computing &Machine Intelligence (ISCMI), pages 17–22, 2020.
Simon Dennis and Andries Petrus Engelbrecht. Dynamic multi-swarm fractional-best particle swarm optimization for dynamic multi-modal optimization. 2020 IEEE Symposium Series onComputational Intelligence (SSCI), pages 1549–1556, 2020.
Andries P. Engelbrecht. Heterogeneous particle swarm optimization. ANTS 2010, LNCS 6234, pages 191–202, 2010.
Issam Fares, Rizk Masoud Rizk-Allah, Aboul Ella Hassanien, and Snasel Vaclav. Multiple cyclic swarming optimization for uni- and multi-modal functions. 2020.
J. Kennedy. The particle swarm: Social adaptation of knowledge. In Proceedings of the IEEE International Conference on Evolutionary Computation, pages 303–308, 1997.
J. Kennedy. Bare bones particle swarms. In Proceedings of the IEEE Swarm Intelligence Symposium, pages 80–87, 2003.
J. Kennedy and R.C. Eberhart. A new optimizer using particle swarm theory. In Proceedings of the Sixth International Symposium on Micromachine and Human Science, pages 39–43, 1995.
J. Kennedy and R.C. Eberhart. Particle swarm optimization. In Proceedings of IEEE International Conference on Neutral Networks, volume ICNN ’95, pages 1942–1948, Perth, Western Australia, December 1995.
Barend J. Leonard, Andries Petrus Engelbrecht, and Andrich B. van Wyk. Het- erogeneous particle swarms in dynamic environments. 2011 IEEE Symposium on Swarm Intelligence, pages 1–8, 2011.
Xiaodong Li. Niching without niching parameters: Particle swarm optimization using a ring topology. IEEE Transactions on Evolutionary Computation, 14:150–169, 2010.
Andrei Lihu and Stefan Holban. A study on the minimal number of particles for a simplified particle swarm optimization algorithm. In 2011 6th IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI), pages 299–303, 2011.
Xin Lu, Linus Bengtsson, and Petter Holme. Predictability of population dis- placement after the 2010 haiti earthquake. Proceedings of the National Academy of Sciences, 109:11576 – 11581, 2012.
M. Mitchell. An Introduction to Genetic Algorithms. MIT Press, 1996.
Eslam Nabil Mobarez, Amr A. Sarhan, and Mohamed Ashry. Obstacle avoidance for multiuav path planning based on particle swarm optimization. IOP Conference Series: Materials Science and Engineering, 1172, 2021.
Venkataraman Muthiah-Nakarajan and Mathew Mithra Noel. Galactic swarm optimization: A new global optimization metaheuristic inspired by galactic motion. Appl. SoftComput., 38:771–787, 2016.
Masahiko Onosato, Satoshi Tadokoro, Hiroaki Nakanishi, Kenzo Nonami, Kuniaki Kawabata, Yasushi Hada, Hajime Asama, Fumiaki Takemura, Kiyoshi Maeda, Kenjiro Miura, and Atsushi Yamashita. Rescue Robotics, chapter 3. Springer, 2009.
K. E. Parsopoulos and M. N. Vrahatis. Recent approaches to global optimization problems through particle swarm optimization. Natural Computing, pages 235–306, 2002.
Alessandro Passaro and Antonina Starita. Particle swarm optimization for multimodal functions: a clustering approach. Journal of Artificial Evolution and Applications, 2008:8, 2008.
Lukkana Poempool, Boontee Kruatrachue, and Kritawan Siriboon. Combine multi particle swarm in supporting trapping in local optima. 2018 International Conference on Engineering, Applied Sciences, and Technology (ICEAST), pages 1–4, 2018.
Stephen Raharja and Toshiharu Sugawara. Identifying top-k peaks using an extended particle swarm optimization algorithm with re-diversification mechanism. SCAI 2022, pages 359–366, 2022.
Mahsoo Salimi and Philippe Pasquier. Deep reinforcement learning for flocking control of uavs in complex environments. 2021 6th International Conference on Robotics and Automation Engineering (ICRAE), pages 344–352, 2021.
Y. Shi and R.C. Eberhart. An empirical study of particle swarm optimization. In Proceedings of the 1999 Conference on Evolutionary Computation, pages 1945–1950, IEEE Service Center, Piscataway, NJ, 1999.
Satoshi Tadokoro. Rescue Robotics, chapter 1. Springer, 2009.
F. van den Bergh. An Analysis of Particle Swarm Optimizers. PhD thesis, Department of Computer Science, University of Pretoria, Pretoria, South Africa, 2002.
F. van den Bergh and A. P. Engelbrecht. A new locally convergent particle swarm optimizer. In IEEE Conference on Systems,Man, andCybernetics, Tunisia, 2002.
Jianfang Wang, Ning Cheng, Zhidu Liu, and Changwang Liu. Applying fusion of pso-abc algorithm on the minimax location problem. The Open Cybernetics & Systemics Journal, 8, 2014.
Pin Zhang, Haorong Li, Quang Phuc Ha, Zhen-Yu Yin, and Ren peng Chen. Re- inforcement learning based optimizer for improvement of predicting tunneling- induced ground responses. Adv. Eng. Informatics, 45:101097, 2020.
Zhe Zhang, Limin Jia, and Yong Qin. Modified constriction particle swarm opti- mization algorithm. Journal of Systems Engineering and Electronics, 26:1107– 1113, 2015.
