journal article·2024-02-15Open access

Running-Time Analysis of Brain Storm Optimization Based on Average Gain Model

Guizhen Mai, Fangqing Liu, Yinghan Hong, Dingrong Liu, Junpeng Su, Xiaowei Yang, Han Huang

Biomimetics· Volume 9· Issue 2

Abstract

The brain storm optimization (BSO) algorithm has received increased attention in the field of evolutionary computation. While BSO has been applied in numerous industrial scenarios due to its effectiveness and accessibility, there are few theoretical analysis results about its running time. Running-time analysis can be conducted through the estimation of the upper bounds of the expected first hitting time to evaluate the efficiency of BSO. This study estimates the upper bounds of the expected first hitting time on six single individual BSO variants (BSOs with one individual) based on the average gain model. The theoretical analysis indicates the following results. (1) The time complexity of the six BSO variants is O(n) in equal coefficient linear functions regardless of the presence or absence of the disrupting operator, where n is the number of the dimensions. Moreover, the coefficient of the upper bounds on the expected first hitting time shows that the single individual BSOs with the disrupting operator require fewer iterations to obtain the target solution than the single individual BSOs without the disrupting operator. (2) The upper bounds on the expected first hitting time of single individual BSOs with the standard normally distributed mutation operator are lower than those of BSOs with the uniformly distributed mutation operator. (3) The upper bounds on the expected first hitting time of single individual BSOs with the U−12,12 mutation operator are approximately twice those of BSOs with the U(−1,1) mutation operator. The corresponding numerical results are also consistent with the theoretical analysis results.
Source: crossref · Quality: baseline

Research context

OpenAlex topics: Metaheuristic Optimization Algorithms Research · Neural Networks and Reservoir Computing · Evolutionary Algorithms and Applications

SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.

Affiliations

School of Physics and Electronic Engineering, Hanshan Normal University, Chaozhou 521041, China

School of Software Engineering, South China University of Technology, Guangzhou 510006, China

Funding

National Natural Science Foundation of China · Natural Science Foundation of Guangdong Province · Guangdong Provincial Department of Education · Guangzhou Science and Technology Planning Project · Doctor Starting Fund of Hanshan Normal University, China · Scientific Research Talents Fund of Hanshan Normal University, China · The quality of teaching construction project of Hanshan Normal University · Research Platform Project of Hanshan Normal University · The quality of teaching construction project of Guangdong Provincial Department of Education in 2023 · Guangdong Provincial Key Laboratory of Data Science and Intelligent Education

References (59)

