Global Convergence and Premature Convergence of Two-Membered Evolution Strategy

The theory of discrete state Markov chain has been applied widely to the analysis of convergence and time complexity of the evolutionary algorithms, and the application of the theory of continuous state Markov process is relatively few and not systematic due to the adoption of some profound mathematical tools. In this article, we introduce the theory of continuous state Markov process, use the measure theory and conditional mathematical expectation theory as tools to deduce a key calculation formula of the transition probability. We analyze the convergence property of the continuous evolutionary algorithms represented by (1+1)ES; prove theoretically that a wide class of common mutation distributions including normal distribution and Cauchy distribution, if satisfying some specified conditions which are not difficult to meet in practice, can cause (1+1)ES to converge in probability to the ε-vicinity of global optimum if the constant mutation operator is adopted; construct a function with fitness plateau and prove theoretically that some self-adaptive mutation operators can plunge (1+1)ES into premature convergence even if normal distribution and Cauchy distribution are adopted as mutation distribution. The theoretical analysis is validated by simulation experiment. The results show that self-adaptive mechanism is not always effective, and the scale factor should be selected properly.