关于0－1背包问题的研究＊

王 雯，武 燕

（太原工业学院，山西 太原 030008）

0 引言

背包问题是一种组合优化问题，具有较强的实际意义，从现实应用角度来看，货物的装箱问题、物资的分配和存储问题等都可以用背包问题来解决。随着现代网络的日益发展，在电子商务领域中，背包公钥密码的应用也越来越广泛。但是当求解问题的数量较多时，最优解的求解还是比较困难，所以，对0－1背包问题进行算法研究或改进是一件很有必要的工作。

传统求解背包问题的方法有近似算法和精确算法，其中，近似算法包括贪婪法、粒子群算法［1］、遗传算法、蚁群算法［2］等；精确算法包括回溯法、动态规划法等。精确算法存在空间及时间复杂性的问题，为克服此缺点，用近似算法求解背包问题已经越来越受到人们的关注。除了上述这几种常见的算法以外，还出现了二进制差异演化算法［3］、知识进化算法［4］等新的算法。还有粗糙集也可以用于解决背包问题，将粗糙集理论引入遗传算法来解决背包问题，目的在于提高单纯遗传算法的搜索效率，同时也可以改善解的质量。

1 0－1背包问题［5］

背包问题可以这样理解：假设一位商人有一个容量为C公斤的背包，现在有n个重量和价值分别为ci＞0和pi＞0（i＝1，2，…，n）的物件，选择哪几个物件放入背包，能使所装物件的价值最大，并且不超过背包的容量限制。

0－1背包问题是指每类物件都有一件放入或者不放入。设变量为xi，当物件i被放入时，则xi＝1；不放入时，xi＝0。其数学表达式为：

2 常规算法在求解0－1背包问题中的应用

2.1 近似算法

2.1.1 贪婪法

贪婪法属于一种启发式算法，贪婪算法会以当前状况为基础作最优选择，容易忽略整体，但它可以在较短的时间内求到解，在很多情况下可以达到预期的目的，缺点是该启发式算法不一定能够获得最优解。

贪婪策略对贪婪法求取最优解至关重要，常用的贪婪策略有质量贪婪准则和价值密度贪婪准则、价值贪婪准则。这3种贪婪策略对背包的装入都是采用多步过程来完成的。贪婪法可以与其他算法相结合来解决背包问题，例如有杨婷婷、赵新超的更贪心粒子群算法，对于大规模背包问题的求解非常有帮助；此外还有马杰良和刘茜提出的混合遗传算法［6］，贪婪算法可以为遗传进化过程打下良好的基础，最终结果表明在求解质量及速度方面该算法都卓有成效。

2.1.2 遗传算法

遗传算法具有高效性、全局最优性和并行性的优点，广泛应用于函数的优化过程中，它把问题中每个可能性的解当成群体的一个染色体，再对染色体进行编码，依据目标函数进行个体评价，得出适应值，并依据适应值开始寻优，其寻优过程由选择和杂交、变异步骤实现［7］。在此过程中，选择算子及杂交算子影响寻优过程的搜索能力，变异算子则决定了寻优过程中空间的每个点都能被搜索到，因此该算法具有能够搜索全局最优解的优点。

采用传统的遗传算法解决背包问题时，得到最优解或近似最优解的前提是背包问题的规模较小，当背包问题的规模较大时，会出现早熟的情况，不会得出理想的结果，需要进一步改进。改进的方法可以用罚函数法来对目标函数进行改造；还可以把贪心算法和遗传算法相结合，贪心算法可以对染色体的解码过程进行改造，即为混合遗传算法。

除此以外，文献［8］把禁忌搜索算法和遗传算法相结合，为背包问题的解决提供了新的思路，该算法在父代种群的选择、杂交和变异操作基础上，对产生的子代单独个体进行禁忌搜索，搜索完成后，该个体将会被邻域的最优解取代。当禁忌搜索完所有子代个体后，就完成了新种群的衍生过程。其实验结果说明，该算法在搜索效率及收敛速度上卓有成效。

