Learning to Evolve MaxHS Populations: Contextual Bandit-Driven Crossover Bias and Mutation Rate in BRKGA

The Maximum Happy Set (MaxHS) problem selects exactly k ≤ |V | vertices to maxi-
mize the number of selected vertices whose neighbors are also selected. Although widely studied
theoretically, there is still no established algorithmic baseline for large instances. We propose a
learning-augmented Biased Random-Key Genetic Algorithm (BRKGA), where a contextual Lin-
UCB controller dynamically adjusts crossover elite-bias and mutation rate using population-level
and MaxHS-specific signals. Four variants are evaluated under a shared decoding and initialization
scheme: a vanilla BRKGA, versions with bandit-controlled mutation or crossover, and a joint-
control variant. On 114 benchmark instances, the joint controller increases MeanFitness from 29.14
to 29.98 and Wins(%) from 34.21% to 60.53%, with stronger gains on larger graphs; a paired
Wilcoxon signed-rank test confirms significance (p=0.0026). Ablation results indicate that muta-
tion control is the main driver of improvement, while joint control provides the most robust overall
performance.