Plus Strategies are Exponentially Slower for Planted Optima of Random Height

Previous work showed that if all However, both these results have some limitations. As Jorritsma, local optima have the same relative height, then the plus strategy Lengler and Sudholt argued in [10], the Cliff function models never loses more than a factor (log) compared to the comma a rather peculiar type of landscape, and many local optima may strategy. Here we show that even small random fluctuations in the not be represented well by this landscape. Concretely, the Cliff heights of the local optima have a devastating effect for the plus function features a massive plateau of local optima, and when an strategy and lead to superpolynomial runtimes. On the other hand, algorithm manages to escape this plateau, then even a random walk due to their ability to escape local optima, comma strategies are unaffected ignoring fitness returns to the plateau with high probability. This by the height of the local optima and remain efficient. Our is arguably different from local optima in many natural problems.