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

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.