@inproceedings{e8e64e22f3bb4023b58d492e943edc11,
title = "How the (1 + λ) evolutionary algorithm optimizes linear functions",
abstract = "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].",
keywords = "Population-based EA, Runtime analysis, Theory",
author = "Benjamin Doerr and Marvin K{\"u}nnemann",
year = "2013",
month = sep,
day = "2",
doi = "10.1145/2463372.2463569",
language = "English",
isbn = "9781450319638",
series = "GECCO 2013 - Proceedings of the 2013 Genetic and Evolutionary Computation Conference",
pages = "1589--1596",
booktitle = "GECCO 2013 - Proceedings of the 2013 Genetic and Evolutionary Computation Conference",
note = "2013 15th Genetic and Evolutionary Computation Conference, GECCO 2013 ; Conference date: 06-07-2013 Through 10-07-2013",
}