基于深度强化学习编排的仿生元启发式算法组合用于二进制组合优化

《Biomimetics》:Recent Advances in Bioinspired Robot and Intelligent Systems

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

编辑推荐:

  基于学习的超启发式算法(learning-based hyper-heuristics)在组合优化中用于从底层算子(low-level operators)中进行选择,或对单一元启发式算法(metaheuristic)的参数进行调优。然而,在二进制组合优化问题

  
基于学习的超启发式算法(learning-based hyper-heuristics)在组合优化中用于从底层算子(low-level operators)中进行选择,或对单一元启发式算法(metaheuristic)的参数进行调优。然而,在二进制组合优化问题中,尚未有研究对在共享一个演化种群(evolving population)及其联合配置(joint configuration)的完整基于种群的元启发式算法之间进行在线选择进行公式化与评估。本研究提出了这样一种公式化方法,并在两个二进制域上进行了评估:多维背包问题(multidimensional knapsack problem,MKP)和集合覆盖问题(set covering problem,SCP)。一个近端策略优化(proximal policy optimization,PPO)智能体编排了一个由七种自然启发式基于种群的元启发式算法组成的组合,在每次决策时将完整种群在方法间转移,并在每次固定迭代量子(quantum)后基于一个十四维、与规模无关的搜索状态描述进行决策。在相同的状态、奖励和组合下,实例化了三种丰富程度递增的动作空间:离散选择(discrete selection);通过算法特定翻译映射(translation maps)进行的联合选择与配置(joint selection and configuration);以及通过单纯形分配(simplex allocation)实现的异构协同进化(heterogeneous co-evolution)。这三种技术在Chu和Beasley cb9数据集上采用五折交叉验证、二十个记录种子,以近期文献中的最优已知值(best-known values)为基准进行评估,选择技术还在65个集合覆盖实例上进行了评估。在cb9上,选择智能体优于盲循环(blind round-robin)和随机基线(random baselines)。协同进化智能体排名第二,与最优已知值的差距为最强单一元启发式算法之后的若干百分点。在评估预算减半的情况下,两个智能体排名第一和第二;在集合覆盖问题上,由于没有单一方法占主导地位,选择智能体在十一种策略中排名第一。未训练对照和组合消融实验表明,策略主要学习的是应避免哪些成员;联合选择与配置智能体尚未能优于盲基线。本研究的公式化方法、翻译映射、单纯形分配和评估协议随研究一并发布。
一、研究背景与问题
组合优化问题广泛存在于工程、管理与运筹领域,其中多维背包问题和集合覆盖问题均为经典的NP-hard二进制组合优化问题。自然启发式基于种群的元启发式算法,如遗传算法、粒子群优化和差分进化等,通过模拟生物进化、群体行为和动物回声定位等自然机制,已成为求解此类大规模问题的主流工具。然而,这类方法的有效性高度依赖于两个需要人工决策的环节:选择何种元启发式算法,以及如何配置其参数。这两个选择均具有实例依赖性和搜索阶段依赖性,无免费午餐定理从理论上说明了不存在固定最优答案。
超启发式算法通过在启发式空间而非解空间中进行搜索来应对这一依赖性问题,由高层策略在运行过程中决定下一步应执行哪个底层组件。已有研究大多在单一进化算法内部选择移动算子或扰动算子,或将学习应用于单一元启发式算法内部的参数自适应。然而,将多个完整的、异构的基于种群的元启发式算法作为选择单元,在共享一个演化种群的前提下进行在线编排,并同时处理算法选择与配置问题,此前尚未被系统公式化与评估。此外,现有方法多采用固定自适应规则或仅依赖信用统计的无状态机制,缺乏基于搜索状态的条件化决策能力。
二、研究内容与结论
针对上述问题,研究人员提出了一种基于深度强化学习的超启发式框架,将七个完整的自然启发式基于种群的元启发式算法组成组合,包括遗传算法(GA)、模因遗传算法(MGA)、岛屿遗传算法(Island GA)、分布估计算法(EDA)、成功历史自适应差分进化(SHADE)、粒子群优化(PSO)和 dolphin回声定位算法(Dolphin)。该框架的核心设计包括:每次决策时将完整种群在方法间转移,使组合在单一演化种群上运行;采用近端策略优化(PPO)智能体作为决策器,观察十四维与规模无关的搜索状态描述;实例化三种丰富程度递增的动作空间,即离散选择、联合选择与配置、以及基于单纯形分配的异构协同进化。
研究在Chu和Beasley cb9数据集(30个实例,500个物品,5个约束)上采用五折交叉验证、二十个记录种子、600次运行的系统协议进行评估,并在65个OR-Library集合覆盖实例上验证了框架的跨域迁移能力。结果表明:在cb9上,选择智能体优于循环和随机基线,但落后于最强的单一方法Island GA;协同进化智能体排名第二,与Island GA差距约0.03个百分点。在评估预算减半时,两个学习智能体排名第一和第二。在集合覆盖问题上,由于没有单一方法占主导地位,选择智能体在十一种策略中排名第一。控制实验表明,策略主要学习的是避免选择PSO和Dolphin这两个表现崩溃的成员;移除这两个成员后,学习智能体并未获得提升。联合选择与配置智能体在该训练预算下未能优于盲基线。此外,cb7诊断研究证明,基准与预算共同决定了选择问题是否存在。
这项研究的重要意义在于:首次系统公式化并评估了在共享单一演化种群的条件下,通过深度强化学习在线编排完整异构基于种群元启发式算法组合的框架;验证了该框架跨二进制域的迁移能力;提出了翻译映射、单纯形分配和系统评估协议等可复用产品;为自主集体仿生优化系统提供了概念基础,使异构生物启发搜索行为能够通过学习的决策机制动态协作而非依赖固定规则。
三、关键技术方法
研究人员采用了以下主要技术方法:一是近端策略优化(PPO)算法,在Stable-Baselines3框架中实现,采用分离的策略与价值网络,通过14个并行环境进行训练;二是完整种群转移机制,每次决策时将整个种群从当前元启发式算法传递给下一个,不重新初始化;三是十四维与规模无关的状态表示,包含停滞信号、种群多样性、与当前最优解的归一化汉明距离、多样性崩溃信号、近期改进指示、后代接受率和预算比例等特征;四是三种动作空间实例化,即离散选择、通过算法特定翻译映射实现的联合选择与配置(三个抽象旋钮映射到各方法的原生参数)、以及通过单纯形分配实现的异构协同进化;五是五折分层交叉验证协议,按约束紧度分层,训练与评估分离,使用二十个记录种子;六是修复算子,采用贪婪随机化构造与变邻域下降和迭代局部搜索结合,对不可行候选进行修复。评估基准包括cb9多维背包问题(30个实例,500个物品)和OR-Library集合覆盖问题(65个实例)。
四、研究结果
5.1 训练动态:五个折的选择智能体各训练21504个时间步,价值函数的解释方差在各折间一致,训练策略的熵保持在最大值的较高水平,每个方法获得11%至18%的训练决策。确定性评估策略远非均匀且各折不同,总体而言Island GA获得30.1%、SHADE获得27.9%、EDA获得23.5%的评估决策,而PSO和Dolphin几乎只在表现最差的折3中被选择。
5.2 cb9比较评估(RQ1):十五种策略中,Island GA单独运行以0.56的GAP领先,协同进化智能体以0.59紧随其后,MGA为0.60,选择智能体为0.64。选择智能体在四个折中优于循环和随机基线,配对检验拒绝等值假设但效应量可忽略。选择智能体落后Island GA约0.08个百分点,协同进化智能体落后约0.03个百分点。修复仅基线达到1.00的GAP,未训练对照达到0.68但标准差为训练智能体的十四倍,且存在灾难性失败运行。
5.3 PSO与Dolphin的决策追踪与组合消融:训练记录显示,PSO在1.9%的决策后改进最优解,Dolphin在2.7%的决策后改进,而其他五种方法为7%至13%;在第五次决策后,PSO和Dolphin的改进率降至0.05%和0.08%。移除这两个方法后重新训练的智能体达到0.63的GAP,与七方法智能体的0.64相当,学习对cb9的贡献集中在避免产生最差结果的成员。
5.4 第二域:集合覆盖问题(RQ2):在状态、奖励、组合和超参数不变的条件下,仅更换问题工厂,选择智能体以0.18的GAP在十一种策略中排名第一,优于GA(0.21)、MGA(0.21)、SHADE(0.22)和Island GA(0.23)。没有单一元启发式算法领导超过一个折,而选择智能体是唯一领导超过一个折的策略,且具有最佳的平均折排名(2.0)。
5.5 评估预算与量子的敏感性:在预算减半时,协同进化和选择智能体排名第一和第二(0.58和0.62),循环第三(0.68),而Island GA、GA和MGA分别跌至第九、第十和第十一。量子变化对智能体GAP无显著影响,但更细的量子对盲选择器在低预算下有帮助。
5.6 相同协议下的cb7诊断:在cb7上,十一种策略的GAP跨度仅0.2个百分点,选择智能体(0.19)与循环(0.18)和随机选择(0.19)不可区分,验证了饱和论证,即基准与预算共同决定选择问题是否存在。
五、讨论与结论
讨论部分指出,cb9结果部分回答了RQ1:学习选择智能体优于盲选择策略,但落后于最强的单一方法;协同进化智能体是cb9上最佳学习策略。控制实验定位了学习的贡献:学习不改变典型运行但消除灾难性运行,这些运行来自选择PSO和Dolphin。集合覆盖问题回答了RQ2:在无主导成员的域上,选择智能体排名第一且具有最佳平均折排名。两个域共同界定了该技术的运行条件:改进信号必须在所用预算下具有信息量,且当无单一成员主导时,相对于最佳单一方法的优势才会显现。
结论部分翻译如下:本文提出了一个共享的序贯决策框架,用于编排具有完整种群转移的基于种群的元启发式算法组合,实例化为三种动作丰富程度递增的技术。在cb9实例上,协同进化智能体达到0.59的平均GAP,选择智能体达到0.64,而两个盲选择器为0.68和0.72,未训练对照为0.68,Island GA为0.56。在评估预算减半时,两个智能体排名第一和第二(0.58和0.62),而Island GA跌至0.88。在65个集合覆盖实例上,选择智能体以0.18的平均GAP在十一种策略中排名第一,比最佳单一方法低0.03个百分点。控制实验表明,策略主要学习的是避免哪些成员。联合选择与配置智能体在该预算下尚不能优于盲基线。cb7诊断研究确立了基准与预算共同决定选择问题是否存在。该框架被视为迈向自主集体仿生优化系统的第一步,未来工作将加入bandit和选择函数基线、扩大联合智能体的训练规模、分离训练运行方差与实例方差、改进奖励设计并扩展至连续域。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号