高级检索

    进化规划算法的时间复杂度分析

    Time Complexity of Evolutionary Programming

    • 摘要: 进化规划算法是求解连续优化问题的一类进化算法,是进化计算的一个重要分支.在进化规划算法的理论研究上,已有学者证明了其收敛性.然而,进化规划算法的时间复杂度分析是进化计算领域一大难题,目前相关的研究成果很少.基于吸收态Markov过程模型,以期望收敛时间作为研究进化规划算法时间复杂度的指标,提出了进化规划算法期望收敛时间的估算方法,并以此作为算法时间复杂度分析的理论依据.最后分析了Gauss变异进化规划算法的期望收敛时间,作为提出理论的应用举例.

       

      Abstract: 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 bounds 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.

       

    /

    返回文章
    返回