  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 how big the perturbation step should be. We introduce a new
property of fitness landscapes termed "Neighbours with Similar Fitness" and we
demonstrate that the effectiveness of a restart strategy depends on this
property.
