Adaptive Sampled Walk: A Simple and Efficient Autonomous Local Search

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Traditional local search methods often require extensive parameter tuning for optimal performance.
• Developing autonomous search algorithms that adapt to problem characteristics is a key challenge.

Purpose of the Study:

• To introduce and explore automated and adaptive partial neighborhood local search algorithms.
• To design local search methods that operate with minimal prerequisites and no parameter tuning.

Main Methods:

• Extended sampled walk and ID walk algorithms.
• Incorporated distance-based calculations over a sliding window to dynamically determine neighborhood evaluation size.
• Developed parameter-free local search techniques.

Main Results:

• Empirically evaluated parameter-free methods on four benchmark combinatorial optimization problem classes.
• Compared performance against fixed-parameter versions.
• Demonstrated robust and competitive results across diverse problems with varying solution representations, neighborhood structures, and fitness landscapes.

Conclusions:

• Parameter-free local search approaches are viable and effective.
• Autonomous local search methods offer a generic and robust alternative to parameter-tuned algorithms.
• The proposed methods validate the potential of generic autonomous local search.