Simplified drift analysis for proving lower bounds in evolutionary computation

DOI10.1007/s00453-010-9387-zzbMath1211.68521WikidataQ57200627 ScholiaQ57200627MaRDI QIDQ633834

Publication date: 30 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2003/26154

zbMATH Keywords

computational complexity; evolutionary algorithms; drift analysis; runtime analysis; randomized search heuristics

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90C59: Approximation methods and heuristics in mathematical programming

60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W20: Randomized algorithms

Related Items

Robustness of populations in stochastic environments, Concentration of first hitting times under additive drift, Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems, Non-existence of linear universal drift functions, Runtime analysis of ant colony optimization on dynamic shortest path problems, The time complexity analysis of a class of gene expression programming, Free lunches on the discrete Lipschitz class, Hybridizing evolutionary algorithms with variable-depth search to overcome local optima, Simplified drift analysis for proving lower bounds in evolutionary computation, Improved time complexity analysis of the simple genetic algorithm, Analysis of runtime of optimization algorithms for noisy functions over discrete codomains, Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise, Drift analysis of ant colony optimization of stochastic linear pseudo-Boolean functions, Adaptive drift analysis, Multiplicative drift analysis, Runtime analysis of evolutionary algorithms via symmetry arguments, On the runtime analysis of the simple genetic algorithm, The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm, Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming, First-hitting times under drift, \textsc{OneMax} in black-box models with several restrictions, Populations can be essential in tracking dynamic optima, Towards a runtime comparison of natural and artificial evolution, On the benefits and risks of using fitness sharing for multimodal optimisation, Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift, Drift Analysis and Evolutionary Algorithms Revisited

Cites Work