Drift analysis in studying the convergence and hitting times of evolutionary algorithms: An overview

This paper introduces drift analysis approach in studying the convergence and hitting times of evolutionary algorithms. First the methodology of drift analysis is introduced, which links evolutionary algorithms with Markov chains or supermartingales. Then the drift conditions which guarantee the convergence of evolutionary algorithms are described. And next the drift conditions which are used to estimate the hitting times of evolutionary algorithms are presented. Finally an example is given to show how to analyse hitting times of EAs by drift analysis approach. Foundation item: Supported by Engineering and Physical Science Research Courcil (GR R52541 01) and State Laboratory of Software Engineering Foundation item: Supported by Engineering and Physical Science Research Courcil (GR R52541 01) and State Laboratory of Software Engineering Biography: He Jun( 1967-), male, visiting fellow at State Key Lab of Software Engineering, Ph D. , research direction: computational intelligence