Average Drift Analysis and its Application

Abstract

Drift analysis is a useful tool for estimating the running time of evolutionary algorithms. A new representation of drift analysis, called average drift analysis, is described in this paper. It takes a weaker requirement than point-wise drift analysis does. Point-wise drift theorems are corollaries of our average drift theorems. Therefore average drift analysis is more powerful than point-wise drift analysis. To demonstrate the application of average drift analysis, we choose a (1+N) evolutionary algorithms for linear-like functions as a case study. Linear-like functions are proposed as a natural extension of linear functions. For the (1+N) evolutionary algorithms to maximise linear-like functions, the lower and upper bounds on their running time have been derived using the average drift analysis.