Abstract: Theoretical evidence suggests that non-elitist evolutionary algorithms (EAs) with non-linear selection mechanisms can efficiently overcome broad classes of local optima where elitist EAs fail. However, the analysis assumes a weak selective pressure and mutation rates carefully chosen close to the error threshold, above which they cease to be efficient. On problems easier for hill-climbing, the populations may slow down these algorithms, leading to worse runtime compared with variants of the elitist (1+1) EA. Here, we show that a non-elitist EA with power-law ranking selection leads to fast runtime on easy benchmark problems, while maintaining the capability of escaping certain local optima where the elitist EAs spend exponential time in the expectation. We derive a variant of the level-based theorem which accounts for power-law distributions. For classical theoretical benchmarks, the expected runtime is stated with small leading constants. For complex, multi-modal fitness landscapes, we provide sufficient conditions for polynomial optimisation, formulated in terms of deceptive regions sparsity and fitness valleys density. We derive the error threshold and show extreme tolerance to high mutation rates. Experiments on NK-Landscape functions, generated according to the Kauffman's model, show that the algorithm outperforms the (1+1) EA and the univariate marginal distribution algorithm (UMDA).

Cite: Dang D.-C. , Eremeev A. , Lehre P.K. , Qin X.
Fast non-elitist evolutionary algorithms with power-law ranking selection
In compilation GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference, Boston, USA, 09-13 July, 2022. 2022. – C.1372-1380. – ISBN 9781450392372. DOI: 10.1145/3512290.3528873 WOS Scopus OpenAlex

Dates:

Published online:

Jul 8, 2022

Identifiers:

Web of science:	WOS:000847380200155
Scopus:	2-s2.0-85134709684
OpenAlex:	W4288044853

Citing:

DB	Citing
Scopus	11
Web of science	13
OpenAlex	13

Altmetrics: