Optimal resampling for the noisy OneMax problem
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Maximizing Drift is Not Optimal for Solving OneMax
It may seem very intuitive that for the maximization of the OneMax problem $\OM(x):=\sum_{i=1}^n{x_i}$ the best that an elitist unary unbiased search algorithm can do is to store a best so far solution, and to modify it …
A Reinforcement Learning Perspective on the Optimal Control of Mutation Probabilities for the (1+1) Evolutionary Algorithm: First Results on the OneMax Problem
We study how Reinforcement Learning can be employed to optimally control parameters in evolutionary algorithms. We control the mutation probability of a (1+1) evolutionary algorithm on the OneMax function. This problem i…
Evolutionary AlgorithmsQ-Learningreinforcement-learningReinforcement Learning+1Already Moderate Population Sizes Provably Yield Strong Robustness to Noise
Experience shows that typical evolutionary algorithms can cope well with stochastic disturbances such as noisy function evaluations. In this first mathematical runtime analysis of the $(1+\lambda)$ and $(1,\lambda)$ evol…
Evolutionary AlgorithmsRuntime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function
Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited …
On the Robustness of Median Sampling in Noisy Evolutionary Optimization
Evolutionary algorithms (EAs) are a sort of nature-inspired metaheuristics, which have wide applications in various practical optimization problems. In these problems, objective evaluations are usually inaccurate, becaus…
Evolutionary Algorithms