Drift Analysis and Linear Functions Revisited

We regard the classical problem how the (1+1)~Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. We show that any such function is optimized in time ${(1+o(1)) 1.39 e n\ln (n)}$, where ${n}$ is the length of the bit string. We also prove a lower bound of ${(1-o(1))e n\ln(n)}$, which in fact holds for all functions with a unique global optimum. This shows that for linear functions, even though the optimization behavior might differ, the resulting runtimes are very similar. Our experimental results suggest that the true optimization times are even closer than what the theoretical guarantees promise