On the runtime analysis of the simple genetic algorithm

DOI10.1016/j.tcs.2013.06.015zbMath1342.68310OpenAlexW2087605480WikidataQ57200590 ScholiaQ57200590MaRDI QIDQ2250994

Carsten Witt, Pietro S. Oliveto

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

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

Related Items

Towards a runtime comparison of natural and artificial evolution ⋮ Concentration of first hitting times under additive drift ⋮ Tight bounds on the expected runtime of a standard steady state genetic algorithm ⋮ Analysis of noisy evolutionary optimization when sampling fails ⋮ Improved time complexity analysis of the simple genetic algorithm ⋮ OneMax is not the easiest function for fitness improvements ⋮ On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms ⋮ Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances ⋮ How to escape local optima in black box optimisation: when non-elitism outperforms elitism ⋮ Statistical and computational tradeoff in genetic algorithm-based estimation ⋮ Hitting times of local and global optima in genetic algorithms with very high selection pressure ⋮ Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem

Cites Work

• Unnamed Item
• Unnamed Item
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Simplified drift analysis for proving lower bounds in evolutionary computation
• Black-box search by unbiased variation
• Real royal road functions -- where crossover provably is essential
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• On the utility of the population size for inversely fitness proportional mutation rates