Non-existence of linear universal drift functions

DOI10.1016/J.TCS.2012.01.048zbMATH Open1247.68251arXiv1011.3466OpenAlexW1601534271MaRDI QIDQ428906FDOQ428906

Carola Winzen, Daniel Johannsen, Benjamin Doerr

Publication date: 25 June 2012

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

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Drift analysis and average time complexity of evolutionary algorithms
• Simplified drift analysis for proving lower bounds in evolutionary computation
• On the impact of the mutation-selection balance on the runtime of evolutionary algorithms
• On the analysis of the \((1+1)\) evolutionary algorithm
• Optimizing linear functions with randomized search heuristics -- the robustness of mutation

Cited In (4)

• Drift Analysis and Evolutionary Algorithms Revisited
• Runtime analysis for permutation-based evolutionary algorithms
• Adaptive drift analysis
• Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms

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)