Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabet
Carola Doerr, Sebastian Pohl · 2012
We analyze the run-time of the (1 + 1) Evolutionary Algorithm optimizing an arbitrary linear function f : {0,1,...,r}n -> R. If the mutation probability of the algorithm is p = c/n, then (1 + o(1))(ec/c))rn log n + O(r3n log log n) is an upper bound for the expected time needed to find the optimum. We also give a lower bound of (1 + o(1))(1/c)rn log n. Hence for constant c and all r slightly smaller than (log n)1/3, our bounds deviate by only a constant factor, which is e(1 + o(1)) for the standard mutation probability of 1/n. The proof of the upper bound uses multiplicative adaptive drift analysis as developed in a series of recent papers. We cannot close the gap for larger values of r, but find indications that multiplicative drift is not the optimal analysis tool for this case.