Optimizing linear functions with the (1+λ) evolutionary algorithm-Different asymptotic runtimes for different instances

We analyze how the (1 + lambda) 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/lambda n logn + n) iterations. We also show that this bound is sharp for some linear functions, e.g., the binary value function. Since previous works shows an asymptotically smaller runtime for the special case of ONEMAX, it follows that for the (1 + lambda) 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 [13]. We also use our methods to analyze the runtime of the (1 + lambda) EA on the ONEMAX test function and obtain a new upper bound of O(n log log lambda/log lambda) for the case that lambda is larger than O(log n log log n/log log log n); this is the cut-off point where a linear speed-up ceases to exist. While our results are mostly spurred from a theory-driven interest, they also show that choosing the right size of the offspring population can be crucial. For both the binary value and the ONEMAX test function we observe that once a linear speed-up ceases to exist, in fact, the speed-up from a larger lambda reduces to sub-logarithmic (still at the price of a linear increase of the cost of each generation). (C) 2014 Elsevier B.V. All rights reserved.