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

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)507-528
Number of pages22
Issue number3
StatePublished - Jul 1 2016

Bibliographical note

Funding Information:
The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under Grant Agreement No. 618091 (SAGE), and from the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under Grant No. FA9550-11-1-0088. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.

Publisher Copyright:
© 2015, Springer Science+Business Media New York.


  • (1 + 1) EA
  • Lower bounds
  • Runtime analysis


Dive into the research topics of 'Superpolynomial Lower Bounds for the (1 + 1) EA on Some Easy Combinatorial Problems'. Together they form a unique fingerprint.

Cite this