The first hitting time analysis of evolutionary algorithms based on renewal process

Zhensheng Zhou; Lin Wang; Xue Zou; Fei Wang; Zaijun Zhang; Xiaobo Yan; Zhensheng Zhou; Lin Wang; Xue Zou; Fei Wang; Zaijun Zhang; Xiaobo Yan

doi:10.3934/era.2024137

Electronic Research Archive

2024, Volume 32, Issue 5: 2994-3015. doi: 10.3934/era.2024137

Previous Article Next Article

Research article

The first hitting time analysis of evolutionary algorithms based on renewal process

1.
School of Data Sciences and Information Engineering, Guizhou Minzu University, Guiyang 550025, China
2.
Guizhou Key Laboratory of Pattern Recognition and Intelligent System, Guiyang 550025, China
3.
College of Big Data and Information Engineering, Guiyang Institute of Humanities and Technology, Guiyang 550025, China
4.
School of Mathematics and Statistics, Qiannan Normal University for Nationalities, Duyun 558000, China
5.
Key Laboratory of Industrial Automation and Machine Vision of Qiannan, Duyun 558000, China

Received: 05 December 2023 Revised: 27 March 2024 Accepted: 12 April 2024 Published: 22 April 2024

Running time analysis of evolutionary algorithms for continuous optimization is one research challenge in the field of evolutionary algorithms (EAs). However, the theoretical analysis results have rarely been applied to evolutionary algorithms for continuous optimization in practice, let alone their variants for evolution strategy. In this paper, we regarded the first hitting time of evolution strategy as the stopping time of the renewal process on the basis of the renewal process and in combination with Wald's inequality and stopping time theory. Afterwards, to demonstrate the application of the proposed model in the first hitting time analysis of (1 + 1) ES, we analyzed it with different mutation operators on the sphere function. First, we significantly improved the lower bound on the first hitting time of (1 + 1) ES with a uniform mutation operator, i.e., from $\Omega(n)$ to $\Omega\left(e^{c n}\right)$. Next, $O\left(n^{2} \sqrt{n}\right)$ was the upper bound on the first hitting time of (1 + 1) ES with a Gaussian mutation operator from the initial distance R to half of the initial distance R/2. The numerical experimental results showed that the theoretical calculation was consistent with the actual running time, which provides a novel method for analyzing the first hitting time of EAs.
- evolutionary algorithms for continuous optimization,
- renewal process,
- stopping time theory,
- first hitting time,
- sphere function
Citation: Zhensheng Zhou, Lin Wang, Xue Zou, Fei Wang, Zaijun Zhang, Xiaobo Yan. The first hitting time analysis of evolutionary algorithms based on renewal process[J]. Electronic Research Archive, 2024, 32(5): 2994-3015. doi: 10.3934/era.2024137

Related Papers:

Abstract

Running time analysis of evolutionary algorithms for continuous optimization is one research challenge in the field of evolutionary algorithms (EAs). However, the theoretical analysis results have rarely been applied to evolutionary algorithms for continuous optimization in practice, let alone their variants for evolution strategy. In this paper, we regarded the first hitting time of evolution strategy as the stopping time of the renewal process on the basis of the renewal process and in combination with Wald's inequality and stopping time theory. Afterwards, to demonstrate the application of the proposed model in the first hitting time analysis of (1 + 1) ES, we analyzed it with different mutation operators on the sphere function. First, we significantly improved the lower bound on the first hitting time of (1 + 1) ES with a uniform mutation operator, i.e., from $\Omega(n)$ to $\Omega\left(e^{c n}\right)$. Next, $O\left(n^{2} \sqrt{n}\right)$ was the upper bound on the first hitting time of (1 + 1) ES with a Gaussian mutation operator from the initial distance R to half of the initial distance R/2. The numerical experimental results showed that the theoretical calculation was consistent with the actual running time, which provides a novel method for analyzing the first hitting time of EAs.

References