另外文献［9］指出了主动进化遗传算法的思想，这种算法在对种子个体进行编码时采用概率编码方法，用定向变异方式代替了交叉操作，可以使遗传算法的寻优过程更为有效和确定，避免了传统遗传算法中由于是不定向变异而产生的盲目性。

2.1.3 蚁群算法

蚁群算法具有较强的鲁棒性和全局优化性，并且该算法容易与其他优化算法相结合，在车辆路径系统与通信系统等方面应用较为完善。在利用蚁群算法解决0－1背包问题时，关键点在于某一物件聚集的信息素越多，该物件就越有可能被选中。对应于0－1背包问题的物件取值0，1，利用蚁群算法时将一个变量设为两只蚂蚁，并定义目标函数f为［10］：

其中：M为一充分大的正数。

蚁群算法应用于背包问题的具体过程可概括为首先要对迭代次数进行设置，之后把各蚂蚁放在对应变量的0或1位置点，然后依据转移概率对各蚂蚁进行移动，依据强度更新方程对信息素的轨迹进行更新，最后对当前最佳蚂蚁的位置点进行记录，往复循环此过程直至达到退出条件。

一般情况下蚁群算法的收敛速度较快，但当数据的数量增多时，蚁群算法的收敛速度随数据规模的增大而降低。很多学者对该算法的缺点进行了改进，在减少算法时间和降低寻优计算量方面做出了一定贡献。文献［11］提出了一种新的混合算法，该方法使用蚁群算法得到优化解，为扩大解的搜索空间使用了抗体克隆选择算法，这种混合算法可以提高收敛的速度，同时也在一定程度上增强了寻优的能力。文献［12］中把交换策略引入到蚁群算法中，对不属于禁忌表的有向线段序号及属于禁忌表的有向线段序号进行交换，该局部优化方法可改善每一代构造的解，因此解的质量可以得到很好的改善，使收敛速度明显加快。文献［13］提出一种新的基于解的相异度的蚁群算法，这种算法把信息量放在物件上，而非传统蚁群算法将信息量放在路径上，同时该算法增加了信息量的局部更新机制，如果一个物件被选中，其信息量会马上减少，从而降低其他蚂蚁选择该物件的可能性，变异操作可以依据相异度适当地对变异概率进行调整。这种算法中解的变异概率是由解的相异程度决定的，因此可以克服解的早熟现象，无论是解的全局性还是解的多样性都得到了很大的改善，特别适用于求解数量多、规模大的背包问题。

2.2 精确算法

2.2.1 动态规划法

在20世纪50年代，Richard Bell man提出了动态规划法，这种方法可以将多阶段决策问题转换成一些相互关联的单阶段问题，再对这些单阶段问题逐个解决。此方法可以较好地解决离散性问题，其整体思路可概括为在把原问题分解成许多子问题的基础上，通过每个子问题的求解最终得出原问题的解。

在所有背包问题的求解算法中，动态规划算法被公认为是一种经典算法，该算法具有便于实现及思路简单的优点，但也有不足之处，如果背包问题的数量较多、规模较大时此方法就有很大的局限，维数过高，复杂度大大增加，存在维数障碍，不易实现。

2.2.2 回溯法

回溯法中采用了深度优先的策略，在整个解空间树中，根结点作为始发点，从这开始搜索整个解空间树，结束时必须使根结点的每个子树都被搜索完成。在求解0－1背包问题时，回溯法一定程度上可以得到最优解，但当问题的数量较多时实现起来会比较困难。

可见，当背包问题的规模较小时，精确算法具有较强的实用性，但当背包问题的规模不断增大时，其计算复杂，往往得不到最优解。

2.3 各种算法的分析与比较

