When resampling to cope with noise, use median, not mean

Due to their randomized nature, many nature-inspired heuristics are robust to some level of noise in the fitness evaluations. A common strategy to increase the tolerance to noise is to re-evaluate the fitness of a solution candidate several times and to then work with the average of the sampled fitness values. In this work, we propose to use the median instead of the mean. Besides being invariant to rescalings of the fitness, the median in many situations turns out to be much more robust than the mean. We show that when the noisy fitness is ϵ-concentrated, then a logarithmic number of samples suffice to discover the undisturbed fitness (via the median of the samples) with high probability. This gives a simple metaheuristic approach to transform a randomized optimization heuristics into one that is robust to this type of noise and that has a runtime higher than the original one only by a logarithmic factor. We show further that ϵ-concentrated noise occurs frequently in standard situations. We also provide lower bounds showing that in two such situations, even with larger numbers of samples, the average-resample strategy cannot efficiently optimize the problem in polynomial time.