Optimal parameter choices via precise black-box analysis
Proceedings of the Genetic and Evolutionary Computation Conference 2016, 2016•dl.acm.org
In classical runtime analysis it has been observed that certain working principles of an
evolutionary algorithm cannot be understood by only looking at the asymptotic order of the
runtime, but that more precise estimates are needed. In this work we demonstrate that the
same observation applies to black-box complexity analysis. We prove that the unary
unbiased black-box complexity of the classic OneMax function class is n ln (n)--cn±o (n) for a
constant c between 0.2539 and 0.2665. Our analysis yields a simple (1+ 1)-type algorithm …
evolutionary algorithm cannot be understood by only looking at the asymptotic order of the
runtime, but that more precise estimates are needed. In this work we demonstrate that the
same observation applies to black-box complexity analysis. We prove that the unary
unbiased black-box complexity of the classic OneMax function class is n ln (n)--cn±o (n) for a
constant c between 0.2539 and 0.2665. Our analysis yields a simple (1+ 1)-type algorithm …
In classical runtime analysis it has been observed that certain working principles of an evolutionary algorithm cannot be understood by only looking at the asymptotic order of the runtime, but that more precise estimates are needed. In this work we demonstrate that the same observation applies to black-box complexity analysis. We prove that the unary unbiased black-box complexity of the classic OneMax function class is n ln(n) -- cn ± o(n) for a constant c between 0.2539 and 0.2665. Our analysis yields a simple (1+1)-type algorithm achieving this runtime bound via a fitness-dependent mutation strength. When translated into a fixed-budget perspective, our algorithm with the same budget computes a solution that asymptotically is 13% closer to the optimum (given that the budget is at least 0.2675n).
ACM Digital Library