Runtime analysis of non-elitist populations: from classical optimisation to partial information

DOI10.1007/s00453-015-0103-xzbMath1348.68225OpenAlexW2197473496MaRDI QIDQ306486

Per Kristian Lehre, Duc-Cuong Dang

Publication date: 31 August 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://eprints.nottingham.ac.uk/31142/

zbMATH Keywords

partial evaluationevolutionary algorithmsdrift analysisfitness-levelsnon-elitismruntime

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (15)

Populations can be essential in tracking dynamic optima ⋮ Does comma selection help to cope with local optima? ⋮ Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial ⋮ Runtime analysis for self-adaptive mutation rates ⋮ A tight runtime analysis for the \((\mu + \lambda)\) EA ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Choosing the right algorithm with hints from complexity theory ⋮ Lower bounds from fitness levels made easy ⋮ More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments ⋮ Runtime analysis for permutation-based evolutionary algorithms ⋮ The voting algorithm is robust to various noise models ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ Multiplicative up-drift ⋮ How to escape local optima in black box optimisation: when non-elitism outperforms elitism ⋮ Hitting times of local and global optima in genetic algorithms with very high selection pressure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Robustness of populations in stochastic environments
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• Multiplicative drift analysis
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Evolutionary computation in practice
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Simple max-min ant systems and the optimization of linear pseudo-boolean functions
• Probability and Computing
• Concentration of Measure for the Analysis of Randomized Algorithms
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: Runtime analysis of non-elitist populations: from classical optimisation to partial information