### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference |

Publisher | Association for Computing Machinery, Inc |

Pages | 242-248 |

Number of pages | 7 |

ISBN (Electronic) | 9781450361118 |

DOIs | |

State | Published - Jul 13 2019 |

Event | 2019 Genetic and Evolutionary Computation Conference, GECCO 2019 - Prague, Czech Republic Duration: Jul 13 2019 → Jul 17 2019 |

### Publication series

Name | GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference |
---|

### Conference

Conference | 2019 Genetic and Evolutionary Computation Conference, GECCO 2019 |
---|---|

Country | Czech Republic |

City | Prague |

Period | 7/13/19 → 7/17/19 |

### Fingerprint

### Keywords

- Noisy optimization
- Running time analysis
- Theory

### Cite this

*GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference*(pp. 242-248). (GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/3321707.3321837