Note on drift analysis
Xinsheng Lai · Computer Engineering and Applications Journal · 2012
In spite of many successful applications of evolutionary algorithms in various complicated optimization problems, the rigorous theoretical analyses of EAs are still in their infant period. The running time of an evolutionary algorithm for combination optimization problem is an important topic in theoretical study of EAs. This paper discusses the relation between drift analysis and evolutionary algorithms’time complexity. It gives a new proof of the drift theorem. It also uses drift theorem to estimate the expected runtime of global(1+1)for linear function. The result is a better understanding of the performance of evolutionary algorithms.