Adaptive Sampled Walk: A Simple and Efficient Autonomous Local Search

Abstract We introduce and explore the automation and adaptation of partial neighborhood local search. Unlike traditional approaches requiring extensive parameter tuning, we design our approach to operate with minimal prerequisites. Specifically, we extend the sampled walk and ID walk algorithms by using distance-based calculations over a sliding window to determine the number of neighbors to evaluate at each step. To validate their performance, we empirically evaluate these parameter-free methods on four challenging combinatorial optimization benchmark problem classes from the literature, comparing them against fixed-parameter versions across multiple values. Our experiments show that, despite their simplicity, generic nature, and absence of parameters, these approaches achieve robust and competitive results across diverse problems—including different solution representations, neighborhood structures, and fitness landscape characteristics—thus validating the viability of generic autonomous local search methods.