TY - GEN
T1 - A tight runtime analysis for the (1 + (λ, λ)) GA on leading ones
AU - Antipov, Denis
AU - Doerr, Benjamin
AU - Karavaev, Vitalii
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s).
PY - 2019/8/27
Y1 - 2019/8/27
N2 - We conduct a rigorous runtime analysis of the (1+(λ, λ)) evolutionary algorithm with standard parameter settings, that is, a mutation rate of p = λ/n and a crossover bias of c = 1/λ when optimizing the classic LeadingOnes benchmark function. We show that, for all λ ∈ [1..n/2], the runtime is Θ(n2/λ) iterations and Θ(n2) fitness evaluations. This is, asymptotically, the same number of iterations as for the (1 + λ) EA and the same number of fitness evaluations as for the (1 + λ) EA for any value of λ = O(n). We also extend our results to parameter control techniques and prove that for any dynamic choice of λ the bound of Θ(n2) fitness evaluations still holds.
AB - We conduct a rigorous runtime analysis of the (1+(λ, λ)) evolutionary algorithm with standard parameter settings, that is, a mutation rate of p = λ/n and a crossover bias of c = 1/λ when optimizing the classic LeadingOnes benchmark function. We show that, for all λ ∈ [1..n/2], the runtime is Θ(n2/λ) iterations and Θ(n2) fitness evaluations. This is, asymptotically, the same number of iterations as for the (1 + λ) EA and the same number of fitness evaluations as for the (1 + λ) EA for any value of λ = O(n). We also extend our results to parameter control techniques and prove that for any dynamic choice of λ the bound of Θ(n2) fitness evaluations still holds.
KW - Crossover
KW - Runtime Analysis
KW - Theory
U2 - 10.1145/3299904.3340317
DO - 10.1145/3299904.3340317
M3 - Conference contribution
AN - SCOPUS:85071398971
T3 - FOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
SP - 169
EP - 182
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 -