（计算机软件与理论专业论文）对解决背包问题的遗传禁忌搜索算法的研究.pdf

摘要 摘要 解决背包问题是解决优化组合所面l 悔的问题之，也属于n p 难问题，在现实中有着 r “泛的应用背景，例如在解决大量的复杂组合优化问题进行算法设汁时，它律往会作为 一个子问题出现。由于在解决此类问题的规模较大时，要想得到最优的解是极其困难的， 因此，借鉴前人的研究成果，丌展对解决复杂组合优化问题的算法研究或改进是项卜 分有益的工作。 本文在对背包问题进行研究分析的基础上，对其常用算法b r u t ef o r c e 、动态舰划、 分支界定、贪婪算法、遗传算法进行了分析和试验对比，分析结果表明，动态规划算法 和遗传算法的性能较好。针对遗传算法易产生过早收敛等缺点，提出一种将局部搜索 能力强的禁忌搜索算法嵌入到遗传算法中的改进算法。通过采用个体的串行搜索方式， 设置禁忌表记录搜索轨迹并引导搜索方向，以防止“近亲繁殖”，保持种群的差异性， 克服“过早收敛”的缺陷。 同时，又针对遗传算法和禁总搜索算法相结合方法存在收敛速度较慢、搜索效率低 等问题，本文提出了一种采用贪婪算法融入禁忌串行搜索来实现的改进算法。实验结 果表明，该算法比传统的遗传算法与贪婪算法相结合的方法有收敛速度较快、搜索效 率较高等优点。 关键字：背包问题遗传算法禁忌搜索组合规划n _ p 难题 a b s i r a c l a b s t r a c t t h ek n a p s a c kp m b l e mj so n eo fc o m b i n a i o r i a lo p t i m i z a t i o np r o b l e m ，l ti sa l s oa nn p c o m p l e l e p r o b l e ma n da ss u c h 锄e x a c ts o l u f i o nf o ral a r g ei n p u ti sp r a c t i c a l l yj m p o s s i b l el oo b t a i n t h ek n 8 p s a c k p r o b l e mi su s e di nm a n yf i e l d s o nt h ed e s i g no fs o l v i n gt h ec o s m i c a l l yc o i n p l i c a i e dc o m b i n a t 町i a l o p i i m i z a t i o np r o b l e m ，t h ek n a p s a c kp r o b l e mo f t e na p p e a r sa ss u b 巾m b l e m s o “i sm e a n i n g f u lf o r o p t i m i z i n gl h ec o m b i n a t o a lo p t i m i z a t j o np r o b l e mt oi m p m v i n gl h ek n a p s a c kp m b l e mb yt h er e s u j t so f i h ef o r m e r i i l v e s l i g a t i o n 一 o n 【1 1 eb a s eo fr e s e a r c h i n go fh l a p s a c kp m b l e m ，t h i sp a p e rc o m p a r e sa n da n a l y s e ss e v e r a la l g o r i i h m w h i c ha r ea p p l i e dt oas i n 酉8p r o b l e m t h eo 1k n a p s a c kp m b l e m ，p r e s e n t sac o m p a r a “v es t u d yo f t h e b r u t ef o r c e ，d y n a j l l j cp m g r a m m i n 吕m e m o r yf u n c i i o n s ，b r a n c ha n db o u n d ，伊e e d y ，a n dg e n e t i ca i g o r i t h m s o u re x p e r i m e n i a lr e s u l t ss h o wt h a it h em o s tp m m i s i n g a p p m a c h e sa r ed y n a m i cp r o g r a m m j n ga n dg e n e i i c a l g o 订| h m s i na h u s j o nt og e e i i ca l g o 订t h m si ss u b j e c t e dl op r e m a t u r e ，w eu t i l i z et h em a i nf r a m eo fp a r a l l e s e a r c hs u p p l i e db yt h eg e e t i ca l g o r i l h ma n dt l l ei a b ua 1 9 0 r i t h m t sa d o p t si n d i v i d u a ls e r i a ls e a r c hm o d e s ot si sa b l et oo v e r c o m ep r e m a t u r ec o n v e r g e n c eo fg e n e i i ca l g o r i t h m s a t l h es a m et i m e ，】na l l u s i o nt oi h ec o n s i r i n g e n ts p e e do fg aa d d e dw i l ht a b us e a r c ha l g o r i t h ma r e s l o wa n dt h ej m p l e m e n te f f i c i e n c i e sa r el o w ，l b i sp 8 p c ri n t r o d u c e sg r e e d ya k o r i t h mt ot h ea b o v e a l g o r i t h i n t h ee x p e r i m e n tr e s u l t ss h o wt h a b ea 1 9 0 r i t h mh a v ea d v a n t 8 9 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 c n ts p e e d k e y w o r d s ：k n a p s a c kp r o b l e m ，g e n e t i c 越9 0 r i t h m ，t a b us e a r c h ，c o m b i n a t o r i a lo p t i m i z a t i o n p m b l e m ，n p ， 郑重声明 木人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽 窃、抄袭等违反学术道德、学术规范的侵杖行为，否则，本人愿意承担由 此产生的一切法律责任和法律后果。特此郑重声明。 学位论义作者( 签名) ： 硼、 矽秭年舌月f l j 第1 章绪论 第l 章绪论 背包问题( k n a p s a c kpr ( ) b l e m ) 是典型的组合优化问题之_ ，工厂早的卜料问题，管 理中的资源分配、资金预算、投资决策、项目选择、材料切割、货物装载等均i u 建模为 背包问题，并且还常常作为其他问题的子问题加以研究。背包问题是运筹学中的一个典 型的n p 难问题i “，n p 难解问题类，意味着p n p ，无法找到多项式时间算法求得该类问 题最优解。因此我们把研究的重点转向寻找能在较短时间( 多项式时间) 内得到接近寸j 最优解的算法。大多数背包问题有拟多项式的时间算法，这意味着若系数则模有所界定， 在可接受的时问内能够得到最优解。背包问题的应用背景促使人们对浚问题汁算方法进 行了深入研究，背包问题的特有计算性质又使其应用领域不断得到拓展。 它的数学模型实际上是一个o l 规划问题。o 1 背包问题是指有不同价值、不同重 量的物品n 件，求从这n 件物品中选取一部分物品且对每一物晶，要么选，要么刁i 选， 满足被选物品的总重量不超过背包指定的限制重量且达到被选物品的价值总和最大的 问题。如果所有物品的重量之和小于背包的容量，则问题极其简单，所得利益也就足所 有物品的价值之和，而实际问题往往是背包的容量小于物品的重量之和1 4 】o 用形式化方法 可对该问题描述为： 设肘为背包的容量，个物品的重量组成一向量 ，其价值组成另 一向量 ，m o ，u o ，c 。 o ( 1 sf n ) 。要找出另 一n 元向量 ，一 o ，1 1 ，l s ish ，l 表示选，o 表示不选该物晶。 由此，o i 背包问题要求：肘甜c ，且满足以下两个约束条件： ( 1 ) q 葺m ( 2 ) 薯 o ，1 1sf 以 也就是晚对o l 背包问题，可以通过求出变量- ，x ：，x 。的一个决策序列束得到 它的解，而对变量置的决策就是决定它是取o 值还是取1 值。 背包问题可以衍生出一系列与之相关的优化问题，如有限背包问题( 物体可具有相 同价值和重量但数量是有限的) ，无限背包问题( 具有相同价值和重量的物体数量可以是 第l 章绪论 无限的) ，多背包问题( 将物体装入多个容量不同的背包) 等。本文中所指背包问题如无 特殊说明，均指简单o l 背包刚题。 背包问题在实践中有广泛的应用背景。许多简单结构的有机组合构成了复杂结构， 埘简单问题的深入探索也伎复杂问题的解决变得相对容易。在设计解决大量的复杂组合 优化问题算法时，背包问题往往作为子问题出现。背包问题的算法改进，对复杂组合优 化问题算法的改良是十分有益的。 背包问题属于组合最优化问题。严格意义上的最优解求取非常困难，研究高速近似 的算法是一个重要的发展方向。对全局优化问题，目前存在确定性和非确定性两类方法。 前者以b r f a n i n 的下降轨线法、l e v y 的隧道法和r g e 的填充函数法为代表。泼类方法虽 然收敛快、计算效率高，但算法复杂，求得全局极值的概率不大。非确定性方法以 m o n t e c a r 】( ) 。随机试验法、h a r t m a n 的多始点法、s o b s 和w e t s 的结合梯度信息的搜索方 法、模拟退火法( ( s i 舢1 a t e da n n e a l 一i n g ) 等为代表。该类方法对目标函数要求低、容 易实现、稳定性好，但收敛速度慢、求得全局极值的概率较低。对于 包问题，已有的 求解方法可分为精确算法( 如枚举法，动态规划法，分支界定法，陶论法等指数级方法) 和近似算法( 如贪心算法，蚂蚁算法，遗传算法等) 两大类【9 】o d a n t z i gi 3 j 在五十年代中期首先进行了丌创性的研究，利用贪心算法求得了个理 想解，得出了o 1 背包问题最优解的上界。在这之后：十几年里背包问题研究没有取得 太大进展，该上界也未得到改进。直到一九七四年， i o r o w it z 和s a l m j f 4 j 首先利用分支定 界技术设计出一有效算法解答背包问题，并提出了背包问题的可分性，指明了解答该问 题的一条新途径。之后，m a r t e l l o 和t o t h 5 谰整数约束和分支定界技术第一个改进了 d a n t z i g 上界。1 9 8 0 年，b a l a s 和z e m e l c 6 首先提出了解答背包问题的“核”( c ( ) r e ) 思想， 使该1 u j 题的研究有了较大进展。在九十年代末p i s i n g e r 利用平循技术【7 l 和“核膨胀”【8 】 思想设计的算法，该算法结合了动态规划技术，使解答背包问题的算法有了实质进展。 在进入j ：十j 世纪的九十年代以后，生物仿生技术和i n t e r n e t 技术的飞速发展，使得模拟 生物物理规律的各种并行近似算法不断涌现，遗传算法已经在0 1 背包问题e 得到较好 的应用，蚂蚁算法、粒子群算法等仿生算法也在各种组合优化问题中得到了应用。背包 问题的特有计算性质又使其应用领域不断得到拓展。r a l p h m e r k l e 和d i f f i om a r t i n h e i l m a n1 1 2 j 基于背包问题的难解性，设计出了第一个公钥密码体制，开创了密码学的新 方向。下面先对几种常用的传统算法进行讨论。 2 第2 章解决背包问题的常几j 算法 第2 章解决背包问题的常用算法 2 1 解背包问题的常用算法 2 1 1 蛮力算法( b r i i t ef 0 r c e ) 蛮力算法是解决问题的直接算法，通常是基于问题的状态和所涉及剑的概念定义。 如果有n 个物品被选择，那么将会2 。组合方案。算法详见附录二。 算法复杂度分析 再。【荔。+ 篆，1 掣 玎 = z 1 + + 1 ( nt i m e s ) + 1 + + l ，( nt i m e s ) 】 = ( 2 n ) + 【l + 1 + 1 + 1 】( 2 “t i m e s ) = o ( 2 t 1 8 2 “1 = 0 ( n 2 2 “) 此算法的时间复杂度为o ( n 2 0 ) ，因为此算法的复杂度呈指数增 ：= ，所以只能用来 解决小规模的背包问题，另外算法需要两个一维数组的存储空问( a i 】和b e s t c h o i c e 【】) 。 2 1 2 动态规划算法 动态规划法是解决多阶段决策过程最优化的一种数学方法 1 6 l 。1 9 5 1 年美国数学家 贝尔曼等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联 系单阶段问题，然后逐个加以解决，从而创建了动态规划的方法。它的特点是解决多阶 段、离散性问题。它采用最优原则( p r i n c j p l eo fo p t i m a l i t y ) 束建立用于计算最优解的递归 式。所谓最优原则g p 不管前面的策略如何，此后的决策必须是基于当前状态f 由e 一次 决策产生1 的最优决策。由于对于有些问题的某些递归式来说并不一定能保证最优原则， 因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方 法。在得到最优解的递归式之后，需要执行回溯( ( t r a c e b a c k ) 以构造最优解。 采用动态规划方法，可以很高效的解决许多用分支界定法或贪婪法无法解决的问 题。但是，动态规划方法也存在着不足之处：到目前为止，还没有一个统一的标准模型 可供应用。由于实际问题不同，其动态规划模型也就不同。虽然理论上说町以把某些静 3 帮2 章解决背包问题的常用算法 态舰划的问题转化为动态规划模型来求解，但这种转化有时将变得十分困难，需要f - 富 的想象力和灵活的技巧性。 在数值求解时，存在“维数障碍”。山于在大多数问题中，函数 ( & ) 必 须以状态集合s 。内格点上的数值来表示。放在电子计算机上计算时，每递推一段，都必 须把前一段算尚的最优值函数在相应的状态集合上全部值存入内存中。在h 维情况卜- ， 格点数为m ”。可见当维数增大时，所需的内存量成指数倍增氏。那么，若计算机的内 存量为1 2 8 m ，在这样的内存限制下，超过1 2 个变量的问题用通常的动态规划方法是不 可取的。为了克服“维数障碍”，目前已找出了不少方法，如多项式逼近法，逐次逼近 法，状态微增法，拉格朗品乘子法等1 1 3 1 4 ，15 1 。它们对于不同范围内的问题已经证明在一 定程度卜可以克服这个障碍。但是目前尚无一般的解决方法。 动态规划算法求解背包问题过程描述 假定m 0 ，且两个正整数数组分别为： 和 ，期望 找到c ，t 最大且u 薯sm 的子集为t 1 ，2 ，n ) 。采用上述动态规划思想，解决 背包问题的求解过程可描述如下： 步骤：将问题分解为小的子问题 构造一个二维数组v f 0 n ，0 m 】 1 s i s n 且0 量w 蔓m v 【i ，w 】用来存储权值至少为w 且值最大的子集t 1 ，2 ，n ) 即：v 【i ，w 】_ m a x 荟。，汀 1 ，2 ”i ) ，善”，划) 计算出所有满足条件的此二维数组的值，则v 【n ，w 】就包含解决问题的解决 方案。 步骤二：根据子问题的解递归定义最优解的值 设置初始状态集合： v 【o ，w 】- 0 当o s w s m ，没有任何项目时 v 【i ，w 】一o 。当w o ， 非法 递归步： v 【i ，w 】= m a x ( v 【i 一1 ，w 】，c f + ( v 【i 1 ，w u 】) 圭中1s i n ，o s w m 【5 1 。 4 第2 章解决背包问题的常用算法 式中：v i _ 1 ，w 】为上一轮中重量为w 时所求得的价值最大值；c i + ( v 【i - 1 ，w u 】表不： 选取u 时的价值为t ，此时允许的最大的重量为w ，w q 是还剩下的可承重量。 v 【i ，w 】的取值为v 【i - 1 ，w 】和c f + ( v 【i - 1 ，w - 叫中的较大值。如果有i 种物品可以选择， 而此时所能承受的最大重量为w 时，只有两种选择：1 14 i 选新加入的第i 种物品。此 时只有i 一1 种物品，最大承受重量为w 的最大价值为v 【i 一1 ，w 】。 2 ) 选择新加入的第i 种物品。第i 种物品的重量为u 的价值为q ，现所能承受的最大重量为w q ； 而i 1 种 物品还可以选择，此时的最大价值为v 【i _ 1 ，w - u 】；因此价值最大值为( c l + v 【i 一1 ，w q 】) 。 步骤i ：自底向上进行计算v 【i ，w 】： 瘕i ：v 【o ，w 】= 0 当o s w s m ； 自底向上计算：使用公式v 【i w 】= m a ) 【( v 【i - 1 ，w ，c j + ( v 【i - 1 ，w u 】 算法的具体实现描述流程见附录三。 复杂度分析 算法的时问复杂度是0 ( n m ) ，在空间存储上，动态规划算法需要个曲维数组， 数组行为背包个数，列为背包重量，此算法不需要任何附加的结构，所以町能是解背包 问题的最佳方法之一。 例1 ：某人准备外出旅游，背包中有a ，b ，c ，d 四件物品如下表所示，假设背包的最 大承重为3 3 k g ，求获取最大价值的选择方案。 物品a b cd 总数 重量( k ) 1 81 4844 4 价值( y u a n ) 1 51 2743 8 用动态规划分方法求解例1 需要计算1 4 个函数，存储1 3 个值，而且当n 超过2 4 ，m 超过2 时，1 2 8 m 内存就不够用了f 1 2 8 m = 2 2 4 i n t ) 。 应该指出的是，动态规划方法虽存在许多不足之处，但应用还是比较广泛的。许多 专家学者结合实际己经成功的解决了许多实际问题。 2 1 3 分支界定法 分支界定法( b r a n c ha n db o u n dm e t h o d ) 在本世纪六十年代初由m d d o i g 和d a k i n 等 人提出，可用于解纯整数或混合的整数规划问题。其基本思路如下：设有最大化的整数 规划问题a ，与它相应的线性规划为问题b ，从解问题b 开始，若其最优解不符合a 的整数条件，那么b 的最优目标函数必是a 的最优目标函数z + 的上界，记做；：而a s 第2 帝解决背包问题的常用算法 的任意可行解的目标函数值将是z t 的一个下界墨。分支界定法就是将b 的可行域分成子 区域f 称为分支1 的方法。逐步减小z 和增大z ，最终求到z + 。 我们知道，所有的纯整数规划问题可以转化为等价的o 一1 整数规划问题，那么在解 0 l 背包问题时，分支界定法所要定的界就被局限【0 ，1 】区间之内了。由于这个区域本身 己经足够的小，分支界定法所要做的就是在0 和1 这两个数之间判断，这时分支界定法 的优势己经不存在了，它将变得跟穷举法一样了。 当然，这并不是况分支界定法是没有价值的，它最大的用途足在解混合整数规划问 题，而且当纯整数规划问题没有转化为等价的0 1 整数规划问题的时候，它还是相当有 用的。具体的情况是这样的，因为分支界定法首先就要解整数规划问题a 的线性规划解， 得到一个上界z ，这就相当于在将整数规划问题转化为0 1 整数规划问题过程中添加若 ，r 物品f 的副本这一步骤。 考察用分支界定法来解例1 ，我们发现需要进行1 8 次判断，解1 8 次线性规划方程， 共搜索了1 8 个非整数解，其中整数解有两个。这样，我们通过实例再次证明了用分支 界定法解背包问题时效率并不高，有时甚至还不如穷举法。 最坏情况下，分枝界定法将产生所有的中间状态和叶子，因此，这个树将足完全的， 有2 “1 1 个节点，也就是说将有指数的复杂度，但一般来说不会产牛所有可能的节点， 所以仍然优于b n - c ef o r c e 算法。此算法的存储空间取决于优先队列的长度。算法详见附 录四。 2 1 4 贪婪算法 贪婪算法属于一步式启发算法，即每采用个贪婪准则便做出一个不可撤回的决 策。用贪婪算法求解背包问题的特点是每一步迭代选一个物品入包，直到无法再装。该 算法没有在两个可行解之间比较选择，算法结束时得到一个可行解。 解决0 1 背包问题的可能的3 种策略： ( 1 ) 从余下的物品中选择价值最大的个体，这种方法使背包的价值尽可能的增大： ( 2 ) 从余下的物品中选择最轻的个体装入背包，使背包尽可能的多装物品： ( 3 ) 选择单位价值最大的物品装入背包。 上述三种策略中第三种认为最合理，下面的实验中采用第三种贪婪算法求解背包| u j 题，算法描述见附录五。 6 第2 章解决背包问题的常用算浊 贪婪算法的复杂度为d f o g m ，在空间上，此算法仅需要一个一维数组来存储解决 方案。 刑十一维背包问题，贪婪算法先将物品价值密度的值按降序排列，然后依次将物品 放入背包内，直至超出背包最大容纳量为止。用这种方法求解只能得到近似最优解，不 能保证一定能够得到最优解。 例2 m i n 厂= 7 0 z l + 2 0 x 2 + 3 9 鼍+ 3 7 x 4 + 7 鼍+ 5 工6 + 6 工7 s 1 3 7 + 1 0 2 2 + 1 9 屯+ 4 + 7 砖+ 3 + 6 兰5 0 若用贪婪算法求解得到的解为( 1 ，1 ，0 ，o ，1 ，1 ，0 ) ，= 1 0 2 ，而最优解为( 1 ，0 ，0 ，1 ，o ，o ，0 ) ， ，= 1 0 7 0 但足由于贪婪算法的求解效率非常之高，不少专家学者仍然寄希望于这种算法，力 图改进它。1 9 7 7 年r i c h a r dl o u l o u 等提出了一种新的贪婪算法，这种算法可以适用于大 型多维背包问题，在他的一篇论文中所举的最大的例子是4 5 3 3 0 ，得到最优解的概率 为2 0 ，但是这种方法需要较高的数学技巧和一定的经验。 2 1 5 遗传算法 ( 1 ) 随机产生n 个染色体的一代种群； ( 2 ) 计算所有个体的适应度； ( 3 ) 产生新的种群： a 选择当前代中随机选择两个染色体； b 交叉对两个选择的染色体执行交叉操作： c 变异对获得的染色体执行变异操作； ( 4 ) 重组：用新种群替代当前种群； ( 5 ) 判断：判断是否满足结束条件，如果满足，结束。不满足，返回当前代最优解并回 到( 2 ) 。 遗传算法属于改进式启发算法【。改进算法的迭代过程是从一个可行解转移到另一 个可行解，通常通过两个解的比较而选择好的解，进而作为新的起点进行新的迭代，直 到满足一定的要求为止。因此也可成为是迭代算法。实践证明，遗传算法作为现代最优 化的手段，它应用于大规模、多峰多态函数、含离散变量等情况下的全局最优化问题是 合适的，在求解速度和质量上远超过常规方法，因而是一种高速近似算法。对于遗传算 7 第2 章解决背包问题的常用算法 法更详细的介绍请见下一章。 在下面的实验巾，取种群规模为2 5 0 ，交叉率o 8 5 ，变异率0 0 1 ，采用轮盘赌选择。 终止条什：种群中9 0 的染色体具有相同的适应度，或进化代数大于给定的值( 5 0 0 ) 。 2 2 几种实验的实验比较 为了测试不同的算法，我们产生随机的两组整数分别代表重量和价值，执行两种类 型的测试，第种是保持背包容量不变( 为5 0 ) ，提高背包中物品的数量；第二种为保 持背包中所放物品的数量不变( 为5 0 0 ) ，提高背包的容量。 测试一：保持背包容量为5 0 ，增加背包中的物品。 表2 1 背包容量为5 0 ，物品数量为1 0 的实验结果 物品数量包含物品总价值最大价值 b r u c ef o r c e3 ，6 ，8 ，9 ，1 0 1 5 2 1 5 2 贪婪算法 3 ，4 ，6 ，7 ，8 ，91 4 21 5 2 分枝界定算法 3 ，6 ，8 ，9 ，1 01 5 21 5 2 动态舰划算法3 ，6 ，8 ，9 ，1 0 1 5 21 5 2 | 遗传算法 3 ，6 ，8 ，9 ，1 01 5 21 5 2 表2 2 背包容量为5 0 ，物品数量为2 5 的实验结果 物品数量包含物品 总价值 最大价值 b r u c ef o f c e6 ，7 ，9 ，1 3 ，1 7 ，1 9 ，2 0 ，2 12 9 82 9 8 贪婪算法 4 ，6 ，7 ，9 ，1 3 ，1 9 ，2 0 ，2 12 8 42 9 8 分枝界定算法 6 ，7 ，9 ，1 3 ，1 7 ，1 9 ，2 0 ，2 12 9 82 9 8 f 动态规划算法 6 ，7 ，9 ，1 3 ，1 7 ，1 9 ，2 0 ，2 12 9 82 9 8 i 遗传算法 6 ，7 ，9 ，1 3 ，1 7 ，1 9 ，2 0 ，2 l2 9 82 9 8 能执行b n l t ef o r c e 算法的物品的最大数量为2 5 ，从以上两个表可以看出，分枝界定， 动念规划，遗传算法产生的解和b r u t en d r c e 算法产生的最优解相同。接f 柬我们从总价 值，操作次数和空间存储三个方面束考虑贪婪算法，分支界定，动态规划，和遗传算法 的解决方案。 第2 章解决背包问题的常用算法 表2 3 背包释量为5 0 ，物品数量为1 0 0 的实验结果 物品数量总价值总重量 迭代次数内存消耗 贪婪算法 1 3 6 l 5 01 3 9 81 0 0 分枝界定算法 1 3 8 84 94 5 9 82 1 5 6 动态规划算法 1 3 8 84 95 1 0 0 5 1 0 0 遗传算法 1 3 6 84 95 6 0 81 5 0 0 0 表2 4 背包容量为5 0 物品数量为3 0 0 的实验结果 物品数量 总价值总重量迭代次数内存消耗 贪婪算法 5 5 2 35 03 0 0 分枝界定算法 5 6 5 85 06 3 4 6 1 2 5 7 8 动态规划算法 5 6 5 85 01 5 3 0 01 5 3 0 0 遗传算法 5 6 5 85 01 7 6 8 84 5 0 0 0 表2 5 背包容量为5 0 ，物品数量为5 0 0 的实验结果 物品数量总价值总重量迭代次数内存消耗 贪婪算法 1 5 3 4 74 95 0 0 分枝界定算法 1 5 4 6 65 02 0 0 9 2 04 8 5 6 0 动态规划算法 1 5 4 6 65 02 5 5 0 02 5 0 0 0 遗传算法 1 5 4 6 65 02 9 4 4 17 5 0 0 0 表2 6 背包容量为5 0 物品数量为7 5 0 的实验结果 物品数量总价值总重量迭代次数内存消耗 贪婪算法 2 5 8 0 0 4 8 7 5 0 分枝界定算法 2 6 5 0 45 01 3 8 8 2 9 92 2 3 5 9 2 动态规划算法 2 6 5 0 45 03 8 2 5 03 8 2 5 0 遗传算法 2 6 4 5 64 94 4 1 3 2 1 1 2 5 0 0 9 第2 章解决背包问题的常用算法 表2 7 背包容量为5 0 ，物品数量为1 0 0 0 的实验结果 l 物品数量 总价值总重量迭代次数内存消耗 i 贪婪算法 4 3 9 8 54 81 0 0 0 分枝界定算法 n an an an a 动态规划算法 4 4 5 4 95 05 1 0 0 05 1 0 0 0 遗传算法 4 4 5 1 24 95 8 8 2 31 5 0 0 0 0 从表2 3 剑表2 7 中可以看出，我们能够执行分枝界定算法的最大物品数量为7 5 0 个，因此，尽管分枝界定法和b n | t ef o r c e 算法一样，时间复杂度呈指数增长，但分枝界 定法可以支持更多的输入。另外，可以看出，动态规划算法，分枝界定算法和遗传算法 获取的总价值要优于贪婪算法。所以进一步从迭代的次数和内存的消耗量两个方面分析 动态规划，分枝界定和遗传算法。 内存清耗暇) ； f f f ； ； p 一一 ，。，一“? ，p 。 ，矿 、 m 。二t = = ：肾。it 1 0 绻5 0 3 s 7 7 5 09 1 0 0 0 钧品藏量 图2 1 分支界定动态规划，遗传算法的内存消耗比较 1 0 瓣帅帅蚰蚰帅蚰帅蚰蛐吣o 泐薹|枷啪黜m舌i啪m咖啪啪蝴m 第2 章解决背包问题的常用算法 b o e 0 0 自s ； g d 0 8 5 ( j 。8 8 0 0 7 0 f # l l “ f ； l m 。 ， 一，r 一p 一 l，1 l0 71 。 | o i一，i 一1 一llii 1 0 2 55 0 o o3 0 0s o o7 0 07 5 0 9 0 01 0 0 物晶疑置 图2 2 分支界定，动态规划，遗传算法的迭代次数的比较 从图2 1 和浏2 2 中可以看出，随着物品数量的增加，分支界定算法的内存消耗和 迭代次数都比动态规划和遗传算法增加显著，而到物品数大于7 5 0 时，分支界定法就无 法找到解了。从图2 1 中可以看出动态规划比遗传算法需要较少的内存，从图2 2 中【r j 以看出，随着物品数量的增加，动态规划算法和遗传算法的迭代次数具有几乎相同的增 长速率。由此也许可以得出结论：动态规划算法要优于遗传算法。然而我们还忽略了 个问题，动态的规划算法的复杂度取决于物品的数量和背包的容量，而遗传算法的复杂 度取决丁物品的数量和种群的规模，因此如果增加背包的容量，动态规划算法所需要的 基本操作数量和内存容量将会随着增长，而遗传算法将基本保持不变( 从表2 8 2 1 3 【q 以看出) 。到此为止，我们得到的求解背包问题的两个较好的算法是动态规划算法和遗 传算法，下面就这两个算法进行测试二的比较。 测试二：保持物品数量5 0 0 不变，增加背包的容量( 5 0 5 0 0 ) 。 表2 8 物品数量5 0 0 ，背包容量为5 0 物品数量总价值操作数量内存消耗 动态规划算法 1 5 4 6 62 5 5 0 02 5 0 0 0 遗传算法 1 5 4 6 62 9 4 4 17 5 0 0 0 1 l 懈鼢蝌僦辫嗽鼢嗽辩撇黜蝴寄 弛繇胁鹅驰转此雅雏嚣钟俘旧s 第2 章解决背包问题的常用算法 表2 ，9 物品数量5 0 0 ，背包容最为1 0 0 物品数量总价值操作数量内存消耗 动态规划算法2 2 4 0 85 0 5 0 0 5 0 5 0 0 遗传算法 2 2 3 1 32 9 4 5 67 5 0 0 0 表2 1 0 物品数量5 0 0 ，背包容量为2 0 0 物品数量 总价值操作数量内存消耗 动态规划算法 3 1 7 9 31 0 0 5 0 0l 0 0 5 0 0 遗传算法3 1 7 7 22 9 5 3 57 5 0 0 0 表2 1 l 物品数量5 0 0 背包容量为3 0 0 物品数量总价值操作数量内存消耗 动态舰划算法 3 9 2 4 5 1 5 0 5 0 01 5 0 5 0 0 遗传算法 3 9 2 3 12 9 5 4 27 5 0 0 0 表2 1 2 物鼎数量5 0 0 ，背包容量为4 0 0 物品数量总价值 操作数量内存消耗 动态规划算法 4 5 7 7 5 2 0 0 5 0 02 0 0 5 0 0 遗传算法 4 5 7 6 42 9 5 7 47 5 0 0 0 表2 1 3 物品数量5 0 0 ，背包容量为5 0 0 l 物品数量总价值操作数量内存消耗 ；动态规划算法 5 1 4 1 3 2 5 0 5 0 02 5 0 5 0 0 遗传算法 5 1 3 9 22 9 5 7 67 5 0 0 0 根据上面表格的试验结果构造动态规划算法和遗传算法的内存消耗比较图 笫2 帝斛决背包问题的常用算法 内择潲糍0 b 3 0 0 0 0 0 2 5 0 0 0 0 2 0 0 0 0 0 1 5 0 0 0 0 1 0 0 0 0 0 5 0 d o o o 7 一 。，”4 il s ot 2 3 本o 背包褪f f 克) 图2 3 动态规划算法和遗传算法的内存消耗比较 根据上面表格的试验结果构造动态规划算法和遗传算法的迭代次数比较图： 8 0 0 0 0 0 2 5 0 0 0 0 2 0 0 0 0 0 1 5 0 0 0 0 i d 0 0 0 0 5 0 0 0 0 o ，7 一“ 自_ 矿 6 01 0 臻 oo嬲05 首包窖量开3 劫 图2 4 动态规划算法和遗传算法的迭代次数比较 结论：只要背包容量小于种群规模，动态规划算法就优于遗传算法，然而一旦背包 容量大于种群规模，动态规划算法的操作数量和内存消耗都远远大于遗传算法。通过 b r u t ef o r c e ，贪婪算法，动态规划算法，分枝界定法和遗传算法的比较研究可知，解决 背包问题的最佳算法为动态规划算法和遗传算法，而这两种算法的选择取决于背包的容 量和种群的规模。 第3 章遗传算法求解背包问题 第3 章遗传算法求解背包问题 3 1 遗传算法简介 进入2 0 世纪以来，在速度和影响范围方面遗传学的发展只有电子学和汁算机科学 能与之相比。将计算机技术与生物技术相结合产生了各种边缘学科。遗传算法是将生物 技术引入最优化方法而得到的，它是2 0 世纪出现的最令人感兴趣的算法之。遗传算 法( 以及普遍意义上的进化算法1 出现在2 0 世纪6 0 年代早期，最初起源于坩生物系统进 行的计算机模拟研究，并在计算机科学的确定性和非确定性算法之问占据了一席之位。 本质上，遗传算法具有如同其它确定性算法同样的特性，用户町以决定重复次数和结束 条件。它模拟达尔文的自然选择，还有变异，把“适应性”f f 如适用于个体的公式所 决定的那样) 作为主要因素选择生存繁衍和变异的个体。 早在2 0 世纪5 0 年代就有将进化原理应用于计算机科学的努力，但缺乏种普遍 的编码方法，只能依赖于变异而非交配产生新的基因结构。5 0 年代术到6 0 年代初，受 一些生物学家用计算机对生物系统进行模拟的启发，h o l l a n d 丌始应用模拟遗传算子研 究适应性。7 0 年代，由美国密执安大学的h o l l a n d 教授及其学生们刨造出的一种基于生 物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术。存b a 9 1 e y l 9 6 7 年关于自适应下棋程序的论文中，他应用遗传算法搜索下棋游戏评价函数的参数集，并 首次提出了遗传算法这一术语。1 9 7 5 年h o l l a n d 出版了遗传算法历史上的经典著作自 然和人丁系统中的适应性，系统阐述了遗传算法的基本理论和方法，并提出了模式定 理( s c h e m a t at h e o r e m ) ，证明在遗传算子选择、交叉和变异的作用卜，具有低阶、短定 义距以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长，这罩1 1 勺模式 是某一类字符串，其某些位置有相似性。同年，d e j o n g 完成了他的博士论文遗传自 适应系统的行为分析，将h o l l a n d 的模式理论与他的计算试验结合起来，进一步完善了 选择、交叉和变异操作，提出了一些新的遗传操作技术。 进入8 0 年代后，遗传算法得到了迅速发展，不仅理论研究十分活跃，而且在越来 越多的应用领域中得到应用。1 9 8 3 年，h o l l a n d 的学生g o l d b e r g 将遗传算法应用丁管道 煤气系统的优化，很好地解决了这一非常复杂的问题。1 9 8 9 年，g o l d b e r g 出版了搜索、 优化和机器学习中的遗传算法一书，这本可能是遗传算法领域被引用次数最多的书为 1 4 第3 章遗传算法求解背包问题 这一领域莫定了坚实的科学基础。8 0 年代中期，a x e l r o d 和f o r r e s t 合作，采用遗传算法 研究了博奕论中的一个经典问题囚徒困境。在机器学习方面，h o l l a n d 自提出遗传 算法的基本理论后就致力于研究分类器系统( c l a s s i f i e rs y s t e m ) ，h o l l a n d 希望系统能将外 界刺激进行分类，然后送到需要的地方去，因此命名为分类器系统，这里的c l a s s i f i e r 是指一个二进制串，代表一类情况。分类器系统将某一条件是否为真与串的某一位相对 应，从而将产生式系统中的规则编码为二进制串，这样就可以应用遗传算法来进行演化， 同时引入了基于经济学原理的信用分配机制桶队( b u c k e t b r i g a d e ) 算法柬确定规则的 相对强度。h o l i a n d 和s a n t a f e 的t h u f 等人合作，用分类器系统模拟了一些经济现象， 得到了满意的结果。经过多年发展，遗传算法己成为非线性优化和系统辨识的一个有效 工具，被广泛应用于机器人系统、神经网络学习过程、模式识别、图像处理、工、k 优化 控制、自适应控制、社会科学等方面，在解决n p 完全性问题方面取得了很好的效果。 从遗传筛法的来源一自然界现象看，生物演化的目的并非取得某一限制条件下的某些参 数的最优，而是适应环境。生物进化的途径多种多样，没有哪一种是最优的，但是，成 功的生物必然是适应其环境和环境内的其它生物的，对于环境的演化和其它生物的进化 ( 它自己也在改变着环境，人类更是i j 仃所未有地改变着环境白能够适应新的变化，继续 生存。从这一角度看，虽然目前工程实践上遗传算法的主要应用是用于优化，但遗传算 法的真f 威力却远大于此。鉴于遗传算法和生物演化现象的紧密关系，人工生命和复杂 性科学的研究与遗传算法有着极其密切的联系【2 2 1 。 遗传算法己经在背包问题的求解上取得了大量成果【2 n 2 “。运用简单遗传算法求解 背包问题时，若问题的规模不大也能够得到最优解或近似最优解。 3 2 遗传算法的基本要素 遗传算法的基本操作包括编码、产生初始群体、适应度计算、选择、交叉、变异等 。 3 2 1 遗传编码 按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示 与遗传算法的染色体位串结构之间建立关系，即确定编码和解码运算。编码就是将问题 的解用一种码来表示，从而将问题的状态空间与g a 的码空间相对应，这很大程度上依 赖于问题的性质，并将影响遗传操作的设计。由于g a 的优化过程不是直接作用在问题 参数本身，而是在一定编码机制对应的码空间上进行的，因此编码的选择是影响算法性 第3 章遗传算法求解背包问题 能与效率的重要因素。函数优化中，不同的码长和码制，对问题的精度与效率有很大影 响。二进制编码将问题的解用一个二进制串来表示，十进制编码将问题的解用一个i 进 制串柬表示，显然码长将影响算法的精度，而且算法将付出较大的存储量。实数编码将 问题的解用一个实数来表示，解决了编码对算法精度和存储量的影响，也便利于优化中 引入问题的相关信息，它在高维复杂优化空间中得到广泛应用。对于给定的优化问题， 由g a 个体的表现型集合所组成的空间称为问题空间，由g a 基冈型个体所组成的空间 称为g a 编码空间。遗传算子在g a 编码空间中对位串个体进行操作。 理论上而占，编码应该适合要解决的问题，而不是简单的描述问题。对于背包问题 的数学模型，最直接的编码是采用二进制编码，用一组o 一1 决策变量表示h 位二进制字 符串，作为一个个体的遗传基因表示。在这样的表示方法中，若第，位基因码为1 时， 则第，个物体被选择；若第j 位基因码为0 时，则第个物体不被选择。 3 2 2 遗传算子 标准遗传算法的操作算子一般包括选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 三种基本形式，它们构成了遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗 传过程中发生的繁殖、杂交和突变现象的主要载体。遗传算法利用遗传算子产生新代 群体米实现群体进化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过 程的基本工具。文献【2 3 2 7 】分别讨论了遗传算子对收敛性所产生的影响，这种分析对于更 好的了解各遗传算子的特性与作用是大有裨益的。 ( - ) 选择算予 在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多的机会 遗传到下一代，而对生存环境适应程度较低的物种遗传到下一代的机会就相对较少。模 仿这个过程，遗传算法使用选择算子( 或称复制算子r e p r o d u c t i o n0 p e m t o r ) 来对群体巾的 个体进行