  Evolutionary algorithms (EAs) are a sort of nature-inspired metaheuristics,
which have wide applications in various practical optimization problems. In
these problems, objective evaluations are usually inaccurate, because noise is
almost inevitable in real world, and it is a crucial issue to weaken the
negative effect caused by noise. Sampling is a popular strategy, which
evaluates the objective a couple of times, and employs the mean of these
evaluation results as an estimate of the objective value. In this work, we
introduce a novel sampling method, median sampling, into EAs, and illustrate
its properties and usefulness theoretically by solving OneMax, the problem of
maximizing the number of 1s in a bit string. Instead of the mean, median
sampling employs the median of the evaluation results as an estimate. Through
rigorous theoretical analysis on OneMax under the commonly used onebit noise,
we show that median sampling reduces the expected runtime exponentially. Next,
through two special noise models, we show that when the 2-quantile of the noisy
fitness increases with the true fitness, median sampling can be better than
mean sampling; otherwise, it may fail and mean sampling can be better. The
results may guide us to employ median sampling properly in practical
applications.
