计算机工程

作者：李斌, 郭毅

单位：1. 福建理工大学机械与汽车工程学院, 福建 福州 3501182. 福建理工大学福建省大数据挖掘与应用技术重点实验室, 福建 福州 3501183. 福建理工大学计算机科学与数学学院, 福建 福州 350118

关键词：深度强化学习,0-1背包问题,异构多背包问题,Transformer模块,动态惩罚机制,禁忌表

基金：教育部人文社会科学研究规划基金(19YJA630031)

从传统多背包问题(KP)与典型物流系统运作场景出发, 抽象出异构多背包问题(HMKP), 并制定改进深度确定性策略梯度(DDPG)算法对HMKP进行研究和求解。针对DDPG算法在解决0-1 KP时容易陷入局部最优的缺点, 采用动态随机机制(DRM)和动态惩罚机制(DPM)对DDPG算法进行改进, 并嵌入改进Transformer模块来优化算法, 提出基于改进Transformer模块的动态深度确定性策略梯度(TDP-DDPG)算法, 并加入禁忌表防止重复搜索。TDP-DDPG算法在多个实验算例中展现了高效的搜索能力, 在由低到高维度的测试集1、2以及更高维度的测试集3中所有39个算例都能找到最优值, 在大规模测试集4的6个算例中有3个能找到最优值。实验表明, TDP-DDPG算法在融入改进策略后具备更强的寻优能力。在此基础上, 设计基于TDP-DDPG算法的BPD-DDPG算法来解决复杂度更高的HMKP, 且分别在多个经典0-1 KP算例组合而成的高维度算例中进行分析评估。结果显示BPD-DDPG算法与商业求解器Gurobi相比虽求解时间长, 但在3个低规模算例中求解准确率比Gurobi高。BPD-DDPG算法能在可接受时间范围内以低计算代价高效解决高维度、大规模的HMKP。

来源：2026年第4期

《计算机工程》期刊编辑部

查看计算机工程杂志2026年第4期