First hitting time analysis of continuous evolutionary algorithms based on average gain

摘要

Runtime analysis of continuous evolutionary algorithms (EAs) is a hard topic in the theoretical research of evolutionary computation, relatively few results have been obtained compared to the discrete EAs. In this paper, we introduce the martingale and stopping time theory to establish a general average gain model to estimate the upper bound for the expected first hitting time. The proposed model is established on a non-negative stochastic process and does not need the assumption of Markov property, thus is more general. Afterwards, we demonstrate how the proposed model can be applied to runtime analysis of continuous EAs. In the end, as a case study, we analyze the runtime of (1, ES with adaptive step-size on Sphere function using the proposed approach, and derive a closed-form expression of the time upper bound for 3-dimensional case. We also discuss the relationship between the step size and the offspring size to ensure convergence. The experimental results show that the proposed approach helps to derive tight upper bound for the expected first hitting time of continuous EAs.