Abstract
We compare the $(1,\lambda)$-EA and the $(1 + \lambda)$-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.
Abstract (translated)
我们将比较在最近引入的基准测试集合DisOM上的$(1,\lambda)$-EA和$(1+\lambda)$-EA。以前的工作表明，如果所有局部最优解具有相同的相对高度，那么加法策略与逗号策略相比，最多只有$O(n\log n)$的差异。在这里，我们证明了即使是局部最优解高度的微小波动对加法策略也有毁灭性的影响，并导致超多项式运行时间。另一方面，由于它们能够逃避免试局部最优解，逗号策略对局部最优解的高度免疫，仍然有效。我们的结果对于各种可能的扭曲是有效的，并且表明，与加法策略相比，通常被局部无结构波动欺骗的策略是逗号策略，而不是加法策略。
URL
https://arxiv.org/abs/2404.09687
