text: 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.
  @cite_6: In practical applications evaluating a fitness function is frequently subject to noise, i. e., the “true fitness” is disturbed by some random variations. Evolutionary algorithms (EAs) are often successfully applied to noisy problems, where they have turned out to be particularly robust. Theoretical results on the behavior of EAs for noisy functions are comparatively very rare, especially for discrete search spaces. Here we present an analysis of the (1 + 1) EA for a noisy variant of OneMax and compute the maximal noise strength allowing the (1 + 1) EA a polynomial runtime asymptotically exactly. The methods used in the proofs are presented in a general form with clearly stated conditions in order to simplify further applications.
summary: 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 .