TY - GEN
T1 - A tight runtime analysis for the (+) EA
AU - Antipov, Denis
AU - Fang, Jiefeng
AU - Doerr, Benjamin
AU - Hetet, Tangi
N1 - Publisher Copyright:
© 2018 Copyright held by the owner/author(s).
PY - 2018/7/2
Y1 - 2018/7/2
N2 - Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of true population-based evolutionary algorithms remains challenging and only few rigorous results exist. Already for the most basic problem, the determination of the asymptotic runtime of the (+) evolutionary algorithm on the simple OneMax benchmark function, only the special cases = 1 and = 1 have been solved. In this work, we analyze this long-standing problem and show the asymptotically tight result that the runtime T, the number of iterations until the optimum is found, satisfies n n log+ log+ /, E[T ] = Θn logn + + / log+ / where log+ x := max{1, log x } for all x > 0.
AB - Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of true population-based evolutionary algorithms remains challenging and only few rigorous results exist. Already for the most basic problem, the determination of the asymptotic runtime of the (+) evolutionary algorithm on the simple OneMax benchmark function, only the special cases = 1 and = 1 have been solved. In this work, we analyze this long-standing problem and show the asymptotically tight result that the runtime T, the number of iterations until the optimum is found, satisfies n n log+ log+ /, E[T ] = Θn logn + + / log+ / where log+ x := max{1, log x } for all x > 0.
KW - Populations
KW - Runtime Analysis
KW - Theory
UR - https://www.scopus.com/pages/publications/85050588716
U2 - 10.1145/3205455.3205627
DO - 10.1145/3205455.3205627
M3 - Conference contribution
AN - SCOPUS:85050588716
T3 - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
SP - 1459
EP - 1466
BT - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
PB - Association for Computing Machinery, Inc
T2 - 2018 Genetic and Evolutionary Computation Conference, GECCO 2018
Y2 - 15 July 2018 through 19 July 2018
ER -