计算机工程与应用2025，Vol.61Issue(22)：92-113,22.DOI:10.3778/j.issn.1002-8331.2411-0102
基于帝国竞争演化与深度强化学习的背包问题优化算法
Knapsack Problem Optimization Algorithm Based on Imperialist Competitive Evolution and Deep Reinforcement Learning
摘要
Abstract
The 0-1 knapsack problem(KP)is a classical NP-hard problem with wide applications in the field of combina-torial optimization.To address the limitations of the original imperialist competition algorithm(ICA),which is prone to fall into local optimality and lack of global exploration ability in high-dimensional complex problems,an optimization algorithm that combines the improved imperialist competition algorithm incorporating deep reinforcement learning with a multi-head attention mechanism(IICA-DRL)is proposed.The algorithm enhances the local search capability and popu-lation diversity by introducing the insertion cross assimilation operator,the two-bit mutation mechanism and the assis-tance mechanism,and optimizes the high quality solutions of IICA by using the deep reinforcement learning model with the multi-head attention mechanism,which further enhances the quality of the individual solutions and the global explora-tion capability of the algorithm.Performance evaluation is performed on 62 0-1 KP instances in 4 test sets,and the results show that 54 of the instances solved reach the optimal solution.The performance is compared with 20 meta-heuristic algo-rithms.The experimental results show that the IICA-DRL algorithm has strong stability and effectiveness,preliminarily verifies the feasibility of the improved strategy,and provides an effective algorithmic design scheme for ICA to solve the knapsack problem.关键词
0-1背包问题/帝国竞争算法/同化算子/多样性机制/多头注意力机制/深度强化学习Key words
0-1 knapsack problem/imperialist competitive algorithm/assimilation operator/diversity mechanism/multi-head attention mechanism/deep reinforcement learning分类
计算机与自动化引用本文复制引用
李斌,潘智成..基于帝国竞争演化与深度强化学习的背包问题优化算法[J].计算机工程与应用,2025,61(22):92-113,22.基金项目
教育部人文社会科学研究规划基金(19YJA630031). （19YJA630031）
