Abstract: Multidimensional Knapsack（MKP） is a typical NP-hard problem in combinatorial optimization problem. It is widely used in engineering and management. A Modified Binary Differential Evolution algorithm（MBDE） is proposed to solve the MKP problem. The key steps of the proposed algorithm can be divided into two parts： the binary group is generated; the candidate feasible solutions are obtained. The feasible solution is obtained by modifying the binary individual in the process of calculating the fitness value of the individual. An effective method for measuring the density of values is proposed for the repair of binary individuals. In addition,an opposite search strategy and an elite local search strategy are designed to improve accuracy and convergence speed of MBDE by increasing the exploration and the exploitment of the algorithm. To demonstrate the efficiency of MBDE, three sets of benchmark instances are solved and some comparisons with other methods available in literature are shown. MBDE algorithm obtains higher precision and running speed. The experimental results show that MBDE algorithm is very suitable for solving large-scale MKP problem.

Key words: Multidimensional Knapsack（MKP）, Differential Evolution（DE）, density of value, opposite search, elite local search

摘要： 多维背包（MKP）是组合优化中一个典型的NP难问题，广泛应用于工程和管理中。提出了一种改进的二进制差分演化算法（Modified Binary Differential Evolution algorithm，MBDE）求解MKP问题，算法关键步骤可分为两部分：二进制群体生成；得到候选可行解。提出了一种有效的衡量商品价值密度的方法用于对二进制个体修正和优化；设计了反向测试搜索和精英局部搜索策略来提高算法探索和开发能力，从而进一步提高了MBDE的求解精度和收敛速度。为验证MBDE算法的有效性，进行了三组实验，并和近期提出的解决MKP问题的其他启发式算法进行了比较，实验结果显示，MBDE算法求解精度更高。从算法运行时间看，求解速度快，非常适合求解大规模的MKP问题。

关键词: 多维背包, 差分演化算法, 价值密度, 反向测试搜索, 精英局部搜索