A variant of Variable-Drift theorem for continuous (1+1)-Evolutionary Algorithm

The computational time complexity is an important topic in the theory of Evolutionary Algorithms (EAs). The analysis in continuous space function is rare nowadays in comparison to that in discrete space. In this paper, we extend the general drift theory to analyze the complexity of optimization problem in continuous space, by proposing a new version of Variable Drift-Johannsen theorem. Comparing with general drift analysis, we establish a tighter upper bound for continuous optimization by integration for every problem that is monotonic in drift. Finally, we apply the proposed theory to a continuous (1+1)EA algorithm which is the basic framework of evolutionary algorithm(EA) in continuous space. The continuous (1+1)EA is similar with (1+1)EA except for its elitism strategy. In addition, its solutions are transferred to continuous space and mutations are implemented randomly by obeying one single probability distribution. It means that the continuous (1+1)EA requires exponential time complexity. Both the upper and lower bounds of the (1+1)EA with the mutation of (0,1)-normal distribution are bounding above that of the (1+1)EA with the mutation of (¿1,1)-uniform distribution. This means that the (1+1)EA with the mutation of (0,1)-normal distribution outperforms the (1+1)EA with the mutation of (¿1,1)-uniform distribution in reaching the optimum of sphere function.