Improved Running Time Analysis of the (1+1)-ES on the Sphere Function

摘要

During the last two decades, much progress has been achieved on the running time analysis (one essential theoretical aspect) of evolutionary algorithms (EAs). However, most of them focused on discrete optimization, and the theoretical understanding is largely insufficient for continuous optimization. The few studies on evolutionary continuous optimization mainly analyzed the running time of the (1+1)-ES with Gaussian and uniform mutation operators solving the sphere function, the known bounds of which are, however, quite loose compared with the empirical observations. In this paper, we significantly improve their lower bound, i.e., from Ω(n) to Ω(e~(cn)). Then, we study the effectiveness of 1/5-rule, a widely used self-adaptive strategy, for continuous EAs using uniform mutation operator for the first time. We prove that for the (1+1)-ES with uniform mutation operator solving the sphere function, using 1/5-rule can reduce the running time from exponential to polynomial.