Neighbours similar fitness and the effectiveness of restarting local search
Aldeida Aleti, Mark G. Wallace, Markus Wagner · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2022
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 not clear 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 (polynomial-time local search)-complete problems, and we demonstrate that the effectiveness of a restart strategy depends on this property.