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)

Review text

The author studies the (1+1)-evolutionary algorithm (that is, an evolutionary algorithm with population size 1 and mutation on this 1 element) using three classes of problems: finding 2-colourings of a class of bipartite graphs, solving satisfiable 2-CNF formulae, and solving satisfiable propositional Horn formulae. It is proved that the algorithm needs superpolynomial cost with high probability for all these three problems although the problems as such are polynomial. The author is interested in understanding the structural properties of the problems that make the problems hard for evolutionary algorithms. In particular, he investigates when the algorithm becomes trapped in meta-stable states from which it has difficulty to escape. This is due to the so-called spin-flip symmetry, an invariant of the objective function under permutations on the alphabet. For the graph colouring the author gives illustrations which exemplify how the problems occur. The second problem class is isomorphic to the first, the last is different but shares properties with the first two. In order to come up with a better algorithm, the author modifies the algorithm to take into account domain-specific information and shows that by a minor modification the time complexity can be reduced from superpolynomial to polynomial.

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)