TY - GEN
T1 - Exponential upper bounds for the runtime of randomized search heuristics
AU - Doerr, Benjamin
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also in evolutionary computation and we prove several such results. We show that any of the algorithms randomized local search, Metropolis algorithm, simulated annealing, and $$(1+1)$$ evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function under a large set of noise assumptions in a runtime that is at most exponential in the problem dimension n. This drastically extends a previous such result, limited to the $$(1+1)$$ EA, the LeadingOnes function, and one-bit or bit-wise prior noise with noise probability at most 1/2, and at the same time simplifies its proof. With the same general argument, among others, we also derive a sub-exponential upper bound for the runtime of the $$(1,\lambda )$$ evolutionary algorithm on the OneMax problem when the offspring population size $$\lambda $$ is logarithmic, but below the efficiency threshold.
AB - We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also in evolutionary computation and we prove several such results. We show that any of the algorithms randomized local search, Metropolis algorithm, simulated annealing, and $$(1+1)$$ evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function under a large set of noise assumptions in a runtime that is at most exponential in the problem dimension n. This drastically extends a previous such result, limited to the $$(1+1)$$ EA, the LeadingOnes function, and one-bit or bit-wise prior noise with noise probability at most 1/2, and at the same time simplifies its proof. With the same general argument, among others, we also derive a sub-exponential upper bound for the runtime of the $$(1,\lambda )$$ evolutionary algorithm on the OneMax problem when the offspring population size $$\lambda $$ is logarithmic, but below the efficiency threshold.
KW - Noisy optimization
KW - Runtime analysis
KW - Theory
U2 - 10.1007/978-3-030-58115-2_43
DO - 10.1007/978-3-030-58115-2_43
M3 - Conference contribution
AN - SCOPUS:85091158017
SN - 9783030581145
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 619
EP - 633
BT - Parallel Problem Solving from Nature – PPSN XVI - 16th International Conference, PPSN 2020, Proceedings
A2 - Bäck, Thomas
A2 - Preuss, Mike
A2 - Deutz, André
A2 - Emmerich, Michael
A2 - Wang, Hao
A2 - Doerr, Carola
A2 - Trautmann, Heike
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th International Conference on Parallel Problem Solving from Nature, PPSN 2020
Y2 - 5 September 2020 through 9 September 2020
ER -