arXiv:2512.03805cs.LG2025-12被引 2

用深度强化学习优化遗传算法参数,显著提升求解效率。

Deep Reinforcement Learning for Dynamic Algorithm Configuration: A Case Study on Optimizing OneMax with the (1+($λ$,$λ$))-GA

  • 采用DDQN和PPO控制遗传算法种群规模,自动学习最优配置策略。
  • 改进的奖励机制使算法在不同问题规模下保持稳定高效,样本效率提升数个数量级。
  • 揭示了强化学习在动态参数配置中的根本挑战,适合算法优化研究者参考。

动态算法配置(DAC)旨在为参数化优化算法高效识别控制策略。本文系统研究了两种深度强化学习方法——双深度Q网络(DDQN)和近端策略优化(PPO)——在控制(1+(λ,λ))-GA求解OneMax问题时的表现。尽管OneMax结构简单,但其配置空间复杂,构成一个受控而具挑战性的基准。研究发现DDQN和PPO面临可扩展性下降与学习不稳定的双重挑战,源于探索不足与规划视野覆盖不全。为此,提出自适应奖励偏移机制,利用奖励分布统计增强探索,避免实例特异性调参,确保跨问题规模一致性能。进一步表明,无折扣学习在DDQN中有效,而PPO因方差问题难以收敛,即使超参数优化也无法获得有效策略。最终,结合自适应奖励的DDQN达到与理论最优策略相当的性能,且样本效率远超以往方法。研究揭示了标准深度强化学习在该场景下的根本局限,并指明有效学习的关键要素。

原文摘要 · Abstract (English)

Dynamic Algorithm Configuration (DAC) studies the efficient identification of control policies for parameterized optimization algorithms. Numerous studies leverage Reinforcement Learning (RL) to address DAC challenges; however, applying RL often requires extensive domain expertise. In this work, we conduct a comprehensive study of two deep-RL algorithms--Double Deep Q-Networks (DDQN) and Proximal Policy Optimization (PPO)--for controlling the population size of the $(1+(λ,λ))$-GA on OneMax instances. Although OneMax is structurally simple, learning effective control policies for the $(1+(λ,λ))$-GA induces a highly challenging DAC landscape, making it a controlled yet demanding benchmark. Our investigation reveals two fundamental challenges limiting DDQN and PPO: scalability degradation and learning instability, traced to under-exploration and planning horizon coverage. To address under-exploration, we introduce an adaptive reward shifting mechanism that leverages reward distribution statistics to enhance DDQN exploration. This eliminates instance-specific hyperparameter tuning and ensures consistent effectiveness across problem scales. To resolve planning horizon coverage, we demonstrate that undiscounted learning succeeds in DDQN, while PPO faces fundamental variance issues necessitating alternative designs. We further show that while hyperparameter optimization enhances PPO's stability, it consistently fails to identify effective policies. Finally, DDQN with adaptive reward shifting achieves performance comparable to theoretically derived policies with vastly improved sample efficiency, outperforming prior DAC approaches by orders of magnitude. Our findings provide insights into the fundamental obstacles faced by standard deep-RL approaches in this challenging DAC setting and highlight the key methodological ingredients required for effective learning.

强化学习算法优化遗传算法动态配置

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。