Non-existence of linear universal drift functions

Doerr, 2010, Drift analysis and linear functions revisited, 1967

Droste, 2002, On the analysis of the (1+1)~evolutionary algorithm, Theoretical Computer Science, 276, 51, 10.1016/S0304-3975(01)00182-7

He, 2001, Drift analysis and average time complexity of evolutionary algorithms, Artificial Intelligence, 127, 51, 10.1016/S0004-3702(01)00058-3

He, 2004, A study of drift analysis for estimating computation time of evolutionary algorithms, Natural Computing, 3, 21, 10.1023/B:NACO.0000023417.31393.c7

Giel, 2006, On the effect of populations in evolutionary multi-objective optimization, 651

Happ, 2008, Rigorous analyses of fitness-proportional selection for optimizing linear functions, 953

Oliveto, 2011, Simplified drift analysis for proving lower bounds inevolutionary computation, Algorithmica, 59, 369, 10.1007/s00453-010-9387-z

Jägersküpper, 2008, A blend of Markov-chain and drift analysis, 41

C. Witt, Optimizing linear functions with randomized search heuristics — The robustness of mutation, CoRR abs/1108.4386, in: STACS’12: Proceedings of the Symposium on Theoretical Aspects of Computer Science (in press).

Lehre, 2009, On the impact of the mutation-selection balance on the runtime of evolutionary algorithms, 47

Hajek, 1982, Hitting-time and occupation-time bounds implied by drift analysis with applications, Advances in Applied Probability, 14, 387, 10.2307/1426671