Non-existence of linear universal drift functions (Q428906)

The article is concerned with the expected time of the (1+1) evolutionary algorithm on the class of linear functions \(f : \{0, 1\}^n \to {\mathbb R}\). The (1+1) evolutionary algorithm is the most simple evolutionary algorithm that is still useful. Its expected optimization time on linear functions is a fundamental problem that has been studied for more than 10 years and it has lead to the development of analytical tools that proved to be important and useful in the analysis of evolutionary algorithms and other randomized search heuristics. The authors give a good and useful overview of the development of the study of this problem. They are concerned with a more general version of the problem where the probability to flip a single bit, the so-called mutation probability, is given by \(c/n\) for some positive constant \(c\). In the standard version one considers the case \(c=1\). While for the standard case an elegant proof using drift analysis is known, the proofs for the general case with \(c>1\) are much more involved. In this article the authors prove that this is necessary in the following sense. They prove that there is no single drift function that can be used for all \(c>1\) to prove the tight upper bound \(O(n\log n)\) for all linear functions using the currently known drift theorems. The proof is carried out by showing that already for two well-known specific linear functions different drift functions are required.