hide
Free keywords:
-
Abstract:
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.
