Drift analysis and evolutionary algorithms revisited

DOI10.1017/S0963548318000275MaRDI QIDQ3177365zbMATH OpenWikidataFDO

Authors Johannes Lengler, Angelika Steger

Publication date 24 July 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a boolean function $f:{0,1}^{n}omathbbR$. The algorithm starts with a random search point $xiin{0,1}^n$, and in each round it flips each bit of $xi$ with probability $c/n$ independently at random, where $c>0$ is a fixed constant. The thus created offspring $x{i}^{\prime }$ replaces $xi$ if and only if $f(x{i}^{\prime })gef(xi)$. The analysis of the runtime of this simple algorithm on monotone and on linear functions turned out to be highly non-trivial. In this paper we review known results and provide new and self-contained proofs of partly stronger results.

Recommendations

• Multiplicative drift analysis
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Non-existence of linear universal drift functions
• Adaptive drift analysis
• On the analysis of the \((1+1)\) evolutionary algorithm

Cites work

• A study of drift analysis for estimating computation time of evolutionary algorithms
• Adaptive drift analysis
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Concentration of first hitting times under additive drift
• Drift analysis and average time complexity of evolutionary algorithms
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• scientific article; zbMATH DE number 976350 (Why is no real title available?)
• Multiplicative drift analysis
• Non-existence of linear universal drift functions
• On the Brittleness of Evolutionary Algorithms
• Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.
• Simplified drift analysis for proving lower bounds in evolutionary computation
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• Tight bounds on the optimization time of a randomized search heuristic on linear functions

Cited in

(32)

• Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms
• Linear multi-objective drift analysis
• On the analysis of a simple evolutionary algorithm on quadratic pseudo-Boolean functions
• Multiplicative drift analysis
• Optimal parameter choices via precise black-box analysis
• Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions
• Does comma selection help to cope with local optima?
• Runtime analysis of the ( + 1)-EA on the dynamic BinVal function
• The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• First-hitting times under drift
• Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial
• Do additional target points speed up evolutionary algorithms?
• Non-existence of linear universal drift functions
• scientific article; zbMATH DE number 2013513 (Why is no real title available?)
• Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions
• When does hillclimbing fail on monotone functions: an entropy compression argument
• Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Drift analysis and average time complexity of evolutionary algorithms
• Self-adjusting population sizes for the (1, )-EA on monotone functions
• Two-dimensional drift analysis: optimizing two functions simultaneously can be hard
• Choosing the right algorithm with hints from complexity theory
• Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
• Simplified drift analysis for proving lower bounds in evolutionary computation
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Runtime analysis of quality diversity algorithms
• Hardest monotone functions for evolutionary algorithms
• Plus strategies are exponentially slower for planted optima of random height
• Many-objective problems where crossover is provably essential
• Evolutionary anytime algorithms
• Dispersion on the complete graph (extended abstract)

This page was built for publication: Drift analysis and evolutionary algorithms revisited

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