基于遗传算法求解背包问题

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业 毕业设计（论文）基于遗传算法求解背包问题院 别专业名称班级学号学生姓名指导教师2012年6月15日基于遗传算法求解背包问题摘 要背包问题(Knapsack problem)是一种组合优化的NP完全问题,本文首先介绍了基本遗传算法的基本原理、特点及其基本实现技术，接着针对背包问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况。并且结合背包问题实例，给出了具体的编码方法，运行参数，群体大小，最大迭代次数，以及合适的遗传算子

2、。最后，简单说明了遗传算法在求解背包问题中的应用并对遗传算法解决背包问题的前景提出了展望。关键词：背包问题，遗传算法，遗传算子Genetic Algorithm for KP Author：Yang Dong Tutor：Kong ZhiAbstract KP (Knapsack Problem) is a combinatorial optimization of NP - complete problem. The primary knowledge, characteristics and the basic techniques of GA are introduced firstly

3、. The encoding model and genetic operators (including selection operation, crossover operation and mutation operation) solving KP are discussed secondly. Combined with examples of knapsack problem, we have given the specific encoding method, operating parameters, popsize, maxgeneration, and suitable

4、 genetic operator. At last, the application of genetic algorithm is simple presented, and the prospect for the future of genetic algorithm in solving KP has been given.Key Words: KP, genetic algorithm, genetic operators目 录TOC t 标题 1,2,标题 2,3,章标题,1 h 1绪论1.1 引言 现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况

5、之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规则生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。 遗传算法是中用于解决的搜索，是的一种。进化算法最初是借鉴了中的一些现象而发展起来的，这些现象包括、以及等。遗传算法通常实现方式为一种。对于一个最优化问题，一定数量的（称为个体）的抽象表示（称为）的向更好的解进化。传统上，解用表示（即0和1的串），但也可以用其他表示方法。进化从完全个体的种群开始，之后一

6、代一代发生。在每一代中，整个种群的被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。 背包问题(Knapsack problem)是一种组合优化的NP完全问题,对这个问题的求解前人己经研究出了不少的经典的方法,例如解析法，穷举法等，但是这些传统的优化方法存在一些缺点，如算法复杂度太高。与传统的优化算法相比，遗传算法具有以下优点:在每一时刻，GA同时在多个子空间内进行搜索，对初始值不作要求;基本不用搜索空间的知识或其他辅助信息，而仅用适应度来评估个体优劣;具有很强的鲁棒性。因此遗传算法在背包问题求解方面的应用研

7、究，对于构造合适的遗传算法框架、建立有效的遗传作以及有效地解决背包问题等有着多方面的重要意义5。1.2 背包问题概述1.2.1 背包问题的描述它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品总重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而引人注目。背包问题(Knapsack problem)是一种组合优化的。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总

8、重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。 1.2.1.1 01背包问题概述题目有N件物品和一个容量为V的背包。第i件物品的重量是ci，价值是wi。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即fiv表示前i件物品恰放

9、入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：fiv=maxfi-1v,fi-1v-ci+wi。可以压缩空间，fv=maxfv,fv-ci+wi这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为fi-1v；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-ci的背包中”，此时能获得的最大价值就是f

