Monotonic functions in EC
Sylvain Colin, Benjamin Doerr, Gaspard Férey · 2014
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 an exponential runtime.