Time Complexity of Evolutionary Programming

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.