Hardest Monotone Functions for Evolutionary Algorithms

Abstract

The hardness of optimizing monotone functions using the (1 + 1)-EA has been an open problem for a long time. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen proved a runtime bound of O(n(³/²)). In 2019, Lengler, Martinsson and Steger improved this upper bound to O(n log² n) leveraging an entropy compression argument. We continue this line of research by analyzing monotone functions that may vary at each step, 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, SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the (1 + 1)-EA optimizes SDBV in Theta(n(³/²)) generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the PO-EA model. Our simulations demonstrate matching runtimes for both static and self-adjusting (1,lambda) and (1 +lambda)-EA. We additionally demonstrate, devising an example of fixed dimension, that drift minimization does not equal maximal runtime.