Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools

DOI10.1145/3299904.3340302MaRDI QIDQ5215475zbMATH OpenOpenAlexFDO

Authors Hsien-Kuei Hwang, Carsten Witt

Publication date 11 February 2020

Published in Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.09047, https://backend.orbit.dtu.dk/ws/files/198799577/p1_hwang.pdf

zbMATH Keywords

asymptotic methodsdrift analysisrandomized search heuristics(1+1) EA

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50)

Abstract: The expected running time of the classical (1+1) EA on the OneMax benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of $O((logn)/n)$. The same approach proposed there also leads to a full asymptotic expansion with errors of the form $O(n^{-K}logn)$ for any $K>0$. This precise result is obtained by matched asymptotics with rigorous error analysis (or by solving asymptotically the underlying recurrences via inductive approximation arguments), ideas radically different from well-established techniques for the running time analysis of evolutionary computation such as drift analysis. This paper revisits drift analysis for the (1+1) EA on OneMax and obtains that the expected running time $E(T)$, starting from $lceiln/2ceil$ one-bits, is determined by the sum of inverse drifts up to logarithmic error terms, more precisely ${\displaystyle }$sum_{k=1}^{lfloor n/2 floor}frac{1}{Delta(k)} - c_1log n le E(T) le sum_{k=1}^{lfloor n/2 floor}frac{1}{Delta(k)} - c_2log n,${\displaystyle }$ where $Delta(k)$ is the drift (expected increase of the number of one-bits from the state of $n-k$ ones) and $c_1,c_2>0$ are explicitly computed constants. This improves the previous asymptotic error known for the sum of inverse drifts from $ildeO(n^{2/3})$ to a logarithmic error and gives for the first time a non-asymptotic error bound. Using standard asymptotic techniques, the difference between $E(T)$ and the sum of inverse drifts is found to be $(e/2)logn+O(1)$.

Recommendations

• A tight runtime analysis for the \((\mu + \lambda)\) EA
• Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise
• Runtime analysis of the (1+1) EA on computing unique input output sequences
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• A tight runtime analysis for the \((1+(\lambda,\lambda))\) GA on LeadingOnes
• scientific article; zbMATH DE number 2013543
• Exponential upper bounds for the runtime of randomized search heuristics
• Running time analysis of the (1+1)-EA for robust linear optimization
• Optimal mutation rates for the (1+) EA on OneMax through asymptotically tight drift analysis
• (1+1) EA on Generalized Dynamic OneMax

Cited in

(5)

• Runtime analysis for self-adaptive mutation rates
• (1+1) EA on Generalized Dynamic OneMax
• Lower bounds from fitness levels made easy
• Runtime analysis of the (1+1) EA on computing unique input output sequences
• How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys

This page was built for publication: Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215475)