Abstract: The 0-1 knapsack problem (KP) is a classical NP-hard problem with wide applications in the field of combinatorial 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 population diversity by introducing the insertion cross assimilation operator, the two-bit mutation mechanism and the assistance 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 exploration 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 algorithms. 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.

Key words: 0-1 knapsack problem, imperialist competitive algorithm, assimilation operator, diversity mechanism, multi-head attention mechanism, deep reinforcement learning

摘要： 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背包问题, 帝国竞争算法, 同化算子, 多样性机制, 多头注意力机制, 深度强化学习