Improved Runtime Bound for the $(\mu +1)$ EA on BinVal

We study the $(\mu +1)$ EA on the Binary Value function BinVal. We show that it needs at most $O(\mu \log \mu \cdot n\log n)$ function evaluations to find the optimum when $\mu =o(n\mathrm{/}\log n)$. This substantially improves upon the recent upper bound of $O({\mu }^{5}n\log (n\mathrm{/}{\mu }^4))$ by Krejca, Neumann and Witt. Our results hold for several mutation operators including standard bit mutation. In particular, our bound implies that the $(\mu +1)$ EA is at most a factor $O(\log \mu \cdot \log n)$ slower on BinVal than on OneMax.