Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems
type: Item
instance of: scholarly article
title: Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems
zbMATH Open document ID: 1360.68791
author: Andrew M. Sutton
published in: Algorithmica
publication date: 2016-08-31T00:00:00Z
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.
reviewed by: Manfred Kerber
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 6621054
zbMATH Keywords: runtime analysis
zbMATH Keywords: time complexity
zbMATH Keywords: lower bounds
zbMATH Keywords: (1 + 1) EA
zbMATH Keywords: evolutionary algorithm
MaRDI profile type: Publication
full work available at URL: s00453-015-0027-5
OpenAlex ID: W2468335684
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Q5306039
cites work: Q5306365
cites work: A Random Recolouring Method for Graphs and Hypergraphs
cites work: Multiplicative drift analysis
cites work: Upper and lower bounds for randomized search heuristics in black-box optimization
cites work: Generalization of a Probability Limit Theorem of Cramer
cites work: Computing minimum cuts by randomized search heuristics
cites work: The one-dimensional Ising model: mutation versus recombination
cites work: Q4418669
cites work: Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
cites work: Simplified drift analysis for proving lower bounds in evolutionary computation
cites work: The complexity of satisfiability problems
cites work: Probability with Martingales
cites work: Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
DOI: 10.1007/S00453-015-0027-5
description: scientific article; zbMATH DE number 6621054