  For most practical optimisation problems local search outperforms random
sampling - despite the "No Free Lunch Theorem". This paper introduces a
property of search landscapes termed Neighbours' Similar Fitness (NSF) that
underlies the good performance of neighbourhood search in terms of local
improvement. Though necessary, NSF is not sufficient to ensure that searching
for improvement among the neighbours of a good solution is better than random
search. The paper introduces an additional (natural) property which supports a
general proof that, for NSF landscapes, neighbourhood search beats random
search.
