Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsMathematical ProofsSimilar Papers 제목 키워드 기반
Optimal-margin evolutionary classifier
We introduce a novel approach for discriminative classification using evolutionary algorithms. We first propose an algorithm to optimize the total loss value using a modified 0-1 loss function in a one-dimensional space …
ClassificationEvolutionary AlgorithmsGeneral ClassificationMulti-class ClassificationAlready Moderate Population Sizes Provably Yield Strong Robustness to Noise
Experience shows that typical evolutionary algorithms can cope well with stochastic disturbances such as noisy function evaluations. In this first mathematical runtime analysis of the $(1+\lambda)$ and $(1,\lambda)$ evol…
Evolutionary AlgorithmsRuntime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise
In single-objective optimization, it is well known that evolutionary algorithms also without further adjustments can tolerate a certain amount of noise in the evaluation of the objective function. In contrast, this quest…
Evolutionary AlgorithmsRapidly Adaptable Legged Robots via Evolutionary Meta-Learning
Learning adaptable policies is crucial for robots to operate autonomously in our complex and quickly changing world. In this work, we present a new meta-learning method that allows robots to quickly adapt to changes in d…
Meta-LearningEVO-RL: Evolutionary-Driven Reinforcement Learning
In this work, we propose a novel approach for reinforcement learning driven by evolutionary computation. Our algorithm, dubbed as Evolutionary-Driven Reinforcement Learning (evo-RL), embeds the reinforcement learning alg…
OpenAI Gymreinforcement-learningReinforcement LearningReinforcement Learning (RL)