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

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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
JournalAlgorithmica
Volume75
Issue number3
DOIs
StatePublished - Jul 1 2016

Keywords

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

Fingerprint 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