2024/08/31 by Denis Antipov, Antipov, Denis, Benjamin Doerr +1 · 1 citation
Computer Science · #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE)
paper · pdf · doi:10.48550/arxiv.2409.00306
openalex publication_date 2024/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Randomized search heuristics (RSHs) are known to have a certain robustness to noise. Mathematical analyses trying to quantify rigorously how robust RSHs are to a noisy access to the objective function typically assume that each solution is re-evaluated whenever it is compared to others. This aims at preventing that a single noisy evaluation has a lasting negative effect, but is computationally expensive and requires the user to foresee that noise is present (as in a noise-free setting, one would never re-evaluate solutions). In this work, we conduct the first mathematical runtime analysis of an evolutionary algorithm solving a single-objective noisy problem without re-evaluations. We prove that the (1+1) evolutionary algorithm without re-evaluations can optimize the classic LeadingOnes benchmark with up to constant noise rates, in sharp contrast to the version with re-evaluations, where only noise with rates O(n-2 log n) can be tolerated. This result suggests that re-evaluations are much less needed than what was previously thought, and that they actually can be highly detrimental. The insights from our mathematical proofs indicate that this similar results are plausible for other classic benchmarks.