3 papers
cs.AI2020
The Neighbours' Similar Fitness Property for Local Search
Mark Wallace, Aldeida Aleti
For most practical optimisation problems local search outperforms random sampling - despite the "No Free Lunch Theorem". This paper introduces a property of search landscapes terme…
cs.NE2019
Is perturbation an effective restart strategy?
Aldeida Aleti, Mark Wallace, Markus Wagner
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…
cs.DM2019
Steepest ascent can be exponential in bounded treewidth problems
David A. Cohen, Martin C. Cooper, Artem Kaznatcheev +1
We investigate the complexity of local search based on steepest ascent. We show that even when all variables have domains of size two and the underlying constraint graph of variabl…