## 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 language | English (US) |
---|---|

Title of host publication | GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference |

Publisher | Association for Computing Machinery |

Pages | 1431-1438 |

Number of pages | 8 |

ISBN (Print) | 9781450326629 |

DOIs | |

State | Published - Jan 1 2014 |

Event | 16th Genetic and Evolutionary Computation Conference, GECCO 2014 - Vancouver, BC, Canada Duration: Jul 12 2014 → Jul 16 2014 |

### Other

Other | 16th Genetic and Evolutionary Computation Conference, GECCO 2014 |
---|---|

Country | Canada |

City | Vancouver, BC |

Period | 7/12/14 → 7/16/14 |

## Keywords

- Lower bounds
- Runtime analysis