The Neighbours' Similar Fitness Property for Local Search
This work addresses a foundational issue in optimization theory for researchers, but it is incremental as it builds on existing concepts to formalize conditions for local search effectiveness.
The paper tackles the problem of why local search outperforms random sampling in optimization by introducing the Neighbours' Similar Fitness (NSF) property, and it provides a general proof that neighborhood search beats random search for NSF landscapes with an additional property.
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.