（计算机应用技术专业论文）基于概率粒子群算法的背包问题的研究.pdf

华北电力大学硕士学位论文摘要 摘要 背包问题属于n p 难问题，解决背包问题是解决组合优化所面临的问题之一， 在现实中有着广泛的应用背景，开展对解决复杂组合优化问题的算法研究具有一定 的理论意义和实用价值。 本文在对背包问题进行研究分析的基础上，分析和比较了各类方法，提出了一 种用于求解0 1 背包问题的基于概率模型的粒子群算法。该算法利用对概率向量的 操作实现群体的进化，来提高算法性能。然后利用本文构造的算法分别针对不同规 模的背包问题进行了求解。实验结果表明本文提出的概率粒子群优化算法可以有效 的改进算法收敛能力和寻优效果。 关键词：粒子群算法，b m d a ，组合优化，背包问题，概率粒子群 a b s t r a c t k n a p s a c kp r o b l e mi sb e l o n g sa m o n gn p - h a r dp r o b l e m s ，a n di ti sa l s oo n eo ft h e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s k n a p s a c kp r o b l e mh a sw i d ea p p l i c a t i o n si nal o t o ff i e l d s ，s oi ti sm e a n i n g f u lf o ro p t i m i z i n gt h ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m i nt h i st h e s i s ，a n i m p r o v e da l g o r i t h m b a s e do n p r o b a b i l i t yp a r t i c l e s w a r l n o p t i m i z a t i o ni sp r o p o s e d ，w h i c hi s u s e df o rs o l v i n g0 1 k n a p s a c kp r o b l e m ，a f t e r a n a l y z i n ga n dc o m p a r i n gk i n d so fm e t h o d st ok n a p s a c kp r o b l e m i ti m p r o v e st h e p e r f o r m a n c et h r o u g ho p e r a t i n go nt h ep r o b a b i l i t yv e c t o rw h i c hh e l p st h eg r o u pe v o l v e a n dt h e nw es o l v ed i f f e r e n ts c a l e so fk n a p s a c kp r o b l e mw i t ht h en e wa l g o r i t h m t h e e x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h mh a sa d v a n t a g e si ni m p l e m e n te f f i c i e n c ya n d c o n s t r i n g e n ts p e e d w e iy i ( c o m p u t e r a p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f z h a n gg u o l i k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ，b m d a ，c o m b i n a t o r i a lo p t i m i z a t i o n ， k n a p s a c kp r o b l e m ，p r o b a b i l i t yp s o 华北电力大学硕士学位论文摘要 摘要 背包问题属于n p 难问题，解决背包问题是解决组合优化所面临的问题之一， 在现实中有着广泛的应用背景，开展对解决复杂组合优化问题的算法研究具有一定 的理论意义和实用价值。 本文在对背包问题进行研究分析的基础上，分析和比较了各类方法，提出了一 种用于求解0 1 背包问题的基于概率模型的粒子群算法。该算法利用对概率向量的 操作实现群体的进化，来提高算法性能。然后利用本文构造的算法分别针对不同规 模的背包问题进行了求解。实验结果表明本文提出的概率粒子群优化算法可以有效 的改进算法收敛能力和寻优效果。 关键词：粒子群算法，b m d a ，组合优化，背包问题，概率粒子群 a b s t r a c t k n a p s a c kp r o b l e mi sb e l o n g sa m o n gn p - h a r dp r o b l e m s ，a n di ti sa l s oo n eo ft h e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s k n a p s a c kp r o b l e mh a sw i d ea p p l i c a t i o n si nal o t o ff i e l d s ，s oi ti sm e a n i n g f u lf o ro p t i m i z i n gt h ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m i n t h i st h e s i s ，a n i m p r o v e da l g o r i t h m b a s e do np r o b a b i l i t yp a r t i c l es w a r l n o p t i m i z a t i o n i s p r o p o s e d ，w h i c hi su s e df o rs o l v i n g0 1k n a p s a c kp r o b l e m ，a f t e r a n a l y z i n ga n dc o m p a r i n gk i n d so fm e t h o d st ok n a p s a c kp r o b l e m i ti m p r o v e st h e p e r f o r m a n c et h r o u g ho p e r a t i n go nt h ep r o b a b i l i t yv e c t o rw h i c hh e l p st h eg r o u pe v o l v e a n dt h e nw es o l v ed i f f e r e n ts c a l e so fk n a p s a c kp r o b l e mw i t ht h en e wa l g o r i t h m t h e e x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h mh a sa d v a n t a g e si ni m p l e m e n te f f i c i e n c ya n d c o n s t r i n g e n ts p e e d w e iy i ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f z h a n gg u o l i k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ，b m d a ，c o m b i n a t o r i a lo p t i m i z a t i o n ， k n a p s a c kp r o b l e m ，p r o b a b i l i t yp s o 声明尸明 本人郑重声明：此处所提交的硕士学位论文基于概率粒子群算法的背包问题的研 究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得 的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 学位论文作者签名：耄延望垒日期：避：12 1 留 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件：学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播 学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：导师签名： 华北电力大学硕十学位论文 1 1 选题的背景和意义 1 1 1 组合优化问题 第一章绪论 在人们的生活和工作中，总会碰到各种各样的问题，而解决这些问题的方案又 有许多，组合优化问题是一种离散最优化问题，就是在给定约束条件下，求出使目 标函数极小( 或极大) 的变量组合问题。它的数学模型描述为： m i n 厂x ) s j g j ) s 0f = 1 以 f1 - 1 ) ix d 其中，o ) 为目标函数，g j o ) 为约束函数，x 为决策变量，d 表示由离散点组成的 集合。通常，一个组合优化问题可用三参数( d ，f ，) 表示，其中d 表示决策变量的 定义域，f 表示可行解域f ；缸l x e d ，g 。o ) ；0 ) ，厂表示目标函数，满足 ，o ) = m i n f ( x ) l x e f ) 的可行解石称为问题的最优解。 组合优化问题在规划、调度、资源分配、决策等问题中有着非常广泛的应用， 在国际上得到了广泛的重视。美国官方的科学、工程与公共事务政策委员会数学组 国防部分组1 9 8 3 年在报告“美国国防部与数学科学研究 中称：“在这个领域( 组 合优化) 内，存在着大量急需解决而又极端困难的问题，其中包括如何对各个部件 进行分隔、布线和布局的问题，这些问题是一大类已进行了多年研究的组合最优化 问题的典型例子 。该报告把“组合最优化”与“统计学 、“大规模控制系统”、“物 理数学和非线性分析 等并列为当前数学方面的几个重大研究课题。国际上许多优 秀的运筹学家、计算机科学家和数学家等都投入到这一领域，针对许多有重要意义 的组合最优化问题提出了相应的理论和优化算法，目前已发展成为运筹学和应用数 学的一个十分活跃的研究领域，具有重大的理论意义与实用价值，其目的主要是寻 找离散事件的最优编排、分组、次序或筛选等，是运筹学中的一个经典而重要的分 支。由于组合优化问题与大量的实际问题紧密地结合，越来越多的人开始研究组合 优化问题，提出许多新的方法和思路，使得组合优化问题内容越来越丰富。组合优 化问题的求解一直是近年来研究的热点领域之一。 典型的组合优化问题有旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ) 、0 1 背包问题 ( 0 - 1k n a p s a c kp r o b l e m ) 、加工调度问题( s c h e d u l i n gp r o b l e m ) 、装箱问题( b i n p a c k i n g p r o b l e m ) 、图着色问题( g r a p hc o l o r i n gp r o b l e m ) 、聚类问题( c l u s t e r i n gp r o b l e m ) 华北电力大学硕十学位论文 以及最大团问题( m a x i m u mc l i q u ep r o b l e m ) 和最大割问题( m a xc u tp r o b l e m ) 等。 这些问题数学描述非常简单，理论上说每一个组合优化问题都可以通过枚举的方法 求得最优解，但枚举是以时间为代价的，有的枚举时间还可以接受，有的则不可能 接受，即所谓的“组合爆炸 。对于这些n p 一完全【1 】的组合优化问题，至今尚无很 好的解析算法，一般采用启发式算法来解决。 本文将对其中具有代表性的一个组合优化问题：o 1 背包问题的求解进行研究。 1 1 2 背包问题 背包问题( k n a p s a c kp r o b l e m ) 是典型的组合优化问题之一，工厂里的下料问 题，管理中的资源分配、资金预算、投资决策、项目选择、材料切割、货物装载等 均可建模为背包问题，并且还常常作为其他问题的子问题加以研究。背包问题是运 筹学中的一个典型的p 难问题，p 难解问题类，意味着p 一p ，无法找到多项 式时间算法求得该类问题最优解。因此我们把研究的重点转向寻找能在较短时间 ( 多项式时间) 内得到接近于最优解的算法。大多数背包问题有拟多项式的时间算 法，这意味着若系数规模有所界定，在可接受的时间内能够得到最优解。背包问题 的应用背景促使人们对该问题计算方法进行了深入研究，背包问题的特有计算性质 又使其应用领域不断得到拓展。它的数学模型实际上是一个o 1 规划问题。0 - 1 背 包问题是指有不同价值、不同重量的物品n 件，求从这n 件物品中选取一部分物 品且对每一物品，要么选，要么不选，满足被选物品的总重量不超过背包指定的限 制重量且达到被选物品的价值总和最大的问题。如果所有物品的重量之和小于背包 的容量，则问题极其简单，所得利益也就是所有物品的价值之和，而实际问题往往 是背包的容量小于物品的重量之和1 2 j 。 背包问题可以衍生出一系列与之相关的优化问题，如有限背包问题( 物体可具 有相同价值和重量但数量是有限的) ，无限背包问题( 具有相同价值和重量的物体 数量可以是无限的) ，多背包问题( 将物体装入多个容量不同的背包) 等。本文中 所指背包问题如无特殊说明，均指简单o 1 背包问题。 背包问题在实践中有广泛的应用背景。许多简单结构的有机组合构成了复杂结 构，对简单问题的深入探索也使复杂问题的解决变得相对容易。在设计解决大量的 复杂组合优化问题算法时，背包问题往往作为子问题出现。背包问题的算法改进， 对复杂组合优化问题算法的改良是十分有益的。 1 1 3 粒子群优化算法 二十世纪八十年代以来，一些新颖的优化算法，如人工神经网络( a n n ) 、混 沌、遗传算法( g a ) 、进化规划( e p ) 、模拟退火( s a ) 、禁忌搜索( t s ) 等，通 2 华北电力大学硕十学位论文 过模拟或揭示某些现象和过程得到发展，其思想和内容涉及数学、物理学、生物进 化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手 段。在优化领域，由于这些算法构造的直观性与自然机理，因而通常被称为智能优 化算法( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) ，或称为现代启发式算法( m e t a h e u r i s t i c a l g o r i t h m s ) 。 本文研究的粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 最早是由心理学研 究者k e n n e d y 博士和从事计算智能研究的e l b e r h a r t 博士【3 】受到人工生命的研究结果 启发，于1 9 9 5 年提出的一种基于群智能( s w a r mi n t e l l i g e n c e ) 方法的进化计算技 术( e v o l u t i o n a r yc o m p u t a t i o n ) 。因其概念简单、实现容易，而迅速引起学术界的重 视。目前已被应用于多目标优化、模式识别、信号处理、决策支持等领域，被列为 “国际进化计算会议的一个讨论专题。 与其他进化计算技术相比，p s o 的优势在于简单容易实现，同时又有深刻的智 能背景，既适合科学研究，又特别适合工程应用。因此p s o 一经提出，立刻引起了 进化计算等领域的学者们的广泛关注，并在短短的几年时间里出现大量的研究成 果。目前，已提出了多种p s o 改进算法，并且p s o 已广泛应用于函数优化、神经 网络训练、模式分类、模糊系统控制以及其他的应用领域。但却大多是连续问题， 很少被用于解决离散问题。 粒子群算法可以被简单快速的执行，因此它对c p u 等硬件设备要求不高。另 外，它并不需要所考虑的目标函数的具体信息，不需要建立问题本身的精确模型， 也不依赖于知识表示，仅仅需要他的目标函数值和简单的数学操作。粒子群优化算 法已经被证明是一种有效的解决全局优化问题的方法，并且在某些情况下，它不会 遇到其它的进化计算方法所遇到的困难。 基本的p s o 算法是在连续域中搜索一个数值函数的最优值的有力工具，具有直 观，易操作，执行速度快，效率高等优点，已经被成功地应用于许多连续优化问题 中。但有些问题的解被设在一个离散空间中，典型的例子包括要求离散元素的顺序 或安排问题，如时序或路径问题，在这些问题面前普通的粒子群优化算法就显得无 能为力了。按照原有的思路，普通粒子群优化算法最后所求出的解并不能保证它是 在离散解空间的，因此使得已有的普通粒子群优化算法在求解离散问题是失去了原 有的优势，粒子群优化算法在解决离散问题上暂时陷入了困境。 同p s o 算法已经广泛的被用在连续优化问题中相比，用于解决离散问题的p s o 算法屈指可数，且效果大都不理想，它们都是从要解决的具体问题的特点入手，有 针对性地对基本p s o 算法作一些局部修改来达到求解目的。不具有代表性，都只能 在某些具体问题中发挥作用，无法真正推广到其他的离散问题中。我们所期望的是 3 华北电力大学硕士学位论文 一种可以对各种离散问题都有帮助的统一的解决模式，希望p s o 能在离散问题的解 决中发挥出像解决连续问题一样的高效的作用。与遗传算法相比，它深刻的智能背 景更具说服力，相信进一步研究它在离散问题中的应用是很有价值的。 1 2 国内外研究现状 1 2 1 背包问题的研究现状 背包问题属于组合最优化问题。严格意义上的最优解求取非常困难，研究高速 近似的算法是一个重要的发展方向。对全局优化问题，目前存在确定性和非确定性 两类方法。前者以b r i a n i n 的下降轨线法、l e v y 的隧道法和g e 的填充函数法为代 表。该类方法虽然收敛快、计算效率高，但算法复杂，求得全局极值的概率不大。 非确定性方法以c a r l o 的随机试验法、h a r t m a n 的多始点法、s o b s 和w e t s 的结合 梯度信息的搜索方法、模拟退火法( s i m u l a t e d a n n e a l i n g ) 等为代表。该类方法对 目标函数要求低、容易实现、稳定性好，但收敛速度慢、求得全局极值的概率较低。 对于背包问题，已有的求解方法可分为精确算法( 如枚举法，动态规划法，分支界 定法，图论法等指数级方法) 和近似算法( 如贪心算法，蚂蚁算法，遗传算法等) 两大类f 4 1 。 d a n t z i g 5j 在五十年代中期首先进行了开创性的研究，利用贪心算法求得了一个 理想解，得出了0 1 背包问题最优解的上界。在这之后二十几年里背包问题研究没 有取得太大进展，该上界也未得到改进。直到1 9 7 4 年，h o r o w i t z 和s a l m i 6 j 首先利 用分支定界技术设计出一个有效算法来解答背包问题，并提出了背包问题的可分 性，指明了解答该问题的一条新途径。之后，m a r t e l l o 和t o t h 7 】用整数约束和分支 定界技术第一个改进了d a n t z i g 上界。1 9 8 0 年，b a l a s 和z e m e 8 】首先提出了解答背 包问题的“核”( c o r e ) 思想，使该问题的研究有了较大进展。在九十年代末p i s i n g e r 利用平衡技术【9 l 和“核膨胀【1 0 j 思想设计的算法，该算法结合了动态规划技术，使 解答背包问题的算法有了实质进展。在进入二十世纪的九十年代以后，生物仿生技 术和i n t e r n e t 技术的飞速发展，使得模拟生物物理规律的各种并行近似算法不断涌 现，遗传算法已经在o 1 背包问题上得到较好的应用，蚂蚁算法、粒子群算法等仿 生算法也在各种组合优化问题中得到了应用。背包问题的特有计算性质又使其应用 领域不断得到拓展。m e r k l e 和h e l l m a n l 1 1 j 基于背包问题的难解性，设计出了第一 个公钥密码体制，开创了密码学的新方向。 1 2 2 粒子群算法的研究现状 p s o 是计算智能领域的又一种群智能算法，它同遗传算法类似，通过个体间的 协作和竞争实现全局搜索。系统初始化为一组随机解，称之为粒子。通过粒子在搜 4 华北电力大学硕十学位论文 索空间的飞行完成寻优，它没有遗传算法的交叉变异算子，而是粒子在解空间追随 最优的粒子进行搜索。 粒子群优化算法的研究大致可分为五个部分1 1 2 j ：算法、拓扑结构、参数、与其 他进化技术的融合和算法的应用。 起初，p s o 是为实值问题而设计，后来，算法逐渐扩展到二进制和离散问题。 两种最常用的p s o 算法是全局版本p s o 和局部版本的p s o 。这两种版本的差别在 于粒子的邻域不同，即各粒子最近邻的粒子。局部p s o 的粒子，其邻域仅为其两边 有限的几个粒子，而全局p s o 的邻域则为该群体所有粒子。如此以来，全局p s o 可 看成是局部p s o 的特殊情况。研究发现【1 2 l ，全局p s o 收敛较快，但易陷入局部极 小；而局部p s o 可搜索到更优的解，但速度稍慢。此外，为提高p s o 的性能，研 究者又设计了许多不同的邻域结构，包括金字塔结构、星型结构、小邻域结构，以 及冯u 诺以曼结构。试验结果表明，冯u 诺以曼结构比其他规整邻域结构效果要好， 包括全局和局部p s o 。研究还发现，对于复杂问题，采用小邻域结构要好，而对于 简单问题适于用大邻域结构。还有的学者对动态邻域结构进行了研究。通常，每种 结构都有其优势，但缺点也无法避免。对一些问题，可能该结构好，但另外一些问 题，则不然。 p s o 速度的改变由三部分组成：社会项、认知项和动量项。三部分如何平衡， 决定了p s o 算法的性能。原始p s o 中增加了第一个新参数为惯性权重( i n c r t i a w 色i 曲t ) 。惯性权重的引入是为了平衡全局与局部搜索能力。惯性权值较大，全局 搜索能力强，局部搜索能力弱，反之，则局部搜索能力增强，而全局搜索能力减弱。 动态惯性权值能够获得比固定值更为好的寻优结果。动态惯性权值可以在p s o 搜索 过程中线形变化，亦可根据p s o 性能的某个测度而动态改变，比如模糊规则系统。 随后，另一个参数称之为收缩因子( c o n s t r i c t i o nf a c t o r ) 的系数被引入，目的是希 望p s o 可以收敛。从数学上分析，这两个参数是等价的。 p s o 另一个研究的趋势【1 3 】是将其与其他进化计算技术相结合。有些研究者向 p s o 当中引入了一些算子，包括选择、交叉、和变异。通过选择算子，最好性能的 粒子将被直接复制到下一代，从而保持最优性能的粒子。同进化算法类似，通过交 叉算子，成对的粒子将交换相互的信息，以便有向新的搜索空间飞翔的能力。变异 算子主要目的是为了增加p s o 跳出局部极小的能力。另一方面，为了加快进化规划 算法的速度，研究者还借鉴了p s o 的速度思想，将其应用到进化规划当中，来指导 变异操作的进行。 p s o 原理上十分简单，所需参数也较少，并且易于实现，p s o 算法己经被成功 应用于函数优化，神经网络训练、模糊系统控制以及其他工程领域，但是这些算法 5 华北电力大学硕士学位论文 以及它们的大部分应用都是针对连续优化问题的【1 4 】，如何将p s o 算法应用于离散 空间优化问题，是一个重要的研究方向。 1 3 本文的组织 本文共六章。 第二章介绍了背包问题的基本知识和几种数学模型，并对已经实现的0 1 背包 问题的解决方法：精确算法和近似算法，分别进行了介绍和总结。 第三章介绍了粒子群优化算法的基本原理、数学模型及算法的实现，着重介绍 了三种典型的模型，然后介绍了几种已有的改进粒子群优化算法，并将p s o 与其他 几种进化算法进行了比较，最后介绍了p s o 在各个方面的一些应用，尤其重点介绍 了p s o 在离散领域的应用。 第四章重点介绍了如何构造了基于概率进化算法的粒子群算法，论述了粒子群 算法、概率分析进化算法和概率粒子群算法这三个方面的内容： ( 1 ) 粒子群算法 首先分析了基本粒子群算法存在的主要问题和改进思路，然后着重从粒子速度 更新项和收敛性能两个方面进行了剖析，并且提出了改进的措施如下：1 ) 去掉了 粒子群运动方程中的速度项；2 ) 为使粒子能够迅速、有效的摆脱局部最优解，将 突变策略引入了算法中。随后给出了改进后的p s o 流程图，并进行了典型函数的测 试分析，并作了与自适应粒子群算法和混沌组合优化算法的比较。 ( 2 ) 概率分析进化算法 介绍了概率分析进化算法的发展历程、基本原理和分类方法。 ( 3 ) 引入概率分析进化算法的粒子群算法 首先选用了概率分析进化算法中的b m d a ( b i v a r i a t em a r g i n a ld i s t r i b u t i o n a l g o r i t h m ，b m d a ) 与4 1 中的改进粒子群算法进行结合，并给出了具体实现方式。 然后分析了结合后的算法性能，找出了可能影响搜索速度的因素，并针对这些因素 给出了两种加快群体搜索速度的方法：改进了惯性权重的值的选择方式。最后介绍 了结合后的算法的流程。 第五章首先介绍了用于解决背包问题的概率粒子群算法的粒子构造方式，然后 将概率粒子群算法应用于背包问题的解决。分别针对小规模的背包问题和规模较大 的背包问题进行了求解。通过分析和比较计算结果，可以看到，本文提出的概率粒 子群优化算法可以有效的改进算法收敛能力和寻优效果。实验证明，该算法可以有 6 华北电力火学硕十学位论文 效的解决背包问题。 最后对全文进行了总结。 7 华北电力大学硕十学位论文 2 1 背包问题简介 第二章背包问题 弟一早月。巴l 口j 赵 背包问题( k n a p s a c kp r o b l e m ) 在5 0 年代末期由d a n t z i 9 1 5 1 首次提出之后，在近 年来被广泛的研究。这不仅是因为背包问题在工业和金融投资领域能得到直接的应 用，更是因为很多理论上的原因。很多整数规划的问题的解决都依赖于一个高效的 背包问题解法，在这些整数规划问题中；每当需要定界的时候我们都需要解决一个 背包子问题【1 5 l ，因此一个高效的背包问题解法就显得非常有必要。 所有的背包问题都可以定性的描述为，从给定的物品集合中选择出一个子集， 在不超出所有背包的负载的前提下，实现利益最大化。背包问题的不同种类的判定， 使根据物品和背包的类型：在0 1 背包问题( 0 1k n a p s a c kp r o b l e m ) 中，每一个物 品最多被选择一次，而与之相对应的有界背包问题( b o u n d e dk n a p s a c kp r o b l e m ) 中能选择的物品数则可以在某个范围内取值；再比如多选择背包问题 ( m u l t i p l e c h o i c ek n a p s a c kp r o b l e m ) 是说某几个物体必须选择一个或多个，而多背 包的背包问题( m u l t i p l ek n a p s a c kp r o b l e m ) 则是说某些背包必须同时被装满。在这 些背包问题家族中，最通用的形式是多条件约束背包问题( m u l t i c o n s t r a i n e d k n a p s a c kp r o b l e m ) ，而这在实质上就是正系数的整数规划问题( i n t e g e r p r o g r a m m i n g ) 。在2 2 中我们将给出各种背包问题的数学模型。 2 2 背包问题的数学模型 本文给出了七种类型的背包问题的数学定义。这些类型基本上涵盖了大多数的 常规应用。 在这些类型的背包问题中，我们用p ，表示选择物品j 获得的效益；用吩表示物 品的重量；物品需要放在承重能力为c 的包裹中。同时我们还约定，所有这些系 数p j ，w f 和c 都是正整数。 ( 1 ) 0 1 背包问题【1 6 1 ( 0 1k n a p s a c kp r o b l e m ) 0 1 背包问题是从有，1 个物品的物品集选取一个子集，在总体积不超过包裹容 量c 的前提下，使得相对应的利益实现最大化。可以用以下的公式进行形式化的描 述1 1 7 1 ： 8 华北电力大学硕十学位论文 m a x 咖妇p j x ， s u b j e c tf d x ，s c ( 2 1 ) l l x je o ，1 ) ，_ 。1 ，r 其中，如果选择物品j 那么决策变量x j 取1 ，否则取0 。 ( 2 ) 有界背包问题【1 7 1 ( b o u n d e dk n a p s a c kp r o b l e m ) 物品j 最多可以选择聊j 个，那么有界背包问题可以描述为： m 掘咖玩荟p ，x ， 蹦b j e c tt o 荟w “( 2 - 2 ) x ie o ，1 ，j 矩j ) ，j 一1 。鼻 ( 3 ) 无界背包问题【1 8 j ( u n b o u n d e dk n a p s a c kp r o b l e m ) 无界背包问题实际上是有界背包问题的扩展，每个物品可以任意的取。 m a x i m i z e 善p ，x 1 s c 蹦b j e c tt o x ，s c ( 2 - 3 ) j - j x ；0 整数，j = l ，n 但是因为包的承重能力有限，每个物品的数目不可能取到无穷大，因此，实际 上它仍旧是一个有界背包问题。 ( 4 ) 多选择背包问题【1 9 1 ( m u l t i c h o i c ek n a p s a c kp r o b l e m ) 多选择背包问题是0 1 背包问题的另外一种扩展。扩展不是针对数目进行的， 而是针对物品的类型。也即是说，从k 类物品m ( f = 1 ，戈) 中选择出物品使得最终 的总获益最大。数学定义如下： 9 华北电力人学硕士学位论文 m a 咖妇善磊；聊嘞 s u 岫幻著磊峋嘞“ ( 2 - 4 ) 磊嘞_ 1 ，f - 1 ，七 这里如果物品j 被从第i 类中选择出来，那z , 决策变量嘞一1 。限定条件 骞嘞。1 ，江k 七保证了每类物品能且只能选择一个。 ( 5 ) 最大子集和问题【2 0 1 ( s u b s e t s u mp r o b l e m ) 如果0 - 1 背包问题中每个物品的p j 都和他的相等，就构成了最大子集和问题。 数学定义如下： m a x i m i z e 善x j 一 5 “b j e c t 幻m x ，s c ( 2 - 5 ) j 。j z i o ，1 ，j 一1 ，。j l ( 6 ) 换零钱问题【2 1 1 ( c h a n g e m a k i n gp r o b l e m ) 这是一类经常碰到的问题，要从一堆具有面值m ，以的硬币中拿出c 个货币 单位的零钱找给顾客，目的是使得给出的硬币个数最少。其数学模型是： m i n 咖妇z ， j 。1 s u b j e c tt o 芝吁而一c ( 2 - 6 ) x ；0 ，且为整数，一1 。j l ( 7 ) 多条件约束背包问题【2 2 l ( m u l t i c o n s t r a i n e dk n a p s a c kp r o b l e m ) 在2 1 中我们已经提到，多条件约束背包问题是背包问题的一般形式，它在形 式上，就是一个正系数的整数规划问题。其数学模型如下： 1 0 华北电力大学硕士学位论文 m a x i m i z e p j x j j 。l s u b j e t ff d x js c i ，i k ( 2 7 ) ，, 善w i j m 石j 0 且为整数，- a 1 ，。j l 以上的这些类型的背包问题无论在理论上，还是在实践中都具有非常多的应 用。 在理论上，背包问题是很多组合优化问题的子问题，背包问题研究上的任何一 个进步都会使得这些问题的解决受益。 在实践环节上，背包问题并不局限于装箱问题。在投资问题中，某投资者用c 个 货币单位去做投资，有糟个项目可供选择，其中第j 个工程的投入w ，而能获得p ，的 利润。这样的投资问题就是一个0 1 背包问题。 除了以上描述的简单应用之外，背包问题还更主要的应用于货物装载，股票投 资，预算控制，财务管理等问题。d i f f e 和h e l l m a n 2 3 】根据最大子集和问题设计了背 包公开加密算法。m a r t e l l o 和t o t h 2 4 l 证明了计算机中双处理器任务分配问题也是一 个最大子集和问题。 由于任何一个多条件的整数规划问题都可以等价的转化为一个单条件的整数 规划问题，继而转化为0 1 背包问题。因此本文重点研究0 1 背包问题。 2 3 背包问题的算法简介 2 3 1 背包问题的精确算法简介 ( 1 ) 动态规划法 从理论上说，组合优化问题若有解，总是可以用枚举法找到。枚举法就是将问 题所涉及的对象一一列出，逐一比较或将问题相关的各种情况逐一考察，最后归纳 出需要的结论。对于背包问题，枚举法一共要列举n 种情况，每种情况还要判断m 个条件表达式。当m ，l 较大时，显然枚举法是不可行的。 动态规划法【2 5 】是解决多阶段决策过程最优化的一种数学方法。1 9 5 1 年美国数 学家贝尔曼等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系 列相互联系单阶段问题，然后逐个加以解决，从而创建了动态规划的方法。它的特 点是解决多阶段、离散性问题。它采用最优原则( p r i n c i p l eo fo p t i m a l i t y ) 来建立 用于计算最优解的递归式。所谓最优原则，不管前面的策略如何，此后的决策必须 是基于当前状态( 由上一次决策产生) 的最优决策。由于对于有些问题的某些递归 1 1 华北电力大学硕+ 学位论文 式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。若不能 保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行 回溯( t r a c eb a c k ) 以构造最优解。采用动态规划方法，可以很高效的解决许多用 分支定界法或贪婪法无法解决的问题。但是，动态规划方法也存在着不足之处： 到目前为止，还没有一个统一的标准模型可供应用。由于实际问题不同， 其动态规划模型也就不同。虽然理论上说可以把某些静态规划的问题转化为动态规 划模型来求解，但这种转化有时将变得十分困难，需要丰富的想象力和灵活的技巧 性。 在数值求解时，存在“维数障碍”。由于在大多数问题中，函数 瓴) ) 必须 以状态集合墨内格点上的数值来表示。放在电子计算机上计算时，每递推一段，都 必须把前一段算出的最优函数值在相应的状态集合上全部值存入内存中。在n 维情 况下，格点数为n i l 。可见当维数增大时，所需的内存量成指数倍增长。那么，若 计算机的内存量为1 2 8 m ，在这样的内存限制下，超过1 2 个变量的问题用通常的动 态规划方法是不可取的。为了克服“维数障碍，目前己找出了不少方法，如多项 式逼近法，逐次逼近法，状态微增法，拉格朗日乘子法等。它们对于不同范围内的 问题己经证明在一定程度上可以克服这个障碍，但是目前尚无一般的解决方法。 ( 2 ) 分支定界法 分支定界法【2 5 l ( b r a n c ha n db o u n dm e t h o d ) 在二十世纪六十年代初由l a n d ， d o i g 和d a k i n 等人提出，可用于解纯整数或混合的整数规划问题。其基本思路如 下：设有最大化的整数规划问题a ，与它相应的线性规划为问题b ，从解问题b 开 始，若其最优解不符合a 的整数条件，那么b 的最优目标函数必是a 的最优目标 函数z 的上界，记做；而a 的任意可行解的目标函数值将是z 的一个下界z 。分 支定界法就是将b 的可行域分成子区域( 称为分支) 的方法。逐步减小：和增大z ， 最终求到z 事。 由上一节的讨论，我们知道，所有的纯整数规划问题可以转化为等价的0 1 整 数规划问题，那么在解0 - 1 背包问题时，分支定界法所要定的界就被局限在 0 ，1 区间之内了。由于这个区域本身己经足够的小，分支定界法所要做的就是在o 和1 这两个数之间判断，这时，分支定界法的优势己经不存在了，它将变得跟穷举法一 样了。 当然，这并不是说分支定界法是没有价值的，它最大的用途是在解混合整数规 划问题，而且当纯整数规划问题没有转化为等价的0 - 1 整数规划问题的时候，它还 是相当有用的。具体的情况是这样的，因为分支定界法首先就要解整数规划问题a 的线性规划解，得到一个上界z ，这就相当于在将整数规划问题转化为0 - 1 整数 1 2 华北电力大学硕士学位论文 规划问题过程中添加若干物品，的副本这一步骤。 ( 3 ) 图论法 图论【2 5 】是应用十分广泛的运筹学分支，它广泛的应用在物理学、化学、控制论、 信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有 很多问题可以用图论的理论和方法来解决。 欧拉在1 7 3 6 年发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问 题。随着科学技术的发展以及电子计算机的出现与广泛应用，二十世纪五十年代， 图论的理论得到进一步发展。将庞大复杂的工程系统和管理问题用图描述，可以解 决很多工程设计和管理决策的最优化问题。例如，完成工程任务的时间最少，距离 最短，费用最省等。图论受到数学、工程技术及经营管理等各个方面越来越广泛的 重视。 图论中有许多基本的概念，如边，弧，无向图，有向图，树等等，还有许多现 有的方法，如破圈法，避圈法，d i j k s t r a 法等等。这种方法的效率并不高，而且对 于多维的情况也没有比较好的方法。所以图论的方法不适用于解大型背包问题或是 多维背包问题。 2 3 2 背包问题的近似算法简介 启发式算法【2 5 】( h e u r i s t i c a l g o r i t h m ) 是相对于最优算法提出的，它可以这样定 义：启发式算法是一种技术。这种技术使得在可接受的计算费用内去寻找最好的解， 但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同 最优解的近似程度。 在某些情况下，特别是实际问题中，最优算法的计算时间使人无法忍受或因问 题的难度使其计算时间随问题规模的增加以指数速度增加，此时只能通过启发式算 法求得问题的一个可行解。 早在4 0 年代末期，由于实际问题的需要，人们已提出一些解决实际问题的快 捷有效的启发式算法。随着7 0 年代算法复杂性理论的完善，我们不再强调一定要 求得到最优解，因此促使8 0 年代初兴起的现代优化算法在今天得到了巨大的发展。 启发式算法能够迅速发展是因为它有以下长处： 数学模型本身是实际问题的简化，或多或少会忽略一些因素，数据采集具 有不精确性，参数估计具有不准确性，以上因素可能使最优算法所得解比启发式算 法所得解产生更大误差； 有些难的组合优化问题可能还没有找到最优算法，即使存在，由算法复杂 1 3 华北电力大学硕士学位论文 性理论，得知他们的计算时间是无法接受或不实际的； 有些启发式算法可以用在最优算法中，如在分支定界算法中，可以用启发 式算法来估界； 简单易行，比较直观，易被使用者接受； 速度快，在适时管理中非常重要； 多数情况下，程序简单，因此易于修改。 虽说启发式算法有诸多好处，但它也有其短处，这些不足往往成为争论的焦点， 具体表现在： 不能保证求得最优解； 表现不稳定，启发式算法在统一问题的不同实例计算中会有不同的效果， 有些解很好，而有些解则很差，在实际应用中，这种不稳定性造成计算结果不可信； 算法的好坏依赖于实际问题、经验和设计者的技术，这一点很难总结规律， 同时使不同算法之间难以比较。 ( 1 ) 贪婪算法 贪婪算法属于一步式启发算法，即每采用一个贪婪准则便做出一个不可撤回的 决策。用贪婪算法求解背包问题的特点是每一步迭代选一个物品入包，直到无法再 装。该算法没有在两个可行解之间比较选择，算法结束时得到一个可行解。对于一 维背包问题，贪婪算法先将物品价值密度的值按降序排列，然后依次将物品放入背 包内，直至超出背包最大容纳量为止。用这种方法求解只能得到近似最优解，不能 保证一定能够得到最优解。但是由于贪婪算法的求解效率非常之高，不少专家学者 仍然寄希望于这种算法，力图改进它。1 9 7 7 年l o u l o u 等提出了一种新的贪婪算法， 这种算法可以适用于大型多维背包问题，在他的一篇论文中所举的最大的例子是 4 5 3 3 0 ，得到最优解的