Student Surpasses the Teacher: Apprenticeship Learning for Quadratic Unconstrained Binary Optimisation

This study introduces a novel train-and-test approach referred to as apprenticeship learning (AL) for generating selection hyper-heuristics to solve the Quadratic Unconstrained Binary Optimisation (QUBO) problem. The primary goal is to automate the design of hyper-heuristics by learning from a state-of-the-art expert and to evaluate whether the apprentice can outperform that expert. The proposed method collects detailed search trace data from the expert and trains the apprentice based on the machine learning models to predict heuristic selection and parameter settings. Multiple data filtering and class balancing techniques are explored to enhance model performance. The empirical results on unseen QUBO instances show that indeed, “student surpasses the teacher”; the hyper-heuristic with the generated heuristic selection not only outperforms the expert but also generalises quite well by solving unseen QUBO instances larger than the ones on which the apprentice was trained. These findings highlight the potential of AL to generalise expert behaviour and improve heuristic search performance.