Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal
For researchers in evolutionary computation, this provides a tighter runtime analysis for a classic benchmark function, though the improvement is incremental.
The paper improves the upper bound on the runtime of the (μ+1) EA on the BinVal function from O(μ^5 n log(n/μ^4)) to O(μ log μ · n log n) when μ = o(n/log n), showing it is at most a factor O(log μ · log n) slower than on OneMax.
We study the $(μ+1)$ EA on the Binary Value function BinVal. We show that it needs at most $O(μ\log μ\cdot n \log n)$ function evaluations to find the optimum when $μ= o(n/\log n)$. This substantially improves upon the recent upper bound of $O(μ^5 n \log(n/μ^4))$ by Krejca, Neumann and Witt. Our results hold for several mutation operators including standard bit mutation. In particular, our bound implies that the $(μ+1)$ EA is at most a factor $O(\log μ\cdot \log n)$ slower on BinVal than on OneMax.