10、i-1v-ci再加上通过放入第i件物品获得的价值wi。注意fv有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是fN V，而是fN0.V的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项fv-1，这样就可以保证fN V就是最后的答案。至于为什么这样就可以，由你自己来体会了。优化空间复杂度以上方法的时间和空间复杂度均为O(N*V），其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(N）。先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1.N，每次算出来二维数组fi0.V的所有值。那么，如果只用一个数组f

11、 0.V，能不能保证第i次循环结束后fv中表示的就是我们定义的状态fiv呢？fiv是由fi-1v和f i-1v-ci两个子问题递推而来，能否保证在推fv时（也即在第i次主循环中推fv时）能够得到fv和fv -ci的值呢？事实上，这要求在每次主循环中我们以v=V.0的顺序推fv，这样才能保证推fv时fv-ci保存的是状态fi-1v-ci的值。伪代码如下：for i=1.Nfor v=V.0fv=maxfv,fv-ci+wi;其中的fv=maxfv,fv-ci一句恰就相当于我们的转移方程fiv=maxfi-1v,fi-1v-ci，因为现在的fv-ci就相当于原来的fi-1v-ci。如果将v的循环顺

12、序从上面的逆序改成顺序的话，那么则成了fiv由fiv-ci推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 总结0/1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0/1背包问题求解。1.2.1.2 完全背包问题题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物

13、品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件等很多种。如果仍然按照解01背包时的思路，令fi,v表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：fi,v=maxfi,v-vi+wi,fi-1,v。这跟01背包问题一样有O(N*V）个状态需要求解，但求解每个状态的时间则不是常数了，求解状态fv的时间是O(v/c），总的复杂度是超过O(VN）的。将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。简单有效的

14、优化完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c=wj，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高的j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。总结完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN）的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实

15、上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。 1.2.1.3 多重背包问题题目有N种物品和一个容量为V的背包。第i种物品最多有n件可用，每件体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。基本算法这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n+1种策略：取0件，取1件取 n件。令fv表示前i种物品恰放入一个容量为v的背包的最大权值，则：fv=maxfv-k*c+ k*w|0=k0的最大整数。例如，如果n为13，就将这种物品分成系数分别

16、为1,2,4,6的四件物品。分成的这几件物品的系数和为n，表明不可能取多于n件的第i种物品。另外这种方法也能保证对于0.n间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0.2k-1和2k.n两段来分别讨论得出，并不难，希望你自己思考尝试一下。这样就将第i种物品分成了O(log n）种物品，将原问题转化为了复杂度为O(V*log n）的01背包问题，是很大的改进。O(VN）的算法多重背包问题同样有O(VN）的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O的时间求解。小结这里我们看到了将一个算法的复杂度由O(V*n）改进到O(V*log n）的

17、过程，还知道了存在应用超出NOIP范围的知识的O(VN）算法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并用尽量简洁的程序来实现。1.2.1.4 混合三种背包问题问题如果将P01、P02、P03混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？01背包与完全背包的混合考虑到在P01和P02中最后给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN）

18、。伪代码如下：for i=1.Nif 第i件物品是01背包for v=V.0fv=maxfv,fv-c+w;else if 第i件物品是完全背包for v=0.Vfv=maxfv,fv-c+w;再加上多重背包 如果再加上有的物品最多可以取有限次，那么原则上也可以给出O(VN）的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用P03中将每个这类物品分成O(log n）个01背包的物品的方法也已经很优了。小结有人说，困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不论，但它在本讲中已经得到了充分的体现。本来01背包、完全背包、多重背包都不是什么难

19、题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实，领会三种基本背包问题的思想，就可以做到把困难的题目拆分成简单的题目来解决。 1.2.1.5 二维费用的背包问题问题二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a和b。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w。算法费用加了一维，只需状态也加一维即可。设fv表示前i件物品付出两种代价分别为v和u

20、时可获得的最大价值。状态转移方程就是：fiivu=maxfi-1vu,fi-1v-aiu-bi+wi。如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。物品总个数的限制有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设fvm表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f0.V0.M范围内寻

21、找答案。另外，如果要求“恰取M件物品”，则在f0.VM范围内寻找答案。小结事实上，当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。1.2.1.6 分组的背包问题问题有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。算法这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设fkv表示前k组物品花费费用v能取得的最大权值，则有fkv=maxfk-1v,fk-1v-c+w|物

22、品i属于第k组。使用一维数组的伪代码如下：for 所有的组k for v=V.0for 所有的i属于组k fv=maxfv,fv-c+w另外，显然可以对每组中的物品应用P02中“一个简单有效的优化”。小结分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题（例如P07），由分组的背包问题进一步可定义“”的概念，十分有利于解题。1.2.1.7 有依赖的背包问题简化的问题这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖

23、；另外，没有某件物品同时依赖多件物品。算法这个问题由NOIP2006的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2n+1个，为指数级。）考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实

24、际上对应于P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。再考虑P06中的一句话：可以对每组中的物品应用P02中“一个简单有效的优化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0.V-c所有这些值时相应的最大价值f0.V-c。那么这个主件及它的附件集合相当于V-c+1个物品的物品组，其中费用为c+k的物品的价值为

25、fk+w。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为 V-c+1个物品的物品组，就可以直接应用P06的算法解决问题了。更一般的问题更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01 背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其

26、附件集合所对应的附件组中各个费用的附件所对应的价值。事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。小结用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。1.2.1.8 泛化物品定义考虑这样一种物品，它并没有固定的费用和价值，而是它

27、的价值随着你分配给它的费用而变化。这就是泛化物品的概念。更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0.V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v）。这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h0.V，给它费用v，可得到价值hV。一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品，那么它可以看成这样一个函数，仅当v被c整除时有h(v)=v/c*w，其它函数值均为0。如果它是多重背包中重复次数最多为n的物品，那么它对应的泛化物品的函数有

28、h(v)=v/c*w仅当v被c整除且v/c=n，其它情况函数值均为0。一个物品组可以看作一个泛化物品h。对于一个0.V中的v，若物品组中不存在费用为v的的物品，则h(v)=0，否则h(v）为所有费用为v的物品的最大价值。P07中每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品。泛化物品的和如果面对两个泛化物品h和l，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于0.V的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v）。也即f(v)=maxh(k) +l(v-k)|0

29、=k=v。可以看到，f也是一个由泛化物品h和l决定的定义域为0.V的函数，也就是说，f是一个由泛化物品h和 l决定的泛化物品。由此可以定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足f(v)=maxh(k)+l(v-k)|0=k=v，则称f是h与l的和，即f=h+l。这个运算的时间复杂度是O(V2）。泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s，则答案就是s0.V中的最大值。1.2.1.9 背包问题的泛化物品一个背包问题中，可能会给出很多条

30、件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说，给定了所有条件以后，就可以对每个非负整数v求得：若背包容量为v，将物品装入背包可得到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品或者说问题所对应的一个定义域为非负整数的函数包含了关于问题本身的高度浓缩的信息。一般而言，求得这个泛化物品的一个子域（例如0.V）的值之后，就可以根据这个函数的取值得到背包问题的最终答案。小结综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物

31、品的和然后求之。1.2.1.10 关于本文本文讨论的是0-1背包问题，问题描述如下：指定给n件物品和一个背包，物品i 的重量是wi，其价值为vi，背包的容量为C，求从这n 件物品中选取一部分物品且对每件物品,或者选取,或者不选,每种物品只能装入背包一次,且要求满足放入背包中的物品总重量不超过背包容量。求出装入背包中物品价值总和最大的方案。注意：在本题中，所有的重量值均为整数。数学模型限制条件为：所求表达式为：其中，表示物品放入背包，表示物品未放入背包。1.2.2 研究背包问题的意义背包问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最大值。虽然它陈述起来很简单，但求解却很困难，并且已

32、经被证明是NP完全问题。至今尚未找到有效的求解方法，在理论上枚举法可以解这一问题，但是当n较大时，解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短，能满足实际问题精度要求的解，成为解决该问题的主要途径8。 背包问题的求解，一直以来倍受人们的关注。对于这样一个典型的、易于描述却难以处理的NP难题，有效地解决它在可计算理论上有着重要的理论价值。并且，背包问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。背包问题也可描述为决定性问题，相似问题经常出现在商业、投资组合优化、组合数学，计算复杂性理论、密码学和应用数学等领域中，因此具有广泛的实际应用领域。1.3 遗传算法1.3.

33、1 遗传算法概述遗传算法（GA）是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，也是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术。它是在1975年首次由美国密西根大学的D. J. Holland教授和他的同事们借鉴生物界自然选择和进化机制基础之上提出的。经过近30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息19。 遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的

34、目标函数对每个个体进行评价，给出一个适应度值。算法将根据适应度值对它进行寻优的过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的，它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的每一个点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Holland提出的模式定理(Schema Theorem)和隐式并行性得以解释。近年来，遗传算法从理论到实际都已经取得了许多重要成果。由于它具有良好的全局搜索能力，是目前解决各种优化问题的最有效的方法，已经成为研究热点。1.3.2 遗传算法的特点 从整体上来讲，遗传算法是进化算法中产生最早、影响最大

35、、应用也比较广泛的一个研究方向和领域，它不仅包含了进化算法的基本形式和全部优点，同时还具备若干独特的性能。161)在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有优化函数倒数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解过程；2)若遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约个模式,具有很高的并行性，因而具有显著的搜索效率；3)在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力；4

36、)对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普适性和易扩充性；5）遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用；遗传算法的这些特点使得它一经提出即在理论上引起了高度重视，能够应用于一些到目前为止人们知之甚少的困难问题领域，产生大量的成功案例。1.3.3 遗传算法的应用领域遗传算法的主要应用领域包括以下几个方面：函数优化问题。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用例子。很多人构造出了各种各样的复杂形式的测试函数来评价遗传算法的性能。

37、而且对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。组合优化问题。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于求解组合优化问题非常有效。遗传算法已经在求解旅行商问题、图形划分问题等方面得到成功的应用。 生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以求解，也会因简化太多而使求解结果与实际相差甚远

38、。由于可以采用字符编码，而且不必使用恰好的目标函数估值，遗传算法也成为解决复杂调度问题的有效工具。在单件生产车间调度、流水线生产车间调度、生产规划、任务分配、虚拟企业中的伙伴选择方面遗传算法都得到了有效的应用。自动控制。在自动控制领域有很多与优化相关的问题需要求解，而且这些优化问题通常要么是通过积分表达的，要么是写不出明确而严格的解析表达式。遗传算法在求解这类自动控制问题方面已显示出其独特的优点。例如，用遗传算法进行航空控制系统的优化、用遗传算法优化设计透平机械、设计模糊控制器等，都取得了较好的效果。机器学习。学习能力是高级自适应系统所应具备的特征之一。基于遗传算法的机器学习在很多方面都得到成

39、功应用。例如，遗传算法被用于学习模糊控制规则、确定模糊集的隶属函数、改进模糊系统的性能;被用来调整人工神经网络的连接权及网络拓扑优化。此外，遗传算法还被应用到反问题求解、机器人学习、生物计算、图像处理、人工智能以及遗传编程等领域。2遗传算法的基本原理 在遗传算法里，优化问题的解被称为个体，它表示为一个变量序列，叫做或者。染色体一般被表达为简单的字符串或数字串，不过也有其他的依赖于特殊问题的表示方法适用，这一过程称为编码。首先，算法生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，以提高初始种群的质量。在每一代中，每一个个体都被评价，并通过计算得到一个数值。种群中的个体被按照适应

40、度，适应度高的在前面。这里的“高”是相对于初始的种群的低适应度来说的。 下一步是产生下一代个体并组成种群。这个过程是通过选择和完成的，其中繁殖包括交配(crossover，在算法研究领域中我们称之为交叉操作）和突变(mutation)。选择则是根据新个体的适应度进行的，但同时并不意味着完全的以适应度高低作为导向，因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟。作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入交配过程。一般的遗传算法都

41、有一个交配概率（又称为交叉概率），范围一般是0.61，这个交配概率反映两个被选中的个体进行交配的。例如，交配概率为0.8，则80%的“夫妻”会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老”个体，而不交配的个体则保持不变。交配父母的染色体相互交换，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段并不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。再下一步是，通过突变产生新的“子”个体。一般遗传算法都有一个固定的（又称为变异概率），通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染

42、色体随机的突变，通常就是改变染色体的一个字节（0变到1，或者1变到0）。 经过这一系列的过程（选择、交配和突变），产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。一般终止条件有以下几种：进化次数限制；计算耗费的资源限制（例如计算时间、计算占用的内存等）；一个个体已经满足最优值的条件，即最优值已经找到；适应度已经达到饱和，继续进化不会产生适应度更好的个体；人为干预；以及以上两种或更

43、多种的组合。2.1 基本流程遗传算法需要涉及五大要素:编码、群体初始化、适应性函数的设定、遗传操作的设计和控制参数的设定。具体步骤如下：(l)编码，把问题的解转化成位串表示形式;(2)定义适应性函数;(3)确定遗传算法的各算子及参数，包括选择、交叉、变异方法，交叉率、变异率、群体容量、最大遗传代数等;(4)随机初始化群体;(5)计算群体中每一个染色体的适应值;(6)按照遗传操作形成下一代群体;从当前群体中由事先设定好的选择方法选出两个染色体;根据给定的交叉率，对选出的两个染色体进行交叉操作;根据给定的变异率，对每个染色体进行变异操作;重复、步，直到新的一代群体被创建出来;判断新产生的群体是否能

44、满足结束指标，如果满足，则算法结束，如果不满足，则返回步骤(6)。2.2 编码按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与遗传算法的染色体位串结构之间建立关系，即确定编码和解码运算。编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的编码空间相对应，编码的选择是影响算法性能与效率的重要因素。常用的编码方法有如下几种：二进制编码：二进制编码将问题空间的参数表示为基于字符集0,1构成的染色体位串，是最常用的一种编码方式。大字符集编码:除基于字符集0,1的二进制编码之外，可以结合实际问题的特征采用D进制数或字符集来表示长度为L的位串。序列编码：用排列法进行编码显

45、得更为自然、合理。实数编码：实数编码具精度高、大空间搜索的优点。树编码：树编码是一种非固定常用编码模式，其表示空间是开放的。在搜索过程中树可以自由生长，但是不便于形成更具有结构化和层次性的问题解，实际应用中往往可以加以限制。自适应编码：实现选择合适的固定编码方式对潜在的遗传算法用户来说是一个难题。事实上，提出合适的编码同解决问题本身一样困难。因此，许多用户认为既然要用遗传算法解决问题，为什么不让它同时调整编码呢?一些专家就采用了自适应编码11。2.3 适应度函数适应度评价是通过适应度函数对个体质量的一种测量，是进化过程中自然的唯一依据。因此适应度函数的选择至关重要，直接影响到遗传算法的收敛速度

46、以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。对目标函数值域的某种映射变换称为适应度的尺度变换。适应度函数的设计主要满足以下条件：单值、连续、非负、最大化:这个条件是容易理解和实现的。合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达成比较难以衡量。计算量小：适应度函数设计应尽可能简单，这样可以减小计算时间和空间上的复杂性，降低成本。通用性强：适应度函数对具体问题应尽可能具有通用性，最好无需使用者改变适应度函数中的参数。适应度函数的尺度变换有线性变换法、幕函数变换法、指数变换法10。2.4 遗传算子标准的遗传算子一般都包括选择、交叉和变异三种。它们构成了遗传算法的核

47、心，使得算法具有强大的搜索能力。2.4.1 选择算子选择操作就是用来确定如何从父代种群中按照某种方法选取哪些个体遗传到下一代种群的遗传运算。它是根据个体适应度函数值的大小正比于其被放入候选的概率的过程。在备选集中按照一定的选择概率进行操作，这个概率取决于种群中个体的适应度及其分布。其主要作用是避免了基因缺失，提高全局收敛性和计算效率。选择算子可看作是种群空间到父体空间的随机映射，它按照某种准则或概率分布从当前种群中以高的概率选取那些好的个体组成不同的父体以供生成新的个体。目前常用的选择策略有赌盘赌选择算子、排序选择算子、最优保存选择算子和锦标赛选择算子等8。在遗传算法中，目前常用的选择机制有以

48、下几种：适应度比例方法适应度比例方法是目前遗传算法中最基本也是最常用的选择方法。它也叫赌轮或蒙特卡罗选择。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度值为fi，则i被选择的概率psi为：psi=fi / fi （4-1） 显然，概率psi反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大，其被选择的概率就越高，反之则被选择的概率越低。最佳个体保存方法最佳个体保留进化策略的基本思想是当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。具体操作过程是：1)找出

49、当前群体中适应度最高的个体和适应度最低的个体。2)若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。3)用迄今为止的最好个体替换掉当前群体中的最差个体。期望值方法在赌轮选择机制中，当个体数不太多时，依据产生的随机数有可能会出现不正确地反映个体适应度的选择，即存在统计误差。也就是说，适应度高的个体也有可能被淘汰(当然，适应度低的个体也有可能被选择)，为克服这种误差，期望值方法用了如下思想。1)计算群体中每个个体在下一代生存的期望数目：M=fi /=fi / fi/n （4-2）2)若某个体被选中并要参与配对和交叉，则它在下一代

50、中的生存的期望值数目减去0.5；若不参与配对和交叉，则该个体的生存期望数目减去1。3)在2)的两种情况下，若一个个体的期望值小于0时，则该个体不参与选择。排序选择机制排序选择方法的主要着眼点是个体适应度之间的大小关系，对个体适应度是否取正值或负值以及个体适应度之间的数值差异程度并无特别要求。排序选择机制的主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个体被选中的概率。其具体操作过程是：1)对群体中的所有个体按其适应度大小进行降序排序。2)根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体。3)以各个个体所分配到的概率值作为其能够被遗传到下

51、一代的概率，基于这些概率值用比例选择的方法来产生下一代群体。是指在计算每个个体的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概率。2.4.2 交叉算子交叉操作是遗传算法中最主要的遗传操作。它是模仿自然界有性繁殖的基因重组过程，对两个父代个体进行基因操作，其作用在于把原有优良基因遗传到下一代种群中，并生成包含更复杂基因结构的新个体。交叉算子可看作是父体空间到个体空间的随机映射，它通常的作用方式是：随机地确定一个或多个分量位置为交叉点，由此将一对父体的两个个体分为有限个片断再以概率（称为交叉概率）交换相应片断得到新的个体。2.4.3 变异算子

52、在生物种群中总是存在着变异，变异指的是子代和父代之间具有某些不相似的现象，即因为存在着变异现象，所以子代和父代之间中总是不完全相同的。变异是生物进化过程中不可缺少的，它为生物的进化和发展创造了条件。在遗传算法中，变异是指父代染色体中的某些基因片，以相对较小的概率发生随机改变的操作过程。所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。在遗传算法中使用变异算子主要有以下两个目的：改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题的最优解。但仅使用交叉算子无法对

53、搜索空间的细节进行局部搜索。这时若再使用变异算子来调整个体编码串中的部分基因值，就可以从局部的角度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索能力。维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有基因值，从而可以改变个体编码串的结构，维持群体的多样性，这样就有利于防止出现早熟现象。2.5 参数控制在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组参数在初始阶段或种群进化过程中需要合理地选择和控制。主要包括种群规模n、交叉概率pc以及变异概率pm。2.5.1 群体规模大种群含有较多模式，为遗传算法提供了足够的模式采样容量，可以改进GA搜索的质量，防止早熟

54、前收敛。但大种群增加了个体适应性评价的计算量，从而使收敛速度降低。2.5.2 交叉概率 交叉概率pc控制着交叉算子的应用频率，在每一代新的种群中，需要对个体的染色体结构进行交叉操作。交叉概率越高，种群中新结构的引入越快，已获得的优良基因结构的丢失速度也相应升高。而交叉概率太低则可能导致搜索阻滞。一般pc=0.601.00。2.5.3 变异概率变异操作是保持种群多样性的有效手段，交叉结束后，交配池中的全部个体位串上的每位等位基因按概率随机改变，因此每代中大约发生n次变异。变异概率太小，可能使某些基因位过早丢失的信息无法恢复；而变异概率过高，则搜索将变成随机搜索。一般取pm=0.050.2。2.6

55、 算法结束条件控制终止代数是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前种群中的最优个体作为所求问题的最优解输出。由于遗传算法不同于传统的优化算法，它没有利用目标函数的梯度等信息，所以在遗传进化过程中，很难有明确的搜索终止准则。常用的办法是预先给定算法的终止进化代数。一般来说，预先给定算法的终止进化代数只能找到问题在给定时限内所能寻求的相对满意解，但不一定是问题的最优解或较高精度的近似解。为了获得较高精度的近似解，通常可依据种群适应度的稳定来适时调整终止进化代数的设置，或者在连续进化数代以后，如果解的适应度没有明显的改进，则终止进化过程。终止进

56、化代数一般的取值范围是100-1000。3求解实现背包问题的遗传算法3.1 0_1背包问题中染色体的表示用向量X来表示染色体，X = x1，x2，xn。，xi0,1，xi=1表示物品i装入了背包，xi =0表示物品i未装入背包。每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的适应度。程序中定义了这样的一个结构来表示染色体：typedef structint Weight;/染色体代表的物品的总重量int Fitness;/染色体代表的物品的价值（适应度）int GeneNUMG; /用元素取值于定义域0,1的数组表示染色体。GENE;3.2 算法求解01背包

57、问题时用到的参数POPSIZE：种群大小，即已知的可行解的个数。NUMG：染色体中基因的个数，即物品的总数。CAPACITY：背包的容量。MAXB：二进制表示的染色体换算之后的最大十进制整数。用于随机产生一个整数，进而转换作染色体。SIM：染色体之间的相似度阈值。当染色体之间的相似度达到阈值时，算法即停止运行。PC=1.0 ：交叉概率为100。PM=0.2 ：变异概率为20，变异可以保证种群的多样性，从而防止算法收敛于某个局部解。3.3 选择操作选择操作采用了赌轮选择（Roulette-wheel selection）的方法。函数selectIndex()中包含了选择染色体的具体过程。其流程图

58、如图1所示。图1 赌轮选择流程图程序中用一个Begin来代表当前赌轮上的指针的位置，End则用来使赌轮循环转动。用summaryBE表示当前赌轮上的指针转过的染色体的总价值。用summaryF表示当前全部染色体的价值总和。用randProb作为染色体选择的阈值。randProb为介于0,1之间的随机数。选择使summaryBE/summaryF 大于阈值randProb的染色体作为要选择的染色体。3.4 交叉操作单点交叉操作的简单方式是将被选择出的两个个体S1和S2作为父母个体，从0，1中产生一个随机数p，如果ppc，将两者的部分基因码值进行交换。假设如下两个父代：父代1: 1 14 2 13

59、 8 6 3 2 5 4 3 4 3 2 4父代2: 1 12 3 5 6 8 5 6 3 1 8 5 6 3 3随机选择一个交叉点为11，交叉后为：子代1: 1 14 2 13 8 6 3 2 5 4 8 5 6 3 3子代2: 1 12 3 5 6 8 5 6 3 1 3 4 3 2 4交叉过程的目的就是希望新的基因是由旧的基因中好的部分组合而成的，从而新的基因比原先的基因要好。当然把旧的种群中的一部分基因完全保留到下一代中去也是很有意义的。程序中采用了单点交叉的策略。如下程序代码所示：for(int j=0; jpartPos ;j+)nextGenomei.Genej = parent

60、GenomeFather.Genej;nextGenomei+POPSIZE/2.Genej = parentGenomeMother.Genej;for(;j=0.9 & pDiff=0.1)sameFlag = false;如果当前maxFitness最大的头结点满足if语句中的判断条件，则sameFlag置为真，即算法停止迭代的条件得到了满足。TraverseHashTable函数则用于遍历HASH表。算法终止的另一个条件是迭代的次数。程序中设定了算法的最大迭代次数为1000。3.9 仿真结果与测试试验中用到的物品的重量和价值分别存储于以下两个数组之中。int WeightNUMG=6,