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

DOI10.1007/S00453-015-0027-5zbMATH Open1360.68791OpenAlexW2468335684MaRDI QIDQ306491FDOQ306491

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

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

zbMATH Keywords

evolutionary algorithmlower boundstime complexity(1 + 1) EAruntime analysis

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Symmetry breaking for voting mechanisms

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)