Simplified drift analysis for proving lower bounds in evolutionary computation

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

Pietro S. Oliveto, Carsten Witt

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 complexityevolutionary algorithmsdrift analysisruntime analysisrandomized search heuristics

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (35)

\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 ⋮ Tail bounds on hitting times of randomized search heuristics using variable drift analysis ⋮ 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 ⋮ Drift Analysis and Evolutionary Algorithms Revisited ⋮ Does comma selection help to cope with local optima? ⋮ Analysis of noisy evolutionary optimization when sampling fails ⋮ Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial ⋮ The complex parameter landscape of the compact genetic algorithm ⋮ Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift ⋮ On the impact of the performance metric on efficient algorithm configuration ⋮ On the benefits and risks of using fitness sharing for multimodal optimisation ⋮ Improved time complexity analysis of the simple genetic algorithm ⋮ Analysis of runtime of optimization algorithms for noisy functions over discrete codomains ⋮ When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not ⋮ Adaptive drift analysis ⋮ Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter ⋮ Multiplicative drift analysis ⋮ Non-existence of linear universal drift functions ⋮ 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 ⋮ 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 ⋮ Runtime analysis of evolutionary algorithms via symmetry arguments ⋮ Runtime analysis of ant colony optimization on dynamic shortest path problems ⋮ The runtime of the compact genetic algorithm on jump functions ⋮ The time complexity analysis of a class of gene expression programming ⋮ 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

Cites Work

• Simplified drift analysis for proving lower bounds in evolutionary computation
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Upper and lower bounds for randomized search heuristics in black-box optimization
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• The time complexity of maximum matching by simulated annealing
• Drift analysis and average time complexity of evolutionary algorithms
• Unnamed Item
• Unnamed Item

This page was built for publication: Simplified drift analysis for proving lower bounds in evolutionary computation