Abstract: The expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions Plateaur on the search space of binary strings of length n is considered asymptotically with unbounded n. The functions of this family have a plateau of second-best fitness in a Hamming ball of a constant radius r around a unique global optimum, while below the plateau the fitness equals the number of one-bits. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for non-elitist EAs with tournament selection, (μ, λ)-selection and proportionate selection. We assume that these EAs are based on an unbiased mutation, in particular, the bitwise mutation. In the case of proportionate selection, the mutation probability is of order 1/n2. On the other hand, we show that the EA with fitness proportionate selection is inefficient even to search for approximate solutions if the bitwise mutation is used with the mutation probability greater than ln(2)/n.

Cite: Eremeev A.
On runtime of non-elitist evolutionary algorithms optimizing fitness functions with a plateau
Yugoslav Journal of Operations Research. 2025. DOI: 10.2298/yjor250715042e OpenAlex

Dates:

Submitted:	Jul 10, 2025
Accepted:	Nov 15, 2025

Identifiers:

OpenAlex:

W4416981695

Citing: Пока нет цитирований

Altmetrics: