摘要
进化规划算法是求解连续优化问题的一类进化算法,是进化计算的一个重要分支.在进化规划算法的理论研究上,已有学者证明了其收敛性.然而,进化规划算法的时间复杂度分析是进化计算领域一大难题,目前相关的研究成果很少.基于吸收态Markov过程模型,以期望收敛时间作为研究进化规划算法时间复杂度的指标,提出了进化规划算法期望收敛时间的估算方法,并以此作为算法时间复杂度分析的理论依据.最后分析了Gauss变异进化规划算法的期望收敛时间,作为提出理论的应用举例.
As a method of evolutionary computation, evolutionary programming（EP） algorithm is an evolutionary algorithm for continuous optimization problems. The convergence of EP has been proved, but there are few studies on the time complexity of EP, which is one of the hard problems in evolutionary computation. EP algorithm can be modeled as an absorbing Markov process because of its comparison selection. The item called average convergence time is used to propose a method to analyze the time complexity of EP algorithm based on absorbing Markov process model. The average convergence time can be calculated with the probability that the EP algorithm attains the optimal solution in the next iteration but not in the current iteration. A direct approach to estimate the convergence time is given as a theorem. Furthermore, the corollaries of the theorem indicate the way to estimate the hounds of the convergence time. The convergence time reveals how many iteration times the EP algorithm uses to converge to the optimal solution. Therefore, the proposed theorem and corollaries can be considered as the time complexity theory for the foundation of evolutionary programming. Finally, the average convergence time of Gauss-mutation evolutionary programming is analyzed as an application case study of the proposed theory.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2008年第11期1850-1857,共8页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60433020
10471045)
广东省自然科学基金项目(970472
000463
04020079
05011896)
广东省教育部产学研结合基金项目(2007B090400031)~~
关键词
进化计算
进化规划算法
时间复杂度
期望收敛时间
Gauss变异
evolutionary computation
evolutionary programming algorithm
time complexity
average convergence time
Gauss mutation
