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

DOI10.1007/S00453-015-0103-XMaRDI QIDQ306486zbMATH OpenOpenAlexFDO

Authors Duc-Cuong Dang, Per Kristian Lehre

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

evolutionary algorithmspartial evaluationdrift analysisfitness-levelsnon-elitismruntime

Mathematics Subject Classification ID

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

Recommendations

• Dynamic optimization of large-population systems with partial information
• Distributed optimization with information-constrained population dynamics
• Information-theoretic bounded rationality and -optimality
• Complexity of non–adaptive optimization algorithms for a class of diffusions
• Selection of the best population: An information theoretic approach
• Functionals using bounded information and the dynamics of algorithms

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 2013543 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• scientific article; zbMATH DE number 3195515 (Why is no real title available?)
• Analyzing evolutionary algorithms. The computer science perspective.
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Concentration of Measure for the Analysis of Randomized Algorithms
• Drift analysis and average time complexity of evolutionary algorithms
• Evolutionary computation in practice
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Multiplicative drift analysis
• Probability and Computing
• Robustness of populations in stochastic environments
• Simple max-min ant systems and the optimization of linear pseudo-Boolean functions
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm

Cited in

(16)

• Exponential upper bounds for the runtime of randomized search heuristics
• Does comma selection help to cope with local optima?
• 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
• On non-elitist evolutionary algorithms optimizing fitness functions with a plateau
• Runtime analysis of competitive co-evolutionary algorithms for maximin optimisation of a bilinear function
• Choosing the right algorithm with hints from complexity theory
• Hitting times of local and global optima in genetic algorithms with very high selection pressure
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• Populations can be essential in tracking dynamic optima
• Runtime analysis for self-adaptive mutation rates
• The voting algorithm is robust to various noise models
• A tight runtime analysis for the \((\mu + \lambda)\) EA
• Multiplicative up-drift
• Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial

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

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