Superpolynomial Lower Bounds for the (1 + 1) EA on Some Easy Combinatorial Problems

The (1 + 1) EA is a simple evolutionary algorithm that is known to be efficient on linear functions and on some combinatorial optimization problems. In this paper, we rigorously study its behavior on three easy combinatorial problems: finding the 2-coloring of a class of bipartite graphs, solving a class of satisfiable 2-CNF formulas, and solving a class of satisfiable propositional Horn formulas. We prove that it is inefficient on all three problems in the sense that the number of iterations the algorithm needs to minimize the cost functions is superpolynomial with high probability. Our motivation is to better understand the influence of problem instance structure on the runtime character of a simple evolutionary algorithm. We are interested in what kind of structural features give rise to so-called metastable states at which, with probability 1 - o(1) , the (1 + 1) EA becomes trapped and subsequently has difficulty leaving. Finally, we show how to modify the (1 + 1) EA slightly in order to obtain a polynomial-time performance guarantee on all three problems.