Fixed-target runtime analysis of the (1 + 1) EA with resampling
Dmitry V. Vinokurov, Maxim Buzdalov, Буздалова Арина Сергеевна, Benjamin Doerr, Carola Doerr · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2019
We conduct a fixed-target runtime analysis of (1 + 1) EA with resampling on the OneMax and BinVal problems. For OneMax, our fixed-target upper bound refines the previously known bound. Our fixed-target lower bound for OneMax is the first of this kind. We also consider linear functions and show that the traditional approaches via drift analysis cannot easily be extended to yield fixed-target results. However, for the particular case of BinVal, a relatively precise fixed-target bound is obtained.