Plus Strategies are Exponentially Slower for Planted Optima of Random Height
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.
Code (1)
Similar Papers 제목 키워드 기반
Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima
It is an ongoing debate whether and how comma selection in evolutionary algorithms helps to escape local optima. We propose a new benchmark function to investigate the benefits of comma selection: OneMax with randomly pl…
Evolutionary AlgorithmsCircumventing spin glass traps by microcanonical spontaneous symmetry breaking
The planted p-spin interaction model is a paradigm of random-graph systems possessing both a ferromagnetic phase and a disordered phase with the latter splitting into many spin glass states at low temperatures. Conventio…
Spectral Algorithms Optimally Recover Planted Sub-structures
Spectral algorithms are an important building block in machine learning and graph algorithms. We are interested in studying when such algorithms can be applied directly to provide optimal solutions to inference tasks. Pr…
Community DetectionStochastic Block ModelReducibility and Statistical-Computational Gaps from Secret Leakage
Inference problems with conjectured statistical-computational gaps are ubiquitous throughout modern statistics, computer science and statistical physics. While there has been success evidencing these gaps from the failur…
On the optimality of joint periodic and extraordinary dividend strategies
In this paper, we model the cash surplus (or equity) of a risky business with a Brownian motion. Owners can take cash out of the surplus in the form of "dividends", subject to transaction costs. However, if the surplus h…