Improved Runtime Bound for the $(\hat{I}¼+1)$ EA on BinVal

Abstract

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