差异演化算法求解多维0-1背包问题

摘要

多维0-1背包问题是典型的NP难题.设计了一种求解它的差异演化算法,阐述了算法求解多维0-1背包问题的具体操作过程.用提出的算法对55个测试算例进行了仿真实验,得到了全部算例的最优解.测试结果表明了算法是求解多维0-1背包问题的一种有效方法.%Multidimensional 0-1 knapsack problem is a typical NP problem. A kind of special differential evolution for multidimensional 0-1 knapsack problem is designed, and the detailed realization of the algorithm is illustrated. 55 multidimensional 0-1 knapsack test instances are tested by the produced algorithm, all instances achieve optimum solutions. Experimental results demonstrate the proposed algorithm is rather efficient for solving multidimensional 0-1 knapsack problem.