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 parametrizing 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 ∈ R 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.