A Reinforcement Learning Perspective on the Optimal Control of Mutation Probabilities for the (1+1) Evolutionary Algorithm: First Results on the OneMax Problem

Luca Mossina, Emmanuel Rachelson, Daniel Delahaye

Abstract

Parameter tuning remains a significant challenge in the application of Evolutionary Algorithms (EAs). This paper explores a dynamic approach to mutation rate control by framing the (1+1) EA as a Markov Decision Process (MDP). Using Reinforcement Learning (RL) techniques, specifically Value Iteration and Q-Learning, the authors derive optimal mutation schedules for the OneMax benchmark. The results demonstrate that RL-derived policies can outperform traditional static and heuristic-based mutation controls, offering a new perspective on automated parameter adaptation.

Introduction

Evolutionary Algorithms (EAs) are powerful tools for complex optimization, yet their performance is highly sensitive to hyperparameter selection, such as mutation rates. Traditionally, these parameters are either kept constant (e.g., $1/n$) or adjusted via simple heuristics like the "1/5th rule." However, the optimal mutation rate is rarely static; it typically evolves as the algorithm progresses toward a solution.

Mossina, Rachelson, and Delahaye propose treating the EA as an environment and the parameter controller as an RL agent. This perspective allows for the discovery of optimal control policies that are often counter-intuitive to human designers but mathematically superior for specific problem landscapes.

Methods

The study focuses on the (1+1) Evolutionary Algorithm applied to the OneMax problem with a bitstring length of $n=50$. OneMax, which involves maximizing the number of set bits in a string, serves as a fundamental benchmark for convergence analysis.

The control problem is modeled as an MDP:

  • State ($s$): The current fitness value (number of correct bits).
  • Action ($\theta$): The mutation probability.
  • Reward: A constant $-1$ per iteration, incentivizing the agent to minimize the total steps to reach the optimum (fitness $n$).

Two approaches were used to solve the MDP. First, Value Iteration was applied to find the theoretical optimum by calculating exact transition probabilities. Second, Q-Learning was employed as a model-free alternative, simulating scenarios where the underlying transition dynamics are unknown.

Results and Discussion

The most significant finding is the nature of the optimal policy discovered via RL. Unlike standard heuristics that favor low mutation rates, the MDP-optimal policy initiates with a mutation probability near 1.0 when fitness is low, followed by a sharp decline as the algorithm nears the optimum.

Comparison of mutation probability schedules across different control policies.

This "high-initial-mutation" strategy suggests that aggressive exploration is more efficient in the early stages of OneMax than the cautious approach typically used in human-designed heuristics.

The performance of the MDP-derived policy was compared against a constant rate ($1/n$) and an adaptive heuristic ($1/(s+1)$). As shown in the performance table, the MDP policy achieved the lowest average number of steps to convergence.

Performance metrics (average steps to optimum) for the evaluated policies.

The MDP-optimal policy reached the solution in an average of 412 steps, outperforming the $1/(s+1)$ heuristic (430 steps) and the $1/n$ constant rate (442 steps). Notably, the standard deviation remained consistent across all methods, indicating that the RL policy provides a reliable performance gain rather than stochastic outliers.

Conclusion

This research successfully bridges Evolutionary Computation and Reinforcement Learning, demonstrating that RL can automate the discovery of superior mutation schedules. While the current study is limited by discrete action spaces and perfectly observable states in a "toy" problem, it lays the groundwork for more complex applications. Future work will explore continuous action spaces via Policy Gradient methods and address partially observable environments (POMDPs) where the distance to the optimum is not explicitly known.

Summary updated

Abstract

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 is modeled as a Markov Decision Process and solved with Value Iteration via the known transition probabilities. It is then solved via Q-Learning, a Reinforcement Learning algorithm, where the exact transition probabilities are not needed. This approach also allows previous expert or empirical knowledge to be included into learning. It opens new perspectives, both formally and computationally, for the problem of parameter control in optimization.
BibTeX
@misc{mossina2019reinforcement,
  author = {Luca Mossina and Emmanuel Rachelson and Daniel Delahaye},
  title = {{A Reinforcement Learning Perspective on the Optimal Control of Mutation Probabilities for the (1+1) Evolutionary Algorithm: First Results on the OneMax Problem}},
  year = {2019},
  eprint = {1905.03726},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.03726},
}
Figure