Pseudo-Boolean monotone functions are unimodal functions which are trivial to optimize for some hillclimbers, but are challenging for a surprising number of evolutionary algorithms (EAs). A general trend is that EAs are efficient if parameters like the mutation rate are set conservatively, but may need exponential time otherwise. In particular, it was known that the @math -EA and the @math -EA can optimize every monotone function in pseudolinear time if the mutation rate is @math for some @math . The second part of the statement was also known for the @math -EA. In this paper we show that the first statement does not apply to the @math -EA. More precisely, we prove that for every constant @math there is a constant integer @math such that the @math -EA with mutation rate @math and population size @math needs superpolynomial time to optimize some monotone functions. Thus, increasing the population size by just a constant has devastating effects on the performance. This is in stark contrast to many other benchmark functions on which increasing the population size either increases the performance significantly, or affects performance mildly. The reason why larger populations are harmful lies in the fact that larger populations may temporarily decrease selective pressure on parts of the population. This allows unfavorable mutations to accumulate in single individuals and their descendants. If the population moves sufficiently fast through the search space, such unfavorable descendants can become ancestors of future generations, and the bad mutations are preserved. Remarkably, this effect only occurs if the population renews itself sufficiently fast, which can only happen far away from the optimum. This is counter-intuitive since usually optimization gets harder as we approach the optimum.
Moreover, Lengler and Schaller pointed out an interesting connection between functions and a dynamic optimization problem in @cite_19 , which is arguably more natural. In that paper, the algorithm should optimize a linear function with positive weights, but the weights of the objective function are re-drawn each round (independently and identically distributed). This setting is similar to monotone functions, since a one-bit is always preferable over a zero-bit, and the all-one string is always the global optimum. However, the weight of each bit changes from round to round, which somewhat resembles that the function switches between different hot topics as the algorithm progresses. @cite_19 the was studied, and the behavior in the dynamic setting is very similar to the behavior on functions. It remains open whether the effects observed in our paper carry over to this dynamic setting.
@cite_19
2914741526
We study the well-known black-box optimisation algorithm (1+1)-EA on a novel type of noise model. In our noise model, the fitness function is linear with positive weights, but the absolute values of the weights may fluctuate in each round. Thus in every state, the fitness function indicates that one-bits are preferred over zero-bits. In particular, hillclimbing heuristics should be able to find the optimum fast. We show that the (1+1)-EA indeed finds the optimum in time @math if the mutation parameter is @math for a constant @math However, we also show that for @math the (1+1)-EA needs superpolynomial time to find the optimum. Thus the choice of mutation parameter is critical even for optimisation tasks in which there is a clear path to the the optimum. A similar threshold phenomenon has recently been shown for noise-free monotone fitness functions.