  In many real-world optimization problems, the objective function evaluation
is subject to noise, and we cannot obtain the exact objective value.
Evolutionary algorithms (EAs), a type of general-purpose randomized
optimization algorithm, have been shown to be able to solve noisy optimization
problems well. However, previous theoretical analyses of EAs mainly focused on
noise-free optimization, which makes the theoretical understanding largely
insufficient for the noisy case. Meanwhile, the few existing theoretical
studies under noise often considered the one-bit noise model, which flips a
randomly chosen bit of a solution before evaluation; while in many realistic
applications, several bits of a solution can be changed simultaneously. In this
paper, we study a natural extension of one-bit noise, the bit-wise noise model,
which independently flips each bit of a solution with some probability. We
analyze the running time of the (1+1)-EA solving OneMax and LeadingOnes under
bit-wise noise for the first time, and derive the ranges of the noise level for
polynomial and super-polynomial running time bounds. The analysis on
LeadingOnes under bit-wise noise can be easily transferred to one-bit noise,
and improves the previously known results. Since our analysis discloses that
the (1+1)-EA can be efficient only under low noise levels, we also study
whether the sampling strategy can bring robustness to noise. We prove that
using sampling can significantly increase the largest noise level allowing a
polynomial running time, that is, sampling is robust to noise.
