How the (1 + λ) evolutionary algorithm optimizes linear functions

We analyze how the (1 + λ) evolutionary algorithm (EA) optimizes linear pseudo-Boolean functions. We prove that it finds the optimum of any linear function within an expected number of O(1/λn logn + n) iterations. We also show that this bound is sharp for some functions, e.g., the binary value function. Hence unlike for the (1 + 1) EA, for the (1 + λ) EA different linear functions may have run-times of different asymptotic order. The proof of our upper bound heavily relies on a number of classic and recent drift analysis methods. In particular, we show how to analyze a process displaying different types of drifts in different phases. Our work corrects a wrongfully claimed better asymptotic runtime in an earlier work [12].