Superpolynomial lower bounds for the (1+1) EA on some easy combinatorial problems

DOI10.1007/S00453-015-0027-5MaRDI QIDQ306491zbMATH OpenOpenAlexFDO

Authors Andrew M. Sutton

Publication date 31 August 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-0027-5

zbMATH Keywords

(1 + 1) EAevolutionary algorithmlower boundsruntime analysistime complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• On the analysis of the \((1+1)\) evolutionary algorithm
• Evolutionary computation in combinatorial optimization
• scientific article; zbMATH DE number 1703859
• On the analysis of a simple evolutionary algorithm on quadratic pseudo-Boolean functions
• Time complexity analysis of RLS and (1+1) EA for the edge coloring problem

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A Random Recolouring Method for Graphs and Hypergraphs
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Computing minimum cuts by randomized search heuristics
• Generalization of a Probability Limit Theorem of Cramer
• scientific article; zbMATH DE number 1962832 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• Logical foundations of proof complexity
• Multiplicative drift analysis
• Probability with Martingales
• Simplified drift analysis for proving lower bounds in evolutionary computation
• The complexity of satisfiability problems
• The one-dimensional Ising model: mutation versus recombination
• Tight bounds on the optimization time of a randomized search heuristic on linear functions
• Upper and lower bounds for randomized search heuristics in black-box optimization

Cited in

(3)

• Symmetry breaking for voting mechanisms
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Time complexity analysis of RLS and (1+1) EA for the edge coloring problem

This page was built for publication: Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems

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