On runtime of non-elitist evolutionary algorithms optimizing fitness functions with a plateau

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.