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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 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 two easy combinatorial problems: finding the 2-coloring of a class of bipartite graphs, and constructing satisfying assignments for a class of satisfiable 2-CNF Boolean formulas. We prove that it is inefficient on both 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 inuence 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 dificulty leaving. Finally, we show how to modify the (1+1) EA slightly in order to obtain a polynomial-time performance guarantee on both problems.

Original languageEnglish (US)
Title of host publicationGECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Pages1431-1438
Number of pages8
ISBN (Print)9781450326629
DOIs
StatePublished - Jan 1 2014
Event16th Genetic and Evolutionary Computation Conference, GECCO 2014 - Vancouver, BC, Canada
Duration: Jul 12 2014Jul 16 2014

Other

Other16th Genetic and Evolutionary Computation Conference, GECCO 2014
CountryCanada
CityVancouver, BC
Period7/12/147/16/14

Keywords

  • 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