The Neighbours' Similar Fitness Property for Local Search

Mark Wallace 1 and Aldeida Aleti 1 1 Monash University, Wellington Road, Clayton, Vic and 3800, Australia Abstract 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. 1 Introduction Local Search is a successful class of methods used to solve many large complex optimisation problems. A problem (S,f) is defined as a set S of candidate solutions, termed its search space, and a fitness function f that maps candidate solutions to a fitness measure. Many researchers have explored why different forms of local search [ Burke and Kendal, 2014 ] are so effective, and deep theoretical studies have been published on the performance of algorithms on specific classes of problems [ Michiels et al., 2007 ] . Our focus is on challenging problems for which it is hard to find optimal (or just "good") solutions. In section 5 it will also be shown that all the example hard problems (classed as PLS-Complete) in [ Michiels et al., 2007 ] have this same property that solutions thin out towards the optimum.