基于帝国竞争演化与深度强化学习的背包问题优化算法

来源：计算机工程与应用杂志2025年第22期北京时间：

作者：李斌, 潘智成

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

摘要：0-1背包问题（knapsack problem，KP）是组合优化领域中一个具有广泛应用的经典NP难问题。针对原始帝国竞争算法（imperialist competition algorithm，ICA）在高维复杂问题中易陷入局部最优、全局探索能力不足的局限性，提出一种改进帝国竞争算法与融入多头注意力机制深度强化学习方法相结合的优化算法（improved imperialist competition algorithm incorporating deep reinforcement learning，IICA-DRL）。该算法通过引入插入交叉同化算子、双位变异机制和援助机制增强局部搜索能力和种群多样性，并利用多头注意力机制的深度强化学习模型对IICA高质量解进行优化，进一步增强了个体解的质量和算法的全局勘探能力。在4个测试集中的62个0-1 KP算例上进行性能评估，结果显示其中54个算例求解达到最优解。与20种元启发式算法进行了性能对比，实验结果表明，IICA-DRL算法具有较强的稳定性和有效性，初步验证了改进策略的可行性，为ICA求解背包问题提供了一个有效的算法设计方案。

关键词：0-1背包问题,帝国竞争算法,同化算子,多样性机制,多头注意力机制,深度强化学习