Non-existence of linear universal drift functions

DOI10.1016/J.TCS.2012.01.048MaRDI QIDQ428906zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Daniel Johannsen, Carola Winzen

Publication date 25 June 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

evolutionary algorithmsruntime analysisbio-inspired computation

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: Drift analysis has become a powerful tool to prove bounds on the runtime of randomized search heuristics. It allows, for example, fairly simple proofs for the classical problem how the (1+1) Evolutionary Algorithm (EA) optimizes an arbitrary pseudo-Boolean linear function. The key idea of drift analysis is to measure the progress via another pseudo-Boolean function (called drift function) and use deeper results from probability theory to derive from this a good bound for the runtime of the EA. Surprisingly, all these results manage to use the same drift function for all linear objective functions. In this work, we show that such universal drift functions only exist if the mutation probability is close to the standard value of $1/n$.

Recommendations

• Adaptive drift analysis
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Multiplicative drift analysis
• Drift analysis and evolutionary algorithms revisited
• Tight bounds on the optimization time of a randomized search heuristic on linear functions

Cites work

• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Drift analysis and average time complexity of evolutionary algorithms
• On the analysis of the \((1+1)\) evolutionary algorithm
• On the impact of the mutation-selection balance on the runtime of evolutionary algorithms
• Optimizing linear functions with randomized search heuristics -- the robustness of mutation
• Simplified drift analysis for proving lower bounds in evolutionary computation

Cited in

(8)

• Simplified drift analysis for proving lower bounds in evolutionary computation
• Runtime analysis for permutation-based evolutionary algorithms
• Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms
• Drift analysis and evolutionary algorithms revisited
• Adaptive drift analysis
• Multiplicative drift analysis
• Optimizing linear functions with randomized search heuristics -- the robustness of mutation
• Linear multi-objective drift analysis

This page was built for publication: Non-existence of linear universal drift functions

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