Bandit-Based Random Mutation Hill-Climbing
This work addresses discrete optimization problems, particularly where fitness evaluations are expensive, offering an incremental improvement over an existing method.
The authors tackled the problem of improving the Random Mutation Hill-Climbing algorithm for discrete optimization by introducing a bandit-based method for neighbor selection, resulting in significant performance gains over the original algorithm in OneMax and Royal Road problems, with concrete improvements in both noise-free and noisy cases.
The Random Mutation Hill-Climbing algorithm is a direct search technique mostly used in discrete domains. It repeats the process of randomly selecting a neighbour of a best-so-far solution and accepts the neighbour if it is better than or equal to it. In this work, we propose to use a novel method to select the neighbour solution using a set of independent multi- armed bandit-style selection units which results in a bandit-based Random Mutation Hill-Climbing algorithm. The new algorithm significantly outperforms Random Mutation Hill-Climbing in both OneMax (in noise-free and noisy cases) and Royal Road problems (in the noise-free case). The algorithm shows particular promise for discrete optimisation problems where each fitness evaluation is expensive.