On the runtime analysis of the simple genetic algorithm

DOI10.1016/J.TCS.2013.06.015MaRDI QIDQ2250994zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Pietro S. Oliveto, Carsten Witt

Publication date 10 July 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.06.015

zbMATH Keywords

crossoverruntime analysissimple genetic algorithm

Mathematics Subject Classification ID

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

Recommendations

• Improved time complexity analysis of the simple genetic algorithm
• The effect of multiple optima on the simple GA run-time complexity
• Runtime analysis of evolutionary algorithms via symmetry arguments
• scientific article; zbMATH DE number 6019547
• A tight runtime analysis for the \((\mu + \lambda)\) EA

Cites work

• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Black-box search by unbiased variation
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• On the utility of the population size for inversely fitness proportional mutation rates
• Real royal road functions -- where crossover provably is essential
• Simplified drift analysis for proving lower bounds in evolutionary computation

Cited in

(22)

• Finite-time performance analysis for genetic algorithms
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• Tight bounds on the expected runtime of a standard steady state genetic algorithm
• On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
• Runtime analysis of evolutionary algorithms via symmetry arguments
• The runtime of the compact genetic algorithm on jump functions
• Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Towards a runtime comparison of natural and artificial evolution
• Population size versus runtime of a simple evolutionary algorithm
• Analysis of noisy evolutionary optimization when sampling fails
• The complex parameter landscape of the compact genetic algorithm
• Concentration of first hitting times under additive drift
• scientific article; zbMATH DE number 5159419 (Why is no real title available?)
• Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances
• Statistical and computational tradeoff in genetic algorithm-based estimation
• Hitting times of local and global optima in genetic algorithms with very high selection pressure
• An exponential lower bound for the runtime of the compact genetic algorithm on jump functions
• Runtime analysis of mutation-based geometric semantic genetic programming on Boolean functions
• OneMax is not the easiest function for fitness improvements
• The effect of multiple optima on the simple GA run-time complexity
• Improved time complexity analysis of the simple genetic algorithm

This page was built for publication: On the runtime analysis of the simple genetic algorithm

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