Estimating the runtime of evolutionary programming based on uniform mutation

摘要

Although several studies of running time for evolutionary algorithm (EA) of discrete optimization have been proposed, there are few homologous results for EA of continuous optimization like evolutionary programming. This paper presents a preliminary analysis result for the running time of an EP algorithms based on Uniform Mutation. Defined as the measurement of running time, first hitting time is the iteration time which EP spends in converging in the optimal. Hence, this paper proposes a first-hitting-time framework for estimating the running time of EP based on an absorbing Markov process model. Later, the framework is used to calculate an upper bound and a lower bound of the mean first hitting time of Uniform Mutation EP. It can be indicated that the upper bounds are influenced directly by population size, problem size, searching range and the Lebesgue measure of the optimal ε neighborhood.