[1]	T. Bäck, H. P. Schwefel, An overview of evolutionary algorithms for parameter optimization, Evol. Comput., 1 (1993), 1–23. https://doi.org/10.1162/evco.1993.1.1.1 doi: 10.1162/evco.1993.1.1.1
[2]	J. He, X. Yao, Average drift analysis and population scalability, IEEE Trans. Evol. Comput., 21 (2016), 426–439. https://doi.org/10.1109/tevc.2016.2608420 doi: 10.1109/tevc.2016.2608420
[3]	X. Yao, Unpacking and understanding evolutionary algorithm, in IEEE World Congress on Computational Intelligence, Berlin, Springer Berlin Heidelberg, (2012), 60–76. https://doi.org/10.1007/978-3-642-30687-7_4
[4]	J. He, X. Yao, Towards an analytic framework for analysing the computation time of evolutionary algorithms, Artif. Intell., 145 (2003), 59–97. https://doi.org/10.1016/s0004-3702(02)00381-8 doi: 10.1016/s0004-3702(02)00381-8
[5]	C. Witt, Tight bounds on the optimization time of a randomized search heuristic on linear functions, Comb. Probab. Comput., 22 (2013), 294–318. https://doi.org/10.1017/s0963548312000600 doi: 10.1017/s0963548312000600
[6]	B. Doerr, T. Kötzing, J. A. G. Lagodzinski, J. Lengler, The impact of lexicographic parsimony pressure for ORDER/MAJORIT on the run time, Theor. Comput. Sci., 816 (2020), 144–168. https://doi.org/10.1016/j.tcs.2020.01.011 doi: 10.1016/j.tcs.2020.01.011
[7]	B. Doerr, C. Doerr, J. Yang, Optimal parameter choices via precise black-box analysis, in Proceedings of the Genetic and Evolutionary Computation Conference 2016, New York: ACM, (2016), 1123–1130. https://doi.org/10.1145/2908812.2908950
[8]	P. K. Lehre, C. Witt, Tail bounds on hitting times of randomized search heuristics using variable drift analysis, Comb. Probab. Comput., 30 (2020), 550–569. https://doi.org/10.1017/s0963548320000565 doi: 10.1017/s0963548320000565
[9]	C. Gießen, C. Witt, Optimal mutation rates for the (1 + λ) EA on OneMax through asymptotically tight drift analysis, Algorithmica, 80 (2017), 1710–1731. https://doi.org/10.1007/s00453-017-0360-y doi: 10.1007/s00453-017-0360-y
[10]	R. Sarker, M. Mohammadian, X. Yao, I. Wegener, Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions, Springer US, New York, USA, (2002), 349–369. https://doi.org/10.17877/DE290R-15272
[11]	Y. Yu, C. Qian, Z. H. Zhou, Switch analysis for running time analysis of evolutionary algorithms, IEEE Trans. Evol. Comput., 19 (2015), 777–792. https://doi.org/10.1109/tevc.2014.2378891 doi: 10.1109/tevc.2014.2378891
[12]	C. Qian, C. Bian, W. Jiang, K. Tang, Running time analysis of the (1 + 1)-EA for OneMax and LeadingOnes under bit-wise noise, Algorithmica, 81 (2018), 749–795. https://doi.org/10.1007/s00453-018-0488-4 doi: 10.1007/s00453-018-0488-4
[13]	I. Wegener, Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions Evolutionary Optimization, Springer US, New York, USA, 48 (2003), 349–369. https://doi.org/10.1007/0-306-48041-7_14
[14]	H. Huang, J. P. Su, Y. S. Zhang, Z. F. Hao, An experimental method to estimate running time of evolutionary algorithms for continuous optimization, IEEE Trans. Evol. Comput., 24 (2020), 275–289. https://doi.org/10.1109/tevc.2019.2921547 doi: 10.1109/tevc.2019.2921547
[15]	F. J. Feng, H. Huang, Y. S. Zhang, Z. F. Hao, Comparative analysis for first hitting time of evolutionary algorithms based on equal-in-time model, Chin. J. Comput., 42 (2019), 2297–2308. https://doi.org/10.11897/SP.J.1016.2019.02297 doi: 10.11897/SP.J.1016.2019.02297
[16]	D. Morinaga, K. Fukuchi, J. Sakuma, Y. Akimoto, Convergence rate of the (1 + 1) ES on locally strongly convex and Lipschitz smooth functions, IEEE Trans. Evol. Comput., 2023. https://doi.org/10.1109/tevc.2023.3266955
[17]	J. Jägersküpper, Combining Markov-chain analysis and drift analysis: The (1 + 1) evolutionary algorithm on linear functions reloaded, Algorithmica, 59 (2010), 409–424. https://doi.org/10.1007/s00453-010-9396-y doi: 10.1007/s00453-010-9396-y
[18]	A. Agapie, M. Agapie, G. Rudolph, G. Zbaganu, Convergence of evolutionary algorithms on the n-dimensional continuous space, IEEE Trans. Cybern., 43 (2013), 1462–1472. https://doi.org/10.1109/TCYB.2013.2257748 doi: 10.1109/TCYB.2013.2257748
[19]	D. Morinaga, K. Fukuchi, J. Sakuma, Y. Akimoto, Convergence rate of the (1 + 1) evolution strategy with success-based step-size adaptation on convex quadratic functions, in Proceedings of the Genetic and Evolutionary Computation Conference, (2021), 1169–1177. https://doi.org/10.1145/3449639.3459289
[20]	Y. S. Zhang, H. Huang, Z. F. Hao, G. W. Hu, First hitting time analysis of continuous evolutionary algorithms based on average gain, Chin. J. Comput., 42 (2019), 624–635. https://doi.org/10.11897/SP.J.1016.2019.00624 doi: 10.11897/SP.J.1016.2019.00624
[21]	A. Agapie, Spherical distributions used in evolutionary algorithms, Mathematics, 9 (2021), 2227–7390. https://doi.org/10.3390/math9233098 doi: 10.3390/math9233098
[22]	B. Doerr, C. Witt, J. Yang, Running time analysis for self-adaptive mutation rates, in Proceedings of the Genetic and Evolutionary Computation Conference, (2018), 1475–1482. https://doi.org/10.1007/S00453-020-00726-2
[23]	Y. Akimoto, A. Anne, G. Tobias, Drift theory in continuous search spaces: expected hitting time of the (1 + 1) ES with 1/5 success rule, in Proceedings of the Genetic and Evolutionary Computation Conference, (2018), 801–808. https://doi.org/10.1145/3205455.3205606
[24]	J. Jägersküpper, Lower bounds for randomized direct search with isotropic sampling, Oper. Res. Lett., 36 (2008), 327–332. https://doi.org/10.1016/j.orl.2007.10.003 doi: 10.1016/j.orl.2007.10.003
[25]	H. G. Beyer, H. P. Schwefel, Evolution strategies–a comprehensive introduction, Nat. Comput., 1 (2002), 3–52. https://doi.org/10.1023/a:1015059928466 doi: 10.1023/a:1015059928466
[26]	F. Neumann, C. Witt, Runtime Analysis of the (1 + 1) EA on weighted Sums of transformed linear functions, in International Conference on Parallel Problem Solving from Nature, Cham: Springer International Publishing, (2022), 542–554. https://doi.org/10.1007/978-3-642-30687-7_4
[27]	B. Doerr, T. Kötzing, Lower bounds from fitness levels made easy, in Proceedings of the Genetic and Evolutionary Computation Conference, New York: ACM, (2021), 1142–1150. https://doi.org/10.1145/3449639.3459352
[28]	H. G. Beyer, The Theory of Evolution Strategies, Springer Science & Business Media, Berlin, Germany, 2001. https://doi.org/10.1007/978-3-662-04448-3_6
[29]	T. Kötzing, Concentration of first hitting times under additive drift, Algorithmica, 75 (2016), 490–506.
[30]	J. He, X. Yao, Drift analysis and average time complexity of evolutionary algorithms, Artif. Intell., 127 (2001), 57–85. https://doi.org/10.1016/s0004-3702(01)00058-3 doi: 10.1016/s0004-3702(01)00058-3
[31]	K. W. Fang, Symmetric Multivariate and Related Distributions, CRC Press, London, UK, 2018. https://doi.org/10.1201/9781351077040
[32]	A. Agapie, O. Solomon, L. Bădin, Theory of (1 + 1) ES on sphere revisited, IEEE Trans. Evol. Comput., 27 (2023), 938–948. https://doi.org/10.1109/tevc.2022.3217524 doi: 10.1109/tevc.2022.3217524
[33]	H. G. Beyer, Toward a theory of evolution strategies: Some asymptotical results from the (1 + λ)-theory, Evol. Comput., 1 (1993), 165–188. https://doi.org/10.1162/evco.1993.1.2.165 doi: 10.1162/evco.1993.1.2.165

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)