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

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