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

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Random Recolouring Method for Graphs and Hypergraphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• 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
• 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)

• 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
• 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)