Renewal Theory Model of First Hitting Time Analysis for Continuous Evolutionary Algorithms
ZHOU Zhensheng1,2, WANG Lin2, FENG Fujian1,2, TAN Mian1,2, HE Xing2, ZHANG Zaijun3
1. School of Data Sciences and Information Engineering, Guizhou Minzu University, Guiyang 550025; 2. Key Laboratory of Pattern Recognition and Intelligent Systems of Guizhou Province, Guizhou Minzu University, Guiyang 550025; 3. School of Mathematics and Statistics, Qiannan Normal University for Nationalities, Duyun 558000
Abstract：In the research on upper bound of the first hitting time for continuous evolutionary algorithms,strong assumptions are required and less attention is given to its lower bound . In this paper, martingale theory and renewal process are introduced and combined with Wald's inequality and renewal theorem. A renewal theory model based on progress rate is proposed to estimate the upper and lower bounds of the expected first hitting time of evolution strategies. The renewal theory model relies on the initial population and the probability density function of the progress rate, providing an estimation advantage for the analysis of the first hitting time of evolutionary strategies. To verify the validity of the proposed renewal theory model, experiments are conducted to estimate the expected first hitting time. Firstly, the expected first hitting time of (1,λ)evolution strategies with uniform mutation on a two-dimensional inclined plane problem is calculated. The closed-form expression for the relationship between(1,λ)evolution strategies population size and the time upper and lower bounds is obtained. It is proved that the expected first hitting time is not negatively correlated with the population size. Next, the expected first hitting time of evolution strategies with uniform mutation on a five-dimensional hyperplane problem is calculated, and the closed-form expression for theoretical upper and lower bounds is derived. Numerical experiments show that the theoretically calculated upper and lower bounds are consistent with the actual expected first hitting time, which provides a theoretical tool for analyzing the first hitting time of evolution strategies.
周珍胜, 王林, 冯夫健, 谭棉, 何兴, 张再军. 连续型进化算法首达时间分析的更新理论模型[J]. 模式识别与人工智能, 2023, 36(10): 918-930.
ZHOU Zhensheng, WANG Lin, FENG Fujian, TAN Mian, HE Xing, ZHANG Zaijun. Renewal Theory Model of First Hitting Time Analysis for Continuous Evolutionary Algorithms. Pattern Recognition and Artificial Intelligence, 2023, 36(10): 918-930.
[1] BÄCK T, SCHWEFEL H P. An Overview of Evolutionary Algorithms for Parameter Optimization. Evolutionary Computation, 1993, 1(1). DOI: 10.1162/evco.1993.1.1.1. [2] HE J, YAO X. Average Drift Analysis and Population Scalability. IEEE Transactions on Evolutionary Computation, 2017, 21(3): 426-439. [3] YAO X. Unpacking and Understanding Evolutionary Algorithms // Proc of the IEEE World Congress on Computational Intelligence. Washington, USA: IEEE, 2012: 60-76. [4] OLIVETO P S, HE J, YAO X. Time Complexity of Evolutionary Algorithms for Combinatorial Optimization: A Decade of Results. International Journal of Automation and Computing, 2007, 4(3): 281-293. [5] HE J, YAO X. Drift Analysis and Average Time Complexity of Evolutionary Algorithms. Artificial intelligence, 2001, 127(1): 57-85. [6] HE J, YAO X. Towards an Analytic Framework for Analysing the Computation Time of Evolutionary Algorithms. Artificial Intelligence, 2003, 145(1/2): 59-97. [7] YU Y, ZHOU Z H. A New Approach to Estimating the Expected First Hitting Time of Evolutionary Algorithms. Artificial Intelligence, 2008, 172(15): 1809-1832. [8] LENGLER J, STEGER A. Drift Analysis and Evolutionary Algorithms Revisited. Combinatorics, Probability and Computing, 2018, 27(4): 643-666. [9] YU Y, QIAN C, ZHOU Z H. Switch Analysis for Running Time Analysis of Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 2014, 19(6): 777-792. [10] WEGENER I. Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions[C/OL]. [2023-2-06]. https://www.researchgate.net/publication/225910965_Methods_for_the_Analysis_of_Evolutionary_Algorithms_on_Pseudo-Boolean_Functions. [11] HUANG H, SU J P, ZHANG Y S, et al. An Experimental Method to Estimate Running Time of Evolutionary Algorithms for Continuous Optimization. IEEE Transactions on Evolutionary Computation, 2020, 24(2): 275-289. [12] 冯夫健,黄翰,张宇山,等.基于等同关系模型的演化算法期望首达时间对比分析.计算机学报, 2019, 42(10): 2297-2308. (FENG F J, HUANG H, ZHANG Y S, et al. Comparative Analysis for First Hitting Time of Evolutionary Algorithms Based on Equal-in-Time Model. Chinese Journal of Computers, 2019, 42(10): 2297-2308.) [13] WITT C. Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions. Combinatorics, Probability and Computing, 2013, 22(2): 294-318. [14] DOERR B, DOERR C, KÖTZING T. Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables. Algorithmica, 2018, 80(5): 1732-1768. [15] DOERR B, KÖTZING T, LAGODZINSKI J A G, et al. The Impact of Lexicographic Parsimony Pressure for Order/Majority on the Run Time. Theoretical Computer Science, 2020, 816: 144-168. [16] DOERR B, DOERR C, YANG J. Optimal Parameter Choices via Precise Black-Box Analysis. Theoretical Computer Science, 2020, 801. DOI: 10.1016/j.tcs.2019.06.014. [17] LEHRE P K, WITT C. Tail Bounds on Hitting Times of Rando-mized Search Heuristics Using Variable Drift Analysis. Combinatorics, Probability and Computing, 2021, 30(4): 550-569. [18] GIEβEN C, WITT C. Optimal Mutation Rates for the (1+λ)EA on OneMax through Asymptotically Tight Drift Analysis. Algorithmica, 2018, 80(5): 1710-1731. [19] JIANG W, QIAN C, TANG K. Improved Running Time Analysis of the (1+1)-ES on the Sphere Function // Proc of the 14th International Conference on Intelligent Computing. Berlin, Germany: Springer, 2018: 729-739. [20] 张宇山,郝志峰,黄翰,等.进化算法首达时间分析的停时理论模型.计算机学报, 2015, 38(8): 1582-1591. (ZHANG Y S, HAO Z F, HUANG H, et al. A Stopping Time Theory Model of First Hitting Time Analysis of Evolutionary Algorithms. Chinese Journal of Computers, 2015, 38(8): 1582-1591.) [21] AGAPIE A, SOLOMON O, BǍDIN L. Theory of (1+1)ES on SPHERE Revisited. IEEE Transactions on Evolutionary Computation, 2023, 27(4): 938-948. [22] JÄGERSKÜPPER J. Algorithmic Analysis of a Basic Evolutionary Algorithm for Continuous Optimization. Theoretical Computer Science, 2007, 379(3): 329-347. [23] AGAPIE A, AGAPIE M, ZBAGANU G. Evolutionary Algorithms for Continuous-Space Optimisation. International Journal of Systems Science, 2013, 44(3): 502-512. [24] 张宇山,黄翰,郝志峰,等.连续型演化算法首达时间分析的平均增益模型.计算机学报, 2019, 42(3): 624-634. (ZHANG Y S, HUANG H, HAO Z F, et al. An Average Gain Model to Analyze the First Hitting Time of Continuous Evolutionary Algorithms. Chinese Journal of Computers, 2019, 42(3): 624-634.) [25] DIOUANE Y, GRATTON S, VICENTE L N. Globally Convergent Evolution Strategies. Mathematical Programming, 2015, 152: 467-490. [26] BEYER H G. The Theory of Evolution Strategies. Berlin, Germany: Springer Science & Business Media, 2001. [27] AKIMOTO Y, AUGER A, HANSEN N. Quality Gain Analysis of the Weighted Recombination Evolution Strategy on General Convex Quadratic Functions. Theoretical Computer Science, 2020, 832: 42-67. [28] NEUMANN F, WITT C. Runtime Analysis of the (1+1)EA on Weighted Sums of Transformed Linear Functions // Proc of the International Conference on Parallel Problem Solving from Nature. Berlin, Germany: Springer, 2022: 542-554. [29] DOERR B, KÖTZING T. Lower Bounds from Fitness Levels Made Easy // Proc of the Genetic and Evolutionary Computation Confe-rence. New York, USA: ACM, 2021: 1142-1150. [30] KÖTZING T. Concentration of First Hitting Times under Additive Drift. Algorithmica, 2016, 75(3): 490-506. [31] SHI F, SCHIRNECK M, FRIEDRICH T, et al. Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions under Dynamic Uniform Constraints. Algorithmica, 2019, 81(2): 828-857. [32] AGAPIE A, SOLOMON O, GIUCLEA M. Theory of (1+1)ES on the RIDGE. IEEE Transactions on Evolutionary Computation, 2022, 26(3): 501-511.
2023, Vol. 36 
