1、- 1 -背包问题的进一步讨论摘要：本文提出了背包问题的一种基于属性论的启发式算法。文章在开篇综述背包问题的一些基本情况后，接着介绍了属性论的一些基本观点、方法和理论，包括定性映射模型，人工神经元模型与定性映射模型的关系，量质转换程度函数等等。随后结合贪婪算法和背包核问题的思想，我们给出了物件基于核的一个定性映射。在根据背包的核问题的具体情况对属性论中传统的 Gauss 型转换程度作了必要的改进之后，我们给出了背包问题基于属性论的一个近似转化优化算法并且根据此算法用 Java 语言设计了背包问题软件包。软件包的设计充分结合了 Java 语言的特点，具有高性能和高的可扩展性，提供了可扩展的接口以
2、方便其他应用程序扩展和调用。关键字:背包问题，核问题，属性论方法，定性映射，转化程度函数- 2 -Knapsack problem further discussion(Mameijuan Department of Computer Science Institute Hexi College)Abstract: After the introduction of Knapsack Problem，we focus on the basic Points， Methods and theories of attribute theory Then, the QM of items on th
3、e basis of the Core has been introduced with the thoughts of greedy theories and core Problem theories. After the alternation of the ordinary Gauss convertion degree function, we Present an approximate algorithm based on the attribute theory. And then，a Software Package is presented in Java. The des
4、ign and implementation of the Package embody many features of the Java Programming language. And the Package Can be easily extended with a good API.KEYWORDS: knapsack Problem， Core Problem，qualitative mapping，conversion Degree function- 3 -1 引言 背包问题是一个在运筹学领域里常见的典型 NP-C 难题。工厂里的下料问题，管理中的资源分配，资金预算，投资决策
5、，装载问题等均可建模为背包问题。对该问题的求解方法的研究无论是在理论上，还是在实践中都具有重要意义。对于背包问题，己有的求解方法可分为精确算法(如动态规划，分支定界等)和近似算法(如贪婪法，蚁群算法，遗传算法等)两大类。因为精确算法的时间复杂性都是呈指数增长的，所以从六十年代逐渐提出了一些近似算法。1.1 历史背景背包问题(Knapsack problem)在50年代末期被Dantzig首次提出之后，在近年来被广泛的研究。这不仅是因为背包问题在工业和金融投资领域能得到直接的应用，更是因为很多理论上的原因。很多整数规划的问题的解决都依赖于一个高效的背包问题解法(在这些整数规划问题中，每当需要定界
6、的时候我们都需要解决一个背包子问题，因此，一个高效的背包问题解法就显得非常有必要。所有的背包问题都可以定性的描述为，从给定的物品集合中选择出一个子集，在不超出所有背包的负载的前提下，实现利益最大化。背包问题的不同种类的判定，是根据物品和背包的类型:在0-1背包问题(Knapsack problem)中，每一个物品最多被选择一次，而与之相对应的有界背包问题。(Bunded Knapsack problem)中能选择的物品数则可以在某个范围内取值;再比如多选择背包问题(Multi-constrained Knapsack problem)是说某几个物体必须选择一个或多个，而多背包的背包问题(Mul
7、ti Knapsack problem)则是说某些背包必须同时被装满。在这些背包问题家族中，最通用的形式是多条件约束背包问题伍加(Multi-constrained Knapsack problem)，而这在实质上就是正系数的整数规划问题(Integer Programming)。在下面我们将给出各种背包问题的数学模型。背包问题属于组合最优化问题。一般的，最优化问题(Optimization Problem)由目标函数(Objective Function)和约束条件(Constraints)两部分构成:Minimzief(x)=f(x， ，xZ，xn)Subjectotx=(xl，xZ，xn
8、)Sc x将满足所有约束条件的解空间s称为可行域(Feasible Region)，可行域中的解称为可行解(Feasible Solution);将可行域中使目标函数最小的解称为最优解(Optimal Solution)。对于最大化问题，可将目标函数乘以(-1)转化为最小化问题求解。当x或S为离散集合构成的解空间时，这类最优化问题称为组合最优化问题(Combinatoraial Optimization problem)。基于属性论的0-1背包问题算法研究衡量一个算法的好坏通常用算法中的加、减、乘、除和比较等基本运算的总次数同实例在计算机中计算时的二进制输入数据的大小关系来度量。我们对实例的二
9、进制输人长度和算法的基本计算总次数是粗略估计的，一般是给予一个上限。一个求解实例I的算法的基本计算总次数C同实例I的计算机二进制输入长度d(I)的关系常用符号C(I)=f(d(I)=O(g(d(I)表示。它的含义是:求解实例I的算法的基本计算总次数C(I)是实例- 4 -输入长度d(I)的一个函数，这个函数被另一个函数g(x)控制，即存在一个函数g(x)和一个正常a使得:C(I)ag(d(I)其中 g(x)的函数特性决定了基本计算总次数的性能。定义:假设问题和解决该问题的一个算法己经给定，如给定该问题的一个实例I，存在多项式函数 g(x)，使得成立，我们称该算法对实例 I 是多项式时间算法;若
10、存在 g(x)为多项式函数且对该问题任意的一个实例 I，都有(1-1-2)成立，则称该算法为解决该问题的多项式时间算法。定义:对于给定的一个优化问题，若存在一个求解该问题最优解的算法，一个多项实函数 g(x)和常数 a，使得对给定优化问题的任何一个实例成立，则称给定的优化问题是多项式时间可解问题，或简称多项式问题，所有多顶式问题集合记为 P(Polynomial)。并不是所有的组合最优化问题都找到了求解最优解的多项式时间算法。也就是说，还不能肯定一些组合最优化问题是否属于 P。经过几代数学家的努力，他们研究整理了一类难以求解的组合最优化问题，迄今为止，这些问题还没有一个有能求得最优解的多项式时
11、间算法。这一类组合最优化问题归为所谓 NP-hard,受人类认识能力的限制，目前人们只能假设这一类难解的组合最优化问题不存在求解最优解的多项式时间算法。所有的背包问题都属于 NP-hard 问题，这就是说我们设计出背包问题的多项式时间算法的可能性非常小。也即是说对于背包问题而言，我们除了枚举整个解空间而外就无法求得背包问题的精确解。然而，下面的一些技术的应用，使得我们的枚举可能变得相对容易一些，这些技术也是目前大多数算法设计思想的一个小结: 分枝定界，(Branch-and-bound):几乎是一个完整的枚举,只是使用上下界“剪枝”的方法避免扩展了一些不可能导出最优解的结点 11011111。
12、 动态规划(Dyamci Porgrpmming): 动态规划的方法是在宽础上添加了一些优先规则。有的时候也可以加入边界测试，方法在某些时候可以看作分枝定界的改进版本。 状态空间松弛(State Space Relaxatoin):在可能牺牲优化质量状态空间的大小，从而极大地减少算法的时间复杂度和空间包问题的很多高效近似解法都来源于此种思想。 预处理(Preporcessing): 通过一些特别的测试能预先确定出在向量中某些决策变量的取值，从而事先把他们排除在外，减与其它的算法设计者类似，本文作者在算法的设计中也用到了这些思背包问题各种形式的数学模型。1.2 背包问题各种形式的数学模型在这些类
13、型的背包问题中，我们用 Pj 表示选择物品 j 获得的效益品 j 的重量;物品需要放在承重能力为 C 的包裹中。同时我们还约定，所有这些系数p ,w 和 c 都是正整数。j- 5 -(1) 0-1背包问题(0-1 Knapsack problem)0-1背包问题是从有n个物品的物品集选取一个子集，在总容量c的前提下，使得相对应的利益实现最大化。可以用以下的的描述:Maximize jnjxp1Subject to CXWnjj10,1,M , j=1,n,jXj其中如果选择物品 j 那么决策变量 X 取 1，否则取。j(2) 有界背包问题(Bounded Knapsack Problem)物品
14、 j 最多可以选择 m 个，那么有界背包问题可以描述为:jMaximize jnjxp1Subject to CXWnjj10,1,M , j=1,n,jXj(3) 无界背包问题 (Unbounded Knapsack problem)无界背包问题实际上是有界背包问题的扩展，每个物品可以任意的取。但是因为包的承重能力有限，每个物品的数目不可能取到无穷大，因此，实际上它仍旧是一个有界背包问题。(4) 多选择背包问题 (Multi-choice Knapsack problem)多选择背包问题是 O-1 背包问题的另外一种扩展。扩展不是针对数目进行的，而是针对物品的类型。也即是说，从 k 类物品凡
15、(i=I，k)中选择出物品 j 使得最终的总获益最大。数学定义如下:Maximize ijkiNjxpI1Subject to CXWnjijNi1x 0 整数 ，j=1,.,n,j- 6 -但是因为包的承重能力有限，每个物品的数目不可能取到无穷大，因此，实际上它仍旧是一个有界背包问题。(5) 多选择背包问题 (Multi-choice Knapsack problem)多选择背包问题是 0-1 背包问题的另外一种扩展。扩展不是针对数目进行的，而是针对物品的类型。也即是说，从 k 类物品凡(i=I，k)中选择出物品 j 使得最终的总获益最大。数学定义如下:Maximize ijkiNjxpI1
16、Subject to CXWnjijNi1=1, i=1,k,ijj0,1, i=1,k,j NijXi这里如果物品 j 被从第 i 类中选择出来，那么决策变量 x =1。限定条件 ij=1, i=1,k,保证了每类物品能且只能选择一个。iNjjX(6) 最大子集和问题(Subset-sum Problem)如果 0-1 背包问题中每个物品的 P 都和它的 W 相等，就构成了最大子集j j和问题。数学定义如下:Maximize jnjxp1Subject to , i=1,.,m, CXnjji1x 0 整数，j=I,.n,j(7) 换零钱问题 （Change-making problem)这
17、是一类经常碰到的问题，要从一堆具有面值 w ，w ，w 的硬币中拿12n出 c 个货币单位的零钱找给顾客，目的是使得给出的硬币个数最少。其数学模型是:Maximize jnjx1- 7 -Subject to cXWnjj1x 0 整数，j=I,n,j(8) 多条件约束背包问题 （Multi-Constrained Knapsack problem)在前面我们己经提到，多条件约束背包问题是背包问题的一般形式，它在形式上，就是一个正系数的整数规划问题。其数学模型如下:Maximize jnjxp1Subject to , i=1,m, CXWnjji1x 0 整数，j=I,n,j以上的这些类型的
18、背包问题无论在理论上，还是在实践中都具有非常多的应用。在理论上，背包问题是很多组合优化问题的子问题，背包问题研究上的任何一个进步都会使得这些问题的解决受益。在实践环节上，背包问题并不局限于装箱问题。在投资问题中，某投资者用c个货币单位去做投资，有n个项目可供选择，其中第j个工程的投入w 而能j获得P 的利润。这样的投资问题就是一个0-1背包问题。j除了以上描述的简单的应用之外，背包问题还更主要的应用于货物装载，股票投资，预算控制，财务管理等问题。Diffe和Hellman根据最大子集和问题设计了背包公开加密算法。Martello和Toth，证明了计算机中双处理器任务分配问题也是一个最大子集和问
19、题。1.3 0-1背包问题背包问题可以看成普通整数规划问题的特殊形式。相反的情况也是成立的，也就是说，任何一个多条件的整数规划问题都可以等价的转化为一个单条件的整数规划问题，继而转化为 0-1 背包问题。我们考虑下面的整数规划问题:Maximize jnjxp1Subject to , CXnjj11,wnjj122- 8 -0 x u 整数，j=i,.n,jj算法：Maximize jnjp1Subject to , i=1,m, CXWnjji1x 0 整数，j=i,.n,j定理 l-1如果选择满足(1-3-4)的 ，那么(1-3-1)和(1-3-5)有相同的解集合。【证明】:很明显，对于
20、任意的因子 ，(1-3-1)的解都将是(1-3-5)的解。因此我们只用证明相反的情况。假设 x 是(1-3-5)的一个解，且令h(x)=K (l-3-6)很明显，K 是一个整数，因为所有的系数都是整数。我们希望证明，根据(1-3-4)选择得出的 可以使得 K=0。注意，(1-3-5)中的约束条件也可以写成:g(x)+ h(x)=O(l-3-7)通过代入(1-3-6)我们可以得出 g(x)+ K=0.而根据(l-3-4)，有|g(x)| ，而且 K 是整数，因此 K=0.根据(1-3-6)，h(x)=0，所以 g(x)=0.因此，x是(1-3-1)的可行解。证毕。我们反复的应用算法 1-1，就可
21、以将多个约束转化为单个约束。对于负系数的背包问题，很容易转化为正系数背包问题。我们还可以看出算法 1-1 的复杂度是线性的。因此，0-1 背包问题如果得到解决，那么背包问题就能够得到解决。1.4本文的结构和主要创新点本论文在研究了国内外大量文献的基础上，设计了一种基于属性论的背包问题近似算法。论文主要做了如下的工作:(1) 对背包问题的实例进行分类，并在测试过程中设计相应的实例产生策略。(2) 结合背包的核问题和属性论的相关理论，提出物件关于核的定性映射及核的模糊化。(3) 给出背包近似核大小的估计。(4) 改进传统属性论中的Gauss。型转化程度函数，以适应核问题的具体情况。(5) 充分运用
22、转化程度函数和贪婪算法的思想，根据国外背包算法的统计规律，设计转化优化算法。- 9 -(6) 为算法运用Java语言设计了易于扩展的软件包。(7 ) 用大量测试实例验证了算法的有效性。论文的创新点主要有以下五个方面:(1) 结合国内外背包的核问题的研究，提出物件关于核的定性映射模型。(2) 给出近似核大小的估计。(3) 改进传统属性论的Gauss型转化程度函数。(4) 运用转化程度函数和贪婪算法的思想，提出了核问题产生的原因的属性论假设并根据此假设设计转化优化算法。(5) 提供了软件包的实现。2 0-1背包问题算法及实现 2.1 算法原理及概述属性论方法在组合优化问题中已经得到了应用，例如谢意
23、军将转化成度函数成功应用于问题的研究中。作为另一个应用实例，本文提出的转换优化算法是基于属性论的背包问题的新型启发式算法。2.1.1启发式算法启发式算法是一种技术.这种技术使得在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。在某些情况下，特别是实际问题中，最优算法的计算时间使人无法忍受或因问题的难度使其计算时间随问题规模的增加以指数速度增加，此时只能通过启发式算法求得问题的一个可行解。早在40年代末期，由于实际问题的需要，人们已提出一些解决实际问题的快捷有效的启发式算法。随着70年代算法复杂性理论的完善，我们不再强调
24、一定要求得到最优解，因此促使80年代初兴起的现代优化算法在今天得到了巨大的发展。启发式算法的优点:(1)数学模型本身是实际问题的简化，或多或少会忽略一些因素，数据采集具有不精确性，参数估计具有不准确性，以上因素可能使最优算法所得解比启发式算法所得解产生更大误差;(2)有些难的组合优化问题可能还没有找到最优算法，即使存在，由算法复杂性理论，得知他们的计算时间是无法接受或不实际的;(3)有些启发式算法可以用在最优算法中，如在分支定界算法中，可以用启发式算法来估界;(4)简单易行，比较直观，易被使用者接受;(5)速度快，在适时管理中非常重要;(6)多数情况下，程序简单，因此易于修改。启发式算法的缺点
25、:- 10 -(1)不能保证求得最优解;(2)表现不稳定，启发式算法在统一问题的不同实例计算中会有不同的效果，有些解很好，而有些解则很差，在实际应用中，这种不稳定性造成计算结果不可信;(3)算法的好坏依赖于实际问题、经验和设计者的技术，这一点很难总结规律，同时使不同算法之间难以比较。蚁群算法，遗传算法，和贪婪算法都属于启发式算法，在近年来的研究中，这些思想被广泛的应用于背包问题领域，并且取得了较好的效果。但是由于理论上的原因，蚁群算法，遗传算法很难充分考虑到背包问题在结构上的特点，因此，在背包问题的研究领域中，很难取得比贪婪算法更优的解。基于以上原因，本文算法中，没有采用蚁群算法和遗传算法来求
26、取初始解，而是采用了贪婪算法。2.1.2 贪婪算法在下面的讨论中，我们假设物件应经按照质价比e =P /w 非递增排列，也jj即是e e 如果 ijij可能因为对象具有相同的质价比e ，使得很多序列都有这样的性质，这种j情况下我们任取一个。2.1.3 背包的核问题背包的”核”问题是Balas和 Zemel在1980年提出的，近年来国际国内几乎所有高效的背包问的算法几乎都利用了这种思想。Balas和Zemel证明了，在“核”的内部找到最优解的几率是非常高，这样就避免了考虑核外的对象，从而在规模上将背包问题变小。在理论上，我们要找到一个背包问题的核，在难度上是和解决背包问题是一样的，也就是说找寻背
27、包问题的精确核也是一个NP-hard，必须等到背包问题得到解决，精确核才能够找到，因此，找寻一个近似核的思想便很自然的得到了。Balas和Zemel在1980年做了以下的试验1221:让计算机生成规模=nl000，P和w 均匀分布在1，1000的背包实例，选择c保证所有的这些背包实例的不jj完整项都等于500。在按照(3-1-4)完全排序之后，利用分支定界法求取此背包的最优解。他们将最优解和贪婪算法的解x进行了比较，记录了x有异于最优解的次数.找到核之后，传统的方法都是对核内物件进行隐枚举或者分枝定界法去考虑，本文采取了一种新型的优化算法。算法的提出基于下面的一个假设:正是由于物件对核的转化程度的不同，才造成了背包核问题的产生。而我们的优化过程，正是对这一假设的仿真。背包问题的近似解的满意程度
