Monotonic functions in EC: Anything but monotone!

To understand how evolutionary algorithms optimize the simple class of monotonic functions, Jansen (FOGA 2007) introduced the partially-ordered evolutionary algorithm (PO-EA) model and analyzed its runtime. The PO-EA is a pessimistic model of the true optimization process, hence performance guarantees for it immediately take over to the true optimization process. Based on the observation that Jansen's model leads to a process more pessimistic than what any monotonic function would, we extend his model by parameterizing the degree of pessimism. For all degrees of pessimism, and all mutation rates c/n, we give a precise runtime analysis of this process. For all degrees of pessimism lower than that of Jansen, we observe a Θ (n log n) runtime for the standard mutation probability of 1/n. However, we also observe a strange double-jump behavior in terms of the mutation probability. For all non-zero degrees of pessimism, there is a threshold c ε ℝ such that (i) for mutation rates c′/n with c′ < c we have a Θ (n log n) runtime, (ii) for the mutation rate c/n we have a runtime of Θ (n^3/2), and (iii) for mutation rates c″/n with c″ > c we have an exponential runtime. To overcome the complicated interplay of mutation and selection in the PO-EA, by define artificial algorithms which provably (via a coupling argument) have the same asymptotic runtime, but allow a much easier computation of the drift towards the optimum.