The OneMax problem is a standard benchmark optimisation problem for a binary search space. Recent work on applying a Bandit-Based Random Mutation Hill-Climbing algorithm to the noisy OneMax Problem showed that it is important to choose a good value for the resampling number to make a careful trade off between taking more samples in order to reduce noise, and taking fewer samples to reduce the total computational cost. This paper extends that observation, by deriving an analytical expression for the running time of the RMHC algorithm with resampling applied to the noisy OneMax problem, and showing both theoretically and empirically that the optimal resampling number increases with the number of dimensions in the search space.
Droste @cite_6 defined a model for the OneMax problem, in which during every fitness evaluation of the bit-string @math , there was exactly one uniformly-chosen random bit mis-read with probability @math . Hence the measured noisy fitness values are equivalent to replacing the Gaussian noise term in by an appropriate discrete random variable taking values from @math . Under this scheme, Droste showed that (1+1)-EA with mutation probability @math could optimise a @math -bit OneMax problem corrupted by , with high probability, in polynomial time if @math is @math .
@cite_6
1569002781
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.