Drift Analysis and Evolutionary Algorithms Revisited

DOI10.1017/S0963548318000275zbMath1484.68324arXiv1608.03226WikidataQ129651807 ScholiaQ129651807MaRDI QIDQ3177365

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

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

Related Items (15)

Tail bounds on hitting times of randomized search heuristics using variable drift analysis ⋮ Does comma selection help to cope with local optima? ⋮ Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions ⋮ Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial ⋮ Self-adjusting population sizes for the (1,\( \lambda )\)-EA on monotone functions ⋮ Two-dimensional drift analysis: optimizing two functions simultaneously can be hard ⋮ Choosing the right algorithm with hints from complexity theory ⋮ Do additional target points speed up evolutionary algorithms? ⋮ Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model ⋮ Runtime analysis of the \((\mu + 1)\)-EA on the dynamic BinVal function ⋮ Optimal parameter choices via precise black-box analysis ⋮ Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions ⋮ 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

Cites Work

• Unnamed Item
• Concentration of first hitting times under additive drift
• Non-existence of linear universal drift functions
• 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
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.
• Adaptive drift analysis
• Multiplicative drift analysis
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• On the Brittleness of Evolutionary Algorithms
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: Drift Analysis and Evolutionary Algorithms Revisited