On the effectiveness of restarting local search
Aldeida Aleti, Mark G. Wallace, Markus Wagner · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2021
Premature convergence can be detrimental to the performance of search methods, which is why many search algorithms include restart strategies to deal with it. While it is common to perturb the incumbent solution with diversification steps of various sizes with the hope that the search method will find a new basin of attraction leading to a better local optimum, it is usually unclear whether this strategy is effective. To establish a connection between restart effectiveness and properties of a problem, we introduce a new property of fitness landscapes termed Neighbours with Similar Fitness. We conjecture that this property is true for many PLS-complete problems, and we argue that the effectiveness of a restart strategy depends on this property.