The first hitting time analysis of evolutionary algorithms based on renewal process

Abstract

Running time analysis of evolutionary algorithms for continuous optimization is one research challenge in the field of evolutionary algorithms (EAs). However, the theoretical analysis results have rarely been applied to evolutionary algorithms for continuous optimization in practice, let alone their variants for evolution strategy. In this paper, we regarded the first hitting time of evolution strategy as the stopping time of the renewal process on the basis of the renewal process and in combination with Wald's inequality and stopping time theory. Afterwards, to demonstrate the application of the proposed model in the first hitting time analysis of (1 + 1) ES, we analyzed it with different mutation operators on the sphere function. First, we significantly improved the lower bound on the first hitting time of (1 + 1) ES with a uniform mutation operator, i.e., from $\Omega(n)$ to $\Omega\left(e^{c n}\right)$. Next, $O\left(n^{2} \sqrt{n}\right)$ was the upper bound on the first hitting time of (1 + 1) ES with a Gaussian mutation operator from the initial distance R to half of the initial distance R/2. The numerical experimental results showed that the theoretical calculation was consistent with the actual running time, which provides a novel method for analyzing the first hitting time of EAs.

Keywords

• evolutionary algorithms for continuous optimization
• renewal process
• stopping time theory
• first hitting time
• sphere function