通过上面的研究可知，各算法都有优、缺点：①贪婪法速度较快，但不足之处是不一定能获得最优解；②遗传算法能够获得近似最优解，但可能会产生早熟的情况；③蚁群算法能够获得近似最优解，但问题的规模较大时，收敛速度不理想；④动态规划法能够获得最优解，但求解过程速度较慢，并且如果背包问题的数量较多时不宜实现；⑤回溯法能够获得最优解，但时间的复杂度比较高，背包问题的规模较大时实现比较困难。

因此，上述各种算法的不足之处可以概括为两种：即最优解容易陷入局部最优；不能在较短的时间内求出全局最优解。

3 解决背包问题算法的发展方向

关于背包问题算法的发展过程，从最早解决背包问题的精确算法，到之后又产生的近似算法，以及一些混合算法，这些方法都卓有成效，但依然有很多不足。未来背包问题算法的发展方向之一是将知识发现算法引入到传统的算法当中，用知识发现算法挖掘背包问题中的主要信息。

在知识发现算法中，粗糙集理论常用来解决一些不精确的问题，适用于知识的分类及获取，同时可以利用粗糙集理论的知识化简能力对知识系统进行化简，减少属性及属性值，降低属性项目复杂的计算程度。

用粗糙集理论来解决0－1背包问题的可能性是存在的，可以使用粗糙集理论发现0－1背包问题中的主要物件，在此基础上再利用遗传算法对它进行迭代运算。遗传算法在解决0－1背包问题时会产生大量数据，使用粗糙集理论对数据进行化简、筛选和分析，这样可以降低数据的复杂程度和维数，使用提炼及概括后的数据会较容易发现遗传算法中的重要基因位，可以避免遗传算法陷入局部最优解，并在一定程度上改善遗传算法的搜索效率。

本文提出将知识发现算法和遗传算法相结合，使用粗糙集理论的属性化简能力对遗传算法进化信息数据表进行约简，进而可以更有效地解决0－1背包问题。

［1］ 马慧民，叶春明，张爽.二进制改进粒子群算法在背包问题中的应用［J］.上海理工大学学报，2006，28（1）：31－34.

［2］ 刘华蓥，林玉娥，刘金月.基于蚁群算法求解0／1背包问题［J］.大庆石油学院学报，2005，29（3）：59－63.

［3］ 蔡鸿英，郝志峰，王志刚，等.解0－1背包问题的二进制差异演化算法［J］.计算机工程与设计，2009，30（7）：1716－1721.

［4］ 马慧民，叶春明，张爽，等.背包问题的知识进化算法［J］.计算机工程，2009，35（6）：208－212.

［5］ Silvano Martello，David Pisinger，Paolo Toth.New trends in exact algorithms for the 0－1 knapsack problem［J］.European Journal of Operational Research，2000，123：325－332.

［6］ 刘茜，马杰良.对求解0－1背包问题的混合遗传算法的改进［J］.重庆科技学院学报，2006，8（4）：84－87.

［7］ 王小平，曹立明.遗传算法——理论、应用与软件实现［M］.西安：西安交通大学出版社，2006.

［8］ 王乐.对解决背包问题的遗传禁忌搜索算法的研究［D］.郑州：郑州大学，2006：29－35.

［9］ 史亮，董槐林，王备战，等.求解大规模0－1背包问题的主动进化遗传算法［J］.计算机工程，2007，33（13）：31－33.

［10］ 马良，王龙德.背包问题的蚂蚁优化算法［J］.计算机应用，2001，21（8）：4－5.

［11］ 赵朝卿，胡小兵.一种新的求解0－1背包问题的混合算法［J］.计算机工程与应用，2008，44（18）：61－63.

［12］ 潘夏福，倪子伟.基于交换策略的蚁群算法求解多维0－1背包问题［J］.计算机与现代化，2008（3）：83－85.

［13］ 秦玲，白云.解0－1背包问题的蚁群算法［J］.计算机工程，2006，32（6）：212－214.