Optimal resampling for the noisy OneMax problem
This work provides incremental improvements for researchers in optimization algorithms dealing with noisy environments.
The paper tackled the problem of optimizing the resampling number in the noisy OneMax problem to balance noise reduction and computational cost, showing theoretically and empirically that the optimal resampling number increases with the number of dimensions.
The OneMax problem is a standard benchmark optimisation problem for a binary search space. Recent work on applying a Bandit-Based Random Mutation Hill-Climbing algorithm to the noisy OneMax Problem showed that it is important to choose a good value for the resampling number to make a careful trade off between taking more samples in order to reduce noise, and taking fewer samples to reduce the total computational cost. This paper extends that observation, by deriving an analytical expression for the running time of the RMHC algorithm with resampling applied to the noisy OneMax problem, and showing both theoretically and empirically that the optimal resampling number increases with the number of dimensions in the search space.