Improved time complexity analysis of the simple genetic algorithm
From MaRDI portal
Publication:888423
DOI10.1016/j.tcs.2015.01.002zbMath1330.68120OpenAlexW2082931571WikidataQ57200573 ScholiaQ57200573MaRDI QIDQ888423
Pietro S. Oliveto, Carsten Witt
Publication date: 30 October 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.01.002
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (22)
Tight bounds on the expected runtime of a standard steady state genetic algorithm ⋮ Does comma selection help to cope with local optima? ⋮ Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems ⋮ Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints ⋮ Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Self-adjusting population sizes for the (1,\( \lambda )\)-EA on monotone functions ⋮ When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not ⋮ FSPL: a meta-learning approach for a filter and embedded feature selection pipeline ⋮ Two-dimensional drift analysis: optimizing two functions simultaneously can be hard ⋮ Choosing the right algorithm with hints from complexity theory ⋮ Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter ⋮ How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys ⋮ On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax ⋮ Runtime analysis of evolutionary algorithms via symmetry arguments ⋮ On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization ⋮ Multiplicative up-drift ⋮ Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs ⋮ How to escape local optima in black box optimisation: when non-elitism outperforms elitism ⋮ Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
Cites Work
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Analyzing evolutionary algorithms. The computer science perspective.
- Simplified drift analysis for proving lower bounds in evolutionary computation
- Black-box search by unbiased variation
- On the runtime analysis of the simple genetic algorithm
- Real royal road functions -- where crossover provably is essential
- Hitting-time and occupation-time bounds implied by drift analysis with applications
- Probability with Martingales
- Optimizing expected path lengths with ant colony optimization using fitness proportional update
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Improved time complexity analysis of the simple genetic algorithm
