Automatic Adaptation of Mutation Rates for Move Acceptance Hyper-Heuristics Using Hypermutations

Move Acceptance Hyper-Heuristics (MAHHs) switch probabilistically between elitist and non-elitist acceptance rules to escape local optima. Previous work from the literature has shown that if a MAHH is equipped with a one-bit mutation operator (MAHH1-bit), then it remarkably optimizes the multimodal CLIFF function class much faster than the best possible elitist evolutionary algorithms (EAs) and non-elitist algorithms such as Metropolis. However, on harder to escape function classes such as standard JUMP functions, its performance is considerably worse than that of elitist EAs. If the MAHH framework is extended to use global mutation operators that allow for larger step-sizes than just one-bit flips, then its performance for JUMP becomes at least as good as that of elitist EAs, but the algorithm loses its advantages for CLIFF. Since high mutation rates are beneficial for JUMP-like functions and low ones instead for CLIFF-like functions, we propose aFast Adaptive MAHH𝛽, which integrates a power-law hypermutation operator with a self-adaptive mechanism to dynamically adjust the mutation rate. We rigorously prove that the algorithm achieves remarkably fast convergence on both CLIFF and JUMP functions, while maintaining optimal asymptotic performance on the ONEMAX unimodal function.