TY - GEN
T1 - An exponential lower bound for the runtime of the compact genetic algorithm on jump functions
AU - Doerr, Benjamin
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s).
PY - 2019/8/27
Y1 - 2019/8/27
N2 - In the first runtime analysis of an estimation-of-distribution algorithm (EDA) on the multimodal jump function class, Hasenöhrl and Sutton (GECCO 2018) proved that the runtime of the compact genetic algorithm with suitable parameter choice on jump functions with high probability is at most polynomial (in the dimension) if the jump size is at most logarithmic (in the dimension), and is at most exponential in the jump size if the jump size is super-logarithmic. The exponential runtime guarantee was achieved with a hypothetical population size that is also exponential in the jump size. Consequently, this setting cannot lead to a better runtime. In this work, we show that any choice of the hypothetical population size leads to a runtime that, with high probability, is at least exponential in the jump size. This result might be the first nontrivial exponential lower bound for EDAs that holds for arbitrary parameter settings.
AB - In the first runtime analysis of an estimation-of-distribution algorithm (EDA) on the multimodal jump function class, Hasenöhrl and Sutton (GECCO 2018) proved that the runtime of the compact genetic algorithm with suitable parameter choice on jump functions with high probability is at most polynomial (in the dimension) if the jump size is at most logarithmic (in the dimension), and is at most exponential in the jump size if the jump size is super-logarithmic. The exponential runtime guarantee was achieved with a hypothetical population size that is also exponential in the jump size. Consequently, this setting cannot lead to a better runtime. In this work, we show that any choice of the hypothetical population size leads to a runtime that, with high probability, is at least exponential in the jump size. This result might be the first nontrivial exponential lower bound for EDAs that holds for arbitrary parameter settings.
KW - Evolutionary algorithms
KW - Runtime analysis
U2 - 10.1145/3299904.3340304
DO - 10.1145/3299904.3340304
M3 - Conference contribution
AN - SCOPUS:85076443850
T3 - FOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
SP - 25
EP - 33
BT - FOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
PB - Association for Computing Machinery, Inc
T2 - 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019
Y2 - 27 August 2019 through 29 August 2019
ER -