基于深度强化学习的自适应元启发式编排:迈向自主生物启发优化

《Biomimetics》:Towards Autonomous Bio-Inspired Optimization: Deep Reinforcement Learning for Adaptive Metaheuristic Orchestration

【字体: 大 中 小 】 时间:2026年09月23日 来源:Biomimetics 4.2

编辑推荐:

  面向组合优化的基于学习的超启发式算法从低级算子中进行选择,或调节单一元启发式算法的参数。然而,对于二值组合优化问题,在共享一个演化种群并通过公共动作空间进行联合配置的完整种群型元启发式算法之间进行在线选择,尚未被公式化或评估。本文提出了这样一种公式化,并在两个

  
面向组合优化的基于学习的超启发式算法从低级算子中进行选择,或调节单一元启发式算法的参数。然而,对于二值组合优化问题,在共享一个演化种群并通过公共动作空间进行联合配置的完整种群型元启发式算法之间进行在线选择,尚未被公式化或评估。本文提出了这样一种公式化,并在两个二值域上加以评估:多维背包问题(Multidimensional Knapsack Problem, MKP)和集合覆盖问题(Set Covering Problem, SCP)。一个近端策略优化(Proximal Policy Optimization, PPO)智能体编排了七个自然启发种群型元启发式算法的组合,在每次决策时将完整种群在方法之间转移,随后在每固定迭代量子上基于搜索状态的十四维、与规模无关的描述采取动作。在相同的状态、奖励和组合上,实例化了三种丰富度递增的动作空间:离散选择;通过算法特定翻译映射实现的联合选择与配置;以及通过单纯形分配实现的异构协同进化。这三种技术在五折交叉验证下使用二十个记录种子,在Chu和Beasley cb9基准集(500个物品,105次评估,量子100)上对照近期文献的已知最优值进行评估;选择技术还在65个集合覆盖实例上进行了评估。在cb9上,选择智能体领先于盲循环(round-robin)和随机基线。协同进化智能体位居第二,与最强单一元启发式算法相比,与已知最优值仅存在若干百分点的差距。在评估预算减半时,两个智能体排名第一和第二;在集合覆盖问题上,由于没有单一方法占据主导,选择智能体在十一种策略中排名第一。未训练对照和组合消融表明,策略主要学习避开哪些成员;联合选择与配置智能体尚未改进盲基线。该公式化、翻译映射、单纯形分配和评估协议随本研究公开。
**论文解读:深度强化学习编排种群型元启发式算法组合**

**1. 研究背景与问题**
自然启发、基于种群的元启发式算法(如遗传算法、粒子群优化等)是求解大规模二值组合优化问题的常用工具。其有效性高度依赖两个人工选择:运行哪种元启发式算法以及如何配置其参数。这两个选择往往随实例和搜索阶段变化,且“无免费午餐定理”表明不存在固定最优答案。超启发式算法通过在高层的启发式空间中搜索来缓解这一依赖,但已有工作多是在低级算子之间选择,或仅对单一元启发式调参。针对完整种群型元启发式算法,在共享一个演化种群的前提下进行在线选择与联合配置,并统一建模为马尔可夫决策过程(Markov Decision Process, MDP)的研究尚属空白。本研究填补了这一空白,并探索深度强化学习(Deep Reinforcement Learning, DRL)能否自主编排异构生物启发式搜索行为。

**2. 研究内容与关键方法**
研究人员提出了一个共享顺序决策框架:一个近端策略优化(Proximal Policy Optimization, PPO)智能体以固定“量子”迭代为周期,在七个基于种群的元启发式算法——遗传算法(Genetic Algorithm, GA)、模因遗传算法(Memetic Genetic Algorithm, MGA)、岛屿遗传算法(Island GA)、分布估计算法(Estimation of Distribution Algorithm, EDA)、成功历史自适应差分进化(Success-History based Adaptive Differential Evolution, SHADE)、粒子群优化(Particle Swarm Optimization, PSO)和回声定位(Dolphin Echolocation)——之间进行选择,并在每次决策时完整转移种群。状态是十四维、与实例规模无关的搜索特征(如停滞信号、种群多样性、改进指标等)。奖励由相对改进、停滞惩罚和多样性恢复奖励组合而成。框架实例化了三种丰富度递增的动作空间:离散选择、联合选择与配置(通过算法特定翻译映射将抽象旋钮转换为原生参数)、以及通过单纯形分配实现的异构协同进化。实验采用五折分层交叉验证,每折从其余实例训练、在未见实例上评估,使用二十个记录种子,并在多维背包问题(Multidimensional Knapsack Problem, MKP)的Chu和Beasley cb9集(30个实例,500个物品,30个约束)与集合覆盖问题(Set Covering Problem, SCP)的65个OR-Library实例上测试。问题工厂机制使状态、奖励和组合在两个领域间保持不变。

**3. 主要结果**
**3.1 训练动态**
五折训练中,确定性策略在各折间明显不同,通常集中选择Island GA、SHADE和EDA,极少选择PSO和Dolphin;训练熵保持较高,说明探索充分。

**3.2 cb9比较评估(RQ1)**
在标准预算下,选择智能体优于盲循环和随机选择基线,但弱于最强单一方法Island GA和MGA;协同进化智能体位居第二,接近最强单一方法。未训练对照网络性能极不稳定,且会因选择PSO/ Dolphin而出现灾难性失败;修复算子单独可达到中等水平,学习主要带来对不良成员的回避。

**3.3 PSO与Dolphin的决策轨迹与组合消融**
PSO和Dolphin在单独运行时表现崩坏,训练决策记录显示它们极少带来改进;训练后的策略几乎不选择它们。移除这两个成员后重新训练,智能体表现未提升,说明学习价值集中在避免这些成员。

**3.4 第二领域:集合覆盖问题(RQ2)**
在SCP上,选择智能体以最低平均GAP排名十一项策略之首,而主导cb9的Island GA仅列第五。无单一方法统领所有折,而选择智能体是唯一在多个折中领先的策略,表明框架可直接迁移到另一二值域。

**3.5 预算与量子敏感性**
将评估预算减半后,选择智能体和协同进化智能体升至第一、第二,而三类GA方法明显下降;其原因在于修复算子与实例松弛度之间的交互,交替选择方法的策略能更快获得修复收益。量子长度变化对智能体影响不大。

**3.6 cb7诊断**
在较小的cb7集上,预算充裕导致基准饱和,所有策略表现接近,无法区分选择效果;这验证了基准和预算共同决定选择问题是否存在的观点。

**4. 讨论与结论**
研究结论指出:当领域不存在单一主导方法时,学习的编排策略最有利;当存在主导方法时,学习智能体也能接近最优成员且无需先验知识。控制实验证明策略主要学习“避开哪些成员”。联合选择与配置智能体在该训练预算下尚未超过盲基线,配置维度需要更多训练。该框架被视作迈向自主集体生物启发优化的第一步——让异质生物启发行为通过学习机制动态协作,而非依赖固定规则。未来工作将加入更多基线、分离训练方差、改进奖励结构,并扩展到连续域。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号