Run-Time Analysis of the (1+1) Evolutionary Algorithm Optimizing Linear Functions Over a Finite Alphabet

摘要

We analyze the run-time of the (1 + 1) Evolutionary Algorithm optimizing an arbitrary linear function ? : {0,1,...,r}~n → R. If the mutation probability of the algorithm is p = c/n, then (1 + o(1))(e~c/c)rn log n + O(r~3n 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.