连续型演化算法首达时间分析的平均增益模型
|
摘要
连续型演化算法(Evolutionary Algorithms,EAs)的计算时间分析(Runtime analysis)是演化计算理论研究中的难点和热点问题,相较于离散型演化算法,有关前者的理论结果相对较少,数学基础较为薄弱.该文引入鞅论和停时理论,建立了平均增益模型,以估算连续型演化算法的平均首达时间(Expected First Hitting Time,EFHT)上界.平均增益模型建立在一个非负随机过程的基础上,不依赖于算法具体的实现形式.论文介绍了如何应用该模型进行连续型演化算法的计算时间分析.作为案例分析,研究分析了:(1)带自适应步长的非精英(1,λ)ES(Evolution Strategy)求解球函数问题的平均首达时间,得到了3维情形下的时间上界的闭合表达式,并讨论了确保算法收敛条件下步长与子代种群规模λ之间的关系;(2)(1+λ)ES求解2维倾斜平面问题的平均首达时间,得到了上界的闭合表达式.数值实验的结果表明实际的平均首达时间与理论计算的上界吻合.理论分析和实验结果表明平均增益模型有助于获得连续型演化算法平均首达时间紧致的上界,为连续型演化算法的计算时间分析提供了一种新的有效方法.
Runtime analysis of continuous evolutionary algorithms(EAs)is a challenging,hard and hot topic in the theoretical foundation research of evolutionary computation,relatively few theoretical results have been derived compared to the discrete EAs.In this paper,we introduce the stopping time and martingale theory to establish an average gain model to estimate the upper bound for the expected first hitting time of continuous EAs.We regard the first hitting time as a stopping time,the proposed model is established on a non-negative stochastic process,and does not depend on the specific realization of the algorithm.Roughly speaking,the average gain can be considered to be the average one step size varying with the generation's status.In the part of theoretical framework,firstly, we use martingale's property and the Lebesgue dominated convergence theorem to prove a theoretical results on the upper bound of the first hitting time when the lower bound of the average gain is a constant,then,we consider the case that the lower bound of the average gain depends on the t-th generation of population,and derive a tight upper bound for the first hitting time of continuous EAs through integral computation.To demonstrate how the theoretical framework is applied to analyzing the first hitting time of continuous EAs on specific problem,we select two classical problems as case studies.We analyze(1)the expected first hitting time of the non-elitist(1,λ)ES with adaptive step-size solving the Sphere function problem,and derive a closed-form expression of the first hitting time upper bound for 3-dimensional case.We also discuss the relationship between the step size and the offspring sizeλto ensure the convergence of EA;(2)the expected first hitting time of the(1+λ)ES with uniform distribution mutation operator on the 2-dimensional inclined plane,and derive a closed-form expression of the time upper bound.The numerical experimental results show that the practical expected first hitting time is not only lower than the theoretical upper bound but also very close,this means that the proposed model can be used to obtain tight upper bounds for the expected first hitting time of continuous EAs.Both the theoretical analysis and the numerical experimental results show that our model can be effective for the precise runtime analysis of continuous evolutionary algorithms.
Runtime analysis of continuous evolutionary algorithms(EAs)is a challenging,hard and hot topic in the theoretical foundation research of evolutionary computation,relatively few theoretical results have been derived compared to the discrete EAs.In this paper,we introduce the stopping time and martingale theory to establish an average gain model to estimate the upper bound for the expected first hitting time of continuous EAs.We regard the first hitting time as a stopping time,the proposed model is established on a non-negative stochastic process,and does not depend on the specific realization of the algorithm.Roughly speaking,the average gain can be considered to be the average one step size varying with the generation's status.In the part of theoretical framework,firstly, we use martingale's property and the Lebesgue dominated convergence theorem to prove a theoretical results on the upper bound of the first hitting time when the lower bound of the average gain is a constant,then,we consider the case that the lower bound of the average gain depends on the t-th generation of population,and derive a tight upper bound for the first hitting time of continuous EAs through integral computation.To demonstrate how the theoretical framework is applied to analyzing the first hitting time of continuous EAs on specific problem,we select two classical problems as case studies.We analyze(1)the expected first hitting time of the non-elitist(1,λ)ES with adaptive step-size solving the Sphere function problem,and derive a closed-form expression of the first hitting time upper bound for 3-dimensional case.We also discuss the relationship between the step size and the offspring sizeλto ensure the convergence of EA;(2)the expected first hitting time of the(1+λ)ES with uniform distribution mutation operator on the 2-dimensional inclined plane,and derive a closed-form expression of the time upper bound.The numerical experimental results show that the practical expected first hitting time is not only lower than the theoretical upper bound but also very close,this means that the proposed model can be used to obtain tight upper bounds for the expected first hitting time of continuous EAs.Both the theoretical analysis and the numerical experimental results show that our model can be effective for the precise runtime analysis of continuous evolutionary algorithms.
引文
[1]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
[2]Yao X.Unpacking and understanding evolutionary algorithms//Proceedings of the WCCI 2012.Berlin,Germany,2012:60-76
[3]Doerr B,Johannsen D,Winzen C.Multiplicative drift analysis.Algorithmica,2012,64(4):673-697
[4]Droste S,Jansen T,Wegener I.On the analysis of the(1+1)evolutionary algorithm.Theoretical Computer Science,2002,276(1-2):51-81
[5]Wegener I.Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions//Sarker R,Mohammadian M,Yao X eds.Evolutionary Optimization.Norwell,USA:Kluwer Academic Publishers,2002:349-369
[6]He J,Yao X.Drift analysis and average time complexity of evolutionary algorithms.Artificial Intelligence,2001,127(1):57-85
[7]Oliveto P S,He J,Yao X.Analysis of the(1+1)EA for finding approximate solutions to vertex cover problems.IEEE Transactions on Evolutionary Computation,2009,13(5):1006-1029
[8]Lehre P K,Yao X.Runtime analysis of the(1+1)EA on computing unique input output sequences.Information Sciences,2014,259(1):510-531
[9]Lai X S,Zhou Y R,He J,et al.Performance analysis of evolutionary algorithms for the minimum label spanning tree problem.IEEE Transactions on Evolutionary Computation,2014,18(6):860-872
[10]Zhou Y R,Zhang J,Wang Y.Performance analysis of the(1+1)evolutionary algorithm for the multiprocessor scheduling problem.Algorithmica,2015,73(1):21-41
[11]Zhou Y R,Lai X S,Li K.Approximation and parameterized runtime analysis of evolutionary algorithms for the maximum cut problem.IEEE Transactions on Cybernetics,2015,45(8):1491-1498
[12]Xia X,Zhou Y R,Lai X S.On the analysis of the(1+1)evolutionary algorithm for the maximum leaf spanning tree problem.International Journal of Computer Mathematics,2015,92(10):2023-2035
[13]He J,Yao X.Towards an analytic framework for analysing the computation time of evolutionary algorithms.Artificial Intelligence,2003,145(1-2):59-97
[14]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
[15]Yu Y,Qian C,Zhou Z H.Switch analysis for running time analysis of evolutionary algorithms.IEEE Transactions on Evolutionary Computation,2015,19(6):777-792
[16]Sudholt D.A new method for lower bounds on the running time of evolutionary algorithms.IEEE Transactions on Evolutionary Computation,2013,17(3):418-435
[17]Witt C.Fitness levels with tail bounds for the analysis of randomized search heuristics.Information Processing Letters,2014,114(1-2):38-41
[18]J?gersküpper J.Combining Markov-chain analysis and drift analysis:The(1+1)evolutionary algorithm on linear functions reloaded.Algorithmica,2011,59(3):409-424
[19]Chen T S,He J,Sun G,et al.A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems.IEEE Transactions on Systems,Man,and Cybernetics,Part B(Cybernetics),2009,39(5):1092-1106
[20]Oliveto P S,Witt C.Simplified drift analysis for proving lower bounds in evolutionary computation.Algorithmica,2011,59(3):369-386
[21]Rowe J,Sudholt D.The choice of the offspring population size in the(1,λ)EA//Proceedings of the GECCO’12.New York,USA,2012:1349-1356
[22]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
[23]Droste S.Analysis of the(1+1)EA for a noisy OneMax//Proceedings of the 6th ACM Conference on Genetic and Evolutionary Computation.Seattle,USA,2004:1088-1099
[24]Qian C,Yu Y,Zhou Z H.Analyzing evolutionary optimization in noisy environments.Evolutionary Computation,2015,doi:10.1162/EVCO_a_00170
[25]Qian C,Yu Y,Jin Y,et al.On the effectiveness of sampling for evolutionary optimization in noisy environments.Evolutionary Computation,2016,3(1):35-55
[26]J?gersküpper J.Algorithmic analysis of a basic evolutionary algorithm for continuous optimization.Theoretical Computing Science,2007,379(3):329-347
[27]J?gersküpper J.Lower bounds for randomized direct search with isotropic sampling.Operations Research Letters,2008,36(3):327-332
[28]Agapie A,Agapie M,Baganu G.Evolutionary algorithms for continuous-space optimisation.International Journal of Systems Science,2013,44(3):502-512
[29]Zhang Yu-Shan,Hao Zhi-Feng,Huang Han,et al.Astopping time theory model of first hitting time analysis of evolutionary algorithms.Chinese Journal of Computers,2015,38(8):1582-1591(in Chinese)(张宇山,郝志峰,黄翰等.进化算法首达时间分析的停时理论模型.计算机学报,2015,38(8):1582-1591)
[30]Chen Y,Zou X F,He J.Drift conditions for estimating the first hitting times of evolutionary algorithms.International Journal of Computer Mathematics,2011,88(1):37-50
[31]Huang Han,Xu Wei-Di,Zhang Yu-Shan,et al.Runtime analysis for continuous(1+1)evolutionary algorithm based on average gain model.Scientia Sinica Informationis,2014,44(6):811-824(in Chinese)(黄翰,徐威迪,张宇山等.基于平均增益模型的连续型(1+1)进化算法计算时间复杂性分析.中国科学F辑:信息科学,2014,44(6):811-824)
[32]Zhang Bo,Zhang Jing-Xiao.Applied Stochastic Processes.Beijing:Tsinghua University Press,2004(in Chinese)(张波,张景肖.应用随机过程.北京:清华大学出版社,2004)
[33]Xu Zong-Ben,Nie Zan-Kan,Zhang Wen-Xiu.Almost sure convergence of genetic algorithms:A martingale approach.Chinese Journal of Computers,2002,25(8):785-793(in Chinese)(徐宗本,聂赞坎,张文修.遗传算法的几乎必然强收敛性---鞅方法.计算机学报,2002,25(8):785-793
[34]Schumer M A,Steiglitz K.Adaptive step size random search.IEEE Transactions on Automatic Control,1968,13:270-276
[2]Yao X.Unpacking and understanding evolutionary algorithms//Proceedings of the WCCI 2012.Berlin,Germany,2012:60-76
[3]Doerr B,Johannsen D,Winzen C.Multiplicative drift analysis.Algorithmica,2012,64(4):673-697
[4]Droste S,Jansen T,Wegener I.On the analysis of the(1+1)evolutionary algorithm.Theoretical Computer Science,2002,276(1-2):51-81
[5]Wegener I.Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions//Sarker R,Mohammadian M,Yao X eds.Evolutionary Optimization.Norwell,USA:Kluwer Academic Publishers,2002:349-369
[6]He J,Yao X.Drift analysis and average time complexity of evolutionary algorithms.Artificial Intelligence,2001,127(1):57-85
[7]Oliveto P S,He J,Yao X.Analysis of the(1+1)EA for finding approximate solutions to vertex cover problems.IEEE Transactions on Evolutionary Computation,2009,13(5):1006-1029
[8]Lehre P K,Yao X.Runtime analysis of the(1+1)EA on computing unique input output sequences.Information Sciences,2014,259(1):510-531
[9]Lai X S,Zhou Y R,He J,et al.Performance analysis of evolutionary algorithms for the minimum label spanning tree problem.IEEE Transactions on Evolutionary Computation,2014,18(6):860-872
[10]Zhou Y R,Zhang J,Wang Y.Performance analysis of the(1+1)evolutionary algorithm for the multiprocessor scheduling problem.Algorithmica,2015,73(1):21-41
[11]Zhou Y R,Lai X S,Li K.Approximation and parameterized runtime analysis of evolutionary algorithms for the maximum cut problem.IEEE Transactions on Cybernetics,2015,45(8):1491-1498
[12]Xia X,Zhou Y R,Lai X S.On the analysis of the(1+1)evolutionary algorithm for the maximum leaf spanning tree problem.International Journal of Computer Mathematics,2015,92(10):2023-2035
[13]He J,Yao X.Towards an analytic framework for analysing the computation time of evolutionary algorithms.Artificial Intelligence,2003,145(1-2):59-97
[14]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
[15]Yu Y,Qian C,Zhou Z H.Switch analysis for running time analysis of evolutionary algorithms.IEEE Transactions on Evolutionary Computation,2015,19(6):777-792
[16]Sudholt D.A new method for lower bounds on the running time of evolutionary algorithms.IEEE Transactions on Evolutionary Computation,2013,17(3):418-435
[17]Witt C.Fitness levels with tail bounds for the analysis of randomized search heuristics.Information Processing Letters,2014,114(1-2):38-41
[18]J?gersküpper J.Combining Markov-chain analysis and drift analysis:The(1+1)evolutionary algorithm on linear functions reloaded.Algorithmica,2011,59(3):409-424
[19]Chen T S,He J,Sun G,et al.A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems.IEEE Transactions on Systems,Man,and Cybernetics,Part B(Cybernetics),2009,39(5):1092-1106
[20]Oliveto P S,Witt C.Simplified drift analysis for proving lower bounds in evolutionary computation.Algorithmica,2011,59(3):369-386
[21]Rowe J,Sudholt D.The choice of the offspring population size in the(1,λ)EA//Proceedings of the GECCO’12.New York,USA,2012:1349-1356
[22]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
[23]Droste S.Analysis of the(1+1)EA for a noisy OneMax//Proceedings of the 6th ACM Conference on Genetic and Evolutionary Computation.Seattle,USA,2004:1088-1099
[24]Qian C,Yu Y,Zhou Z H.Analyzing evolutionary optimization in noisy environments.Evolutionary Computation,2015,doi:10.1162/EVCO_a_00170
[25]Qian C,Yu Y,Jin Y,et al.On the effectiveness of sampling for evolutionary optimization in noisy environments.Evolutionary Computation,2016,3(1):35-55
[26]J?gersküpper J.Algorithmic analysis of a basic evolutionary algorithm for continuous optimization.Theoretical Computing Science,2007,379(3):329-347
[27]J?gersküpper J.Lower bounds for randomized direct search with isotropic sampling.Operations Research Letters,2008,36(3):327-332
[28]Agapie A,Agapie M,Baganu G.Evolutionary algorithms for continuous-space optimisation.International Journal of Systems Science,2013,44(3):502-512
[29]Zhang Yu-Shan,Hao Zhi-Feng,Huang Han,et al.Astopping time theory model of first hitting time analysis of evolutionary algorithms.Chinese Journal of Computers,2015,38(8):1582-1591(in Chinese)(张宇山,郝志峰,黄翰等.进化算法首达时间分析的停时理论模型.计算机学报,2015,38(8):1582-1591)
[30]Chen Y,Zou X F,He J.Drift conditions for estimating the first hitting times of evolutionary algorithms.International Journal of Computer Mathematics,2011,88(1):37-50
[31]Huang Han,Xu Wei-Di,Zhang Yu-Shan,et al.Runtime analysis for continuous(1+1)evolutionary algorithm based on average gain model.Scientia Sinica Informationis,2014,44(6):811-824(in Chinese)(黄翰,徐威迪,张宇山等.基于平均增益模型的连续型(1+1)进化算法计算时间复杂性分析.中国科学F辑:信息科学,2014,44(6):811-824)
[32]Zhang Bo,Zhang Jing-Xiao.Applied Stochastic Processes.Beijing:Tsinghua University Press,2004(in Chinese)(张波,张景肖.应用随机过程.北京:清华大学出版社,2004)
[33]Xu Zong-Ben,Nie Zan-Kan,Zhang Wen-Xiu.Almost sure convergence of genetic algorithms:A martingale approach.Chinese Journal of Computers,2002,25(8):785-793(in Chinese)(徐宗本,聂赞坎,张文修.遗传算法的几乎必然强收敛性---鞅方法.计算机学报,2002,25(8):785-793
[34]Schumer M A,Steiglitz K.Adaptive step size random search.IEEE Transactions on Automatic Control,1968,13:270-276