Abstract: The quadratic knapsack problem is a kind of NP-Hard problem. It is difficult to solve this problem with the exact algorithms. To solve the problem, a new quantum-inspired evolutionary algorithm was proposed. The algorithm had a dynamic repair operator which considered two types of value： the value of an object and the value of associated with an object in the knapsack problem. At the same time, an improved quantum updating mode using three kinds of knowledge based on particle swarm optimization algorithm was presented. In this updating mode, the quantum could get more comprehensive knowledge during evolution. Performance of the algorithm on 100 standard quadratic knapsack problem instances was compared with other heuristic techniques. Results showed that the proposed algorithm was superior to these techniques in many aspects.

Key words: quadratic knapsack problem, quantum-inspired evolutionary algorithm, greedy repair operator, constrained optimization problem

摘要： 二次背包问题是一种NP难组合优化问题,其精确算法求解难度大,针对该问题提出了一种量子进化算法求解方法。该算法采用一种相对贪婪修补算子,该修补算子不但考虑了二次背包问题的每一物品项价值,而且考虑了物品的协作价值,是一种动态修补算子。同时算法借鉴粒子群算法中粒子的运动方程,提出了一种具有三类知识学习能力的量子更新模式,使得量子进化中获得的知识更全面。通过对100个国际上大规模二次背包问题进行测试实验,验证了提出的求解算法比相应的其他启发式算法性能有较大提升。

关键词: 二次背包问题, 量子进化算法, 贪婪修补算子, 约束优化问题