Simple Hyper-Heuristics Control the Neighbourhood Size of Randomised Local Search Optimally for LeadingOnes

Area of Science:

• Artificial Intelligence
• Optimization Algorithms
• Machine Learning

Background:

• Selection hyper-heuristics (HHs) employ machine learning to choose low-level heuristics for optimization.
• The necessity of sophisticated learning mechanisms in HHs is questioned.
• Simple HHs and their learning capabilities are analyzed on the LeadingOnes benchmark.

Purpose of the Study:

• To investigate if simple learning mechanisms are sufficient for effective hyper-heuristics.
• To analyze the performance of basic HHs, including Random Gradient HH.
• To introduce and evaluate the Generalised Random Gradient (GRG) HH.

Main Methods:

• Analysis of standard HHs (Simple Random, Permutation, Greedy, Random Gradient) on the LeadingOnes benchmark.
• Generalization of the Random Gradient HH to measure success over a time period.
• Theoretical analysis of the Generalised Random Gradient (GRG) HH's performance.
• Experimental validation for various problem sizes and parameter choices.

Main Results:

• Standard HHs like Simple Random, Permutation, and Greedy showed no learning.
• The Random Gradient HH demonstrated a basic reinforcement learning mechanism.
• The Generalised Random Gradient (GRG) HH was proven to optimally adapt neighborhood sizes for Randomised Local Search.
• GRG's performance improved with an increased number of low-level heuristics.
• GRG outperformed Randomised Local Search and Evolutionary Algorithms, especially for anytime performance.

Conclusions:

• Sophisticated learning mechanisms are not always necessary for high-performing hyper-heuristics.
• The Generalised Random Gradient (GRG) HH offers optimal performance by adapting neighborhood size.
• GRG demonstrates superior anytime performance compared to traditional methods.
• The effectiveness of GRG is enhanced by a larger pool of low-level heuristics.