A rigorous proof of a fundamental theorem in the drift analysis of evolutionary algorithms
Yu-Shan Zhang, Zhifeng Hao, Yu-Shan Zhang, Han Pang Huang · 2010
A fundamental theorem in the drift analysis of EAs was initially presented in Jun He and Xin Yao's paper(Artificial Intelligence 127(1) (2001) 57-85). However, the theorem remained defective in spite of its successful applications in some specific cases. This paper points out those defects, then suggests some modifications on the theorem and introduces a new and rigorous proof. This work is expected to contribute to the solid foundation of runtime analysis of Evolutionary Algorithms.