Hardest Monotone Functions for Evolutionary Algorithms

In this paper we revisit the question how hard it can be for the (1+1) Evolutionary Algorithm to optimize monotone pseudo-Boolean functions. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen first proved a runtime bound of O(n3/2). More recently, Lengler, Martinsson and Steger improved this upper bound to O(n log2 n) by an entropy compression argument. In this work, we analyze monotone functions that may adversarially vary at each step of the optimization, so-called dynamic monotone functions. We introduce the function Switching Dynamic BinVal (SDBV) and prove, using a combinatorial argument, that for the (1+1)-EA with any mutation rate p ∈ [0,1], SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the (1+1)-EA optimizes SDBV in Theta(n3/2) generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the poea model. Our simulations demonstrate matching runtimes for both the static and the self-adjusting (1,λ)-EA and (1+λ)-EA. Moreover, devising an example for fixed dimension, we illustrate that drift minimization does not equal maximal runtime beyond asymptotic analysis.