Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns

DOI10.1007/s00453-010-9391-3zbMath1211.68505MaRDI QIDQ633835

Hervé Fournier, Olivier Teytaud

Publication date: 30 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9391-3

zbMATH Keywords

VC-dimension; convergence speed; sphere function; sign patterns; evolution algorithms

Mathematics Subject Classification ID

68W40: Analysis of algorithms

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

68W20: Randomized algorithms

Related Items

Ranking-based black-box complexity, Random drift particle swarm optimization algorithm: convergence analysis and parameter selection, Black-box search by unbiased variation, Optimal parameter choices via precise black-box analysis, Scaling-invariant functions versus positively homogeneous functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Evolution strategies. A comprehensive introduction
• Convergence results for the (1,\(\lambda\))-SA-ES using the theory of \(\varphi\)-irreducible Markov chains
• Algorithmic analysis of a basic evolutionary algorithm for continuous optimization
• Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
• On the density of families of sets
• On the number of zero-patterns of a sequence of polynomials
• `` Direct Search Solution of Numerical and Statistical Problems
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Foundations of Genetic Algorithms