Show source-provided references
1. Michaloglou, A., and Tsitsas, N.L. (2023). A Brain Storm and Chaotic Accelerated Particle Swarm Optimization Hybridization. Algorithms, 16.10.3390/a16040208 ↗
2. Nature inspired methods and their industry applications-swarm intelligence algorithms10.1109/TII.2017.2786782 ↗
3. A self-adaptive artificial bee colony algorithm based on global best for global optimization10.1007/s00500-017-2547-1 ↗
4. Coevolutionary Particle Swarm Optimization With Bottleneck Objective Learning Strategy for Many-Objective Optimization10.1109/TEVC.2018.2875430 ↗
5. Two-Stage Multi-Swarm Particle Swarm Optimizer for Unconstrained and Constrained Global Optimization10.1109/ACCESS.2020.3007743 ↗
6. ACO-A*: Ant Colony Optimization Plus A* for 3-D Traveling in Environments with Dense Obstacles10.1109/TEVC.2018.2878221 ↗
7. Tilting Path Optimization of Tilt Quad Rotor in Conversion Process Based on Ant Colony Optimization Algorithm10.1109/ACCESS.2020.3012672 ↗
8. Cooperative Artificial Bee Colony Algorithm with Multiple Populations for Interval Multiobjective Optimization Problems10.1109/TFUZZ.2018.2872125 ↗
9. Co-variance guided artificial bee colony10.1016/j.asoc.2018.04.050 ↗
10. Brain storm optimization algorithm: A review10.1007/s10462-016-9471-0 ↗
11. Cheng, S., Sun, Y., Chen, J., Qin, Q., Chu, X., Lei, X., and Shi, Y. (2017, January 5–8). A comprehensive survey of brain storm optimization algorithms. Proceedings of the 2017 IEEE Congress on Evolutionary Computation (CEC), San Sebastián, Spain.
12. Generalized pigeon-inspired optimization algorithms10.1007/s11432-018-9727-y ↗
13. A binary coded brain storm optimization for fault section diagnosis of power systems10.1016/j.epsr.2018.07.009 ↗
14. Multi-objective optimisation method of power grid partitioning for wide-area backup protection10.1049/iet-gtd.2017.0311 ↗
15. Ogawa, S., and Mori, H. (2019, January 10–14). A Hierarchical Scheme for Voltage and Reactive Power Control with Predator-Prey Brain Storm Optimization. Proceedings of the 2019 20th International Conference on Intelligent System Application to Power Systems (ISAP), New Delhi, India.10.1109/ISAP48318.2019.9065941 ↗
16. Matsumoto, K., and Fukuyama, Y. (2020, January 19–21). Voltage and Reactive Power Control by Parallel Modified Brain Storm Optimization. Proceedings of the 2020 International Conference on Artificial Intelligence in Information and Communication (ICAIIC), Fukuoka, Japan.10.1109/ICAIIC48513.2020.9065267 ↗
17. Tan, Y., Shi, Y., and Niu, B. (2016). Proceedings of the Advances in Swarm Intelligence, Springer.10.1007/978-3-319-41000-5 ↗
18. Simplified brain storm optimization approach to control parameter optimization in F/A-18 automatic carrier landing system10.1016/j.ast.2015.01.017 ↗
19. Zhang, C., Xu, X., Shi, Y., Deng, Y., Li, C., and Duan, H. (2019, January 10–13). Binocular Pose Estimation for UAV Autonomous Aerial Refueling via Brain Storm Optimization. Proceedings of the 2019 IEEE Congress on Evolutionary Computation (CEC), Wellington, New Zealand.10.1109/CEC.2019.8789952 ↗
20. Tuba, E., Strumberger, I., Zivkovic, D., Bacanin, N., and Tuba, M. (2018, January 8–13). Mobile Robot Path Planning by Improved Brain Storm Optimization Algorithm. Proceedings of the 2018 IEEE Congress on Evolutionary Computation (CEC), Rio de Janeiro, Brazil.10.1109/CEC.2018.8477928 ↗
21. Li, G., Zhang, D., and Shi, Y. (2019, January 10–13). An Unknown Environment Exploration Strategy for Swarm Robotics Based on Brain Storm Optimization Algorithm. Proceedings of the 2019 IEEE Congress on Evolutionary Computation (CEC), Wellington, New Zealand.10.1109/CEC.2019.8789994 ↗
22. Brain Storm Optimization for Electromagnetic Applications: Continuous and Discrete10.1109/TAP.2019.2894318 ↗
23. A Hybrid Approach by Integrating Brain Storm Optimization Algorithm with Grey Neural Network for Stock Index Forecasting
24. Hybrid biogeography-based optimization with brain storm optimization for non-convex dynamic economic dispatch with valve-point effects10.1016/j.energy.2018.05.180 ↗
25. Cheng, S., and Shi, Y. (2019). Proceedings of the Brain Storm Optimization Algorithms: Concepts, Principles and Applications, Springer.10.1007/978-3-030-15070-9 ↗
26. A generalized dynamic fuzzy neural network based on singular spectrum analysis optimized by brain storm optimization for short-term wind speed forecasting10.1016/j.asoc.2017.01.033 ↗
27. Liang, J.J., Wang, P., Yue, C.T., Yu, K., Li, Z.H., and Qu, B. (2018, January 8–13). Multi-objective Brainstorm Optimization Algorithm for Sparse Optimization. Proceedings of the 2018 IEEE Congress on Evolutionary Computation (CEC), Rio de Janeiro, Brazil.10.1109/CEC.2018.8477789 ↗
28. Stochastic multi-objective modelling and optimization of an energy-conscious distributed permutation flow shop scheduling problem with the total tardiness constraint10.1016/j.jclepro.2019.04.046 ↗
29. Feature selection based on brain storm optimization for data classification10.1016/j.asoc.2019.04.037 ↗
30. Multi-Clusters Adaptive Brain Storm Optimization Algorithm for QoS-Aware Service Composition10.1109/ACCESS.2020.2979892 ↗
31. Zhou, Z., Duan, H., and Shi, Y. (2016, January 24–29). Convergence analysis of brain storm optimization algorithm. Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, BC, Canada.10.1109/CEC.2016.7744264 ↗
32. The Global Convergence Analysis of Brain Storm Optimization10.14704/nq.2018.16.6.1571 ↗
33. Theoretical analysis of the convergence property of a basic pigeon-inspired optimizer in a continuous search space10.1007/s11432-018-9753-5 ↗
34. A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms10.1109/TEVC.2012.2202241 ↗
35. Average Drift Analysis and Population Scalability
36. Switch Analysis for Running Time Analysis of Evolutionary Algorithms10.1109/TEVC.2014.2378891 ↗
37. Wave models and dynamical analysis of evolutionary algorithms10.1007/s11432-018-9852-8 ↗
38. Ahn, H.K., and Shin, C.S. (2014). Proceedings of the Algorithms and Computation, Springer.10.1007/978-3-319-13075-0 ↗
39. Fitness levels with tail bounds for the analysis of randomized search heuristics10.1016/j.ipl.2013.09.013 ↗
40. Yu, Y., and Qian, C. (2015, January 25–28). Running time analysis: Convergence-based analysis reduces to switch analysis. Proceedings of the 2015 IEEE Congress on Evolutionary Computation (CEC), Sendai, Japan.10.1109/CEC.2015.7257209 ↗
41. Runtime analysis for continuous (1 + 1) evolutionary algorithm based on average gain model
42. An Experimental Method to Estimate Running Time of Evolutionary Algorithms for Continuous Optimization10.1109/TEVC.2019.2921547 ↗
43. First hitting time analysis of continuous evolutionary algorithms based on average gain10.1007/s10586-016-0587-4 ↗
44. A new approach to estimating the expected first hitting time of evolutionary algorithms10.1016/j.artint.2008.07.001 ↗
45. Wang, Y. (2023). Application of data mining based on swarm intelligence algorithm in financial support of livestock and poultry breeding insurance. Soft Comput.10.1007/s00500-023-08372-w ↗
46. Zhan, Z., Zhang, J., Shi, Y., and Liu, H. (2012, January 10–15). A modified brain storm optimization. Proceedings of the 2012 IEEE Congress on Evolutionary Computation, Brisbane, QLD, Australia.10.1109/CEC.2012.6256594 ↗
47. El-Abd, M. (2016, January 24–29). Brain storm optimization algorithm with re-initialized ideas and adaptive step size. Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, BC, Canada.10.1109/CEC.2016.7744125 ↗
48. Tan, Y., Shi, Y., Chai, Y., and Wang, G. (2011). Proceedings of the Advances in Swarm Intelligence, Springer.10.1007/978-3-642-21515-5 ↗
49. An Optimization Algorithm Based on Brainstorming Process10.4018/ijsir.2011100103 ↗
50. Recent advances in evolutionary computation10.1007/s11390-006-0001-4 ↗
51. Evolutionary algorithms for continuous-space optimisation10.1080/00207721.2011.605963 ↗
52. Drift analysis and average time complexity of evolutionary algorithms10.1016/S0004-3702(01)00058-3 ↗
53. Hassler, U. (2016). Proceedings of the Stochastic Processes and Calculus: An Elementary Introduction with Applications, Springer.10.1007/978-3-319-23428-1 ↗
54. Combining Markov-chain analysis and drift analysis: The (1 + 1) evolutionary algorithm on linear functions reloaded10.1007/s00453-010-9396-y ↗
55. Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions10.1017/S0963548312000600 ↗
56. Hao, Z., Huang, H., Zhang, X., and Tu, K. (2006, January 15–18). A Time Complexity Analysis of ACO for Linear Functions. Proceedings of the Simulated Evolution and Learning, 6th International Conference, SEAL 2006, Hefei, China.
57. Algorithmic analysis of a basic evolutionary algorithm for continuous optimization10.1016/j.tcs.2007.02.042 ↗
58. Feller, W. (2008). An Introduction to Probability Theory and Its Applications, John Wiley & Sons.
59. Zhan, Z.H., Chen, W.N., Lin, Y., Gong, Y.J., Li, Y.L., and Zhang, J. (2013, January 16–19). Parameter investigation in brain storm optimization. Proceedings of the 2013 IEEE Symposium on Swarm Intelligence (SIS), Singapore.10.1109/SIS.2013.6615166 ↗