Plus Strategies are Exponentially Slower for Planted Optima of Random Height
This work addresses the problem of evolutionary algorithm design for optimization in noisy or fluctuating landscapes, highlighting a critical weakness of plus strategies, which is incremental as it builds on prior comparisons of these strategies.
The paper investigates the performance of (1,λ)-EA (comma) versus (1+λ)-EA (plus) strategies on the DisOM benchmark, showing that small random fluctuations in the heights of planted local optima cause super-polynomial runtimes for the plus strategy, while comma strategies remain efficient due to their ability to escape local optima.
We compare the $(1,λ)$-EA and the $(1 + λ)$-EA on the recently introduced benchmark DisOM, which is the OneMax function with randomly planted local optima. Previous work showed that if all local optima have the same relative height, then the plus strategy never loses more than a factor $O(n\log n)$ compared to the comma strategy. Here we show that even small random fluctuations in the heights of the local optima have a devastating effect for the plus strategy and lead to super-polynomial runtimes. On the other hand, due to their ability to escape local optima, comma strategies are unaffected by the height of the local optima and remain efficient. Our results hold for a broad class of possible distortions and show that the plus strategy, but not the comma strategy, is generally deceived by sparse unstructured fluctuations of a smooth landscape.