On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions

Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1) Evolutionary Algorithm ((1+1) EA) and its multistart variants are studied. Several results on the expected runtime of the (1+1) EA on linear or unimodal functions have already been presented by other authors. This paper is focused on quadratic pseudo-boolean functions, i.e., polynomials of degree 2, a class of functions containing NP-hard optimization problems. Subclasses of the class of all quadratic functions are identified where the (1+1) EA is efficient, for other subclasses the (1+1) EA has exponential expected runtime, but a large enough success probability within polynomial time such that a multistart variant of the (1+1) EA is efficient. Finally, a particular quadratic function is identified where the EA and its multistart variants fail in polynomial time with overwhelming probability.