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

DOI10.1145/3299904.3340302zbMATH Open1433.68645arXiv1906.09047OpenAlexW2969868371MaRDI QIDQ5215475FDOQ5215475

Carsten Witt, Hsien-Kuei Hwang

Publication date: 11 February 2020

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

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)$.

Full work available at URL: https://arxiv.org/abs/1906.09047

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)

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

   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 + (λ, λ)) GA on leadingones 👍 👎
• Title not available (Why is that?) 👍 👎
• 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+\lambda)\) EA on OneMax through asymptotically tight drift analysis 👍 👎
• (1+1) EA on Generalized Dynamic OneMax 👍 👎

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)