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

毕业设计〔论文〕基于遗传算法求解背包问题院别专业名称班级学号学生姓名指导教师2023年6月15日基于遗传算法求解背包问题摘要背包问题(Knapsackproblem)是一种组合优化的NP完全问题,本文首先介绍了根本遗传算法的根本原理、特点及其根本实现技术，接着针对背包问题，论述了遗传算法在编码表示和遗传算子〔包括选择算子、交叉算子变异算子这三种算子〕等方面的应用情况。并且结合背包问题实例，给出了具体的编码方法，运行参数，群体大小，最大迭代次数，以及适宜的遗传算子。最后，简单说明了遗传算法在求解背包问题中的应用并对遗传算法解决背包问题的前景提出了展望。关键词：背包问题，遗传算法，遗传算子GeneticAlgorithmforKPAuthor：YangDongTutor：KongZhiAbstractKP(KnapsackProblem)isacombinatorialoptimizationofNP-completeproblem.Theprimaryknowledge,characteristicsandthebasictechniquesofGAareintroducedfirstly.Theencodingmodelandgeneticoperators(includingselectionoperation,crossoveroperationandmutationoperation)solvingKParediscussedsecondly.Combinedwithexamplesofknapsackproblem,wehavegiventhespecificencodingmethod,operatingparameters,popsize,maxgeneration,andsuitablegeneticoperator.Atlast,theapplicationofgeneticalgorithmissimplepresented,andtheprospectforthefutureofgeneticalgorithminsolvingKPhasbeengiven.KeyWords:KP,geneticalgorithm,geneticoperators目录TOC\t"标题1,2,标题2,3,章标题,1"\h304331绪论1117081.1引言1261081.2背包问题概述1296861.2.1背包问题的描述2323251.2.2研究背包问题的意义9310541.3遗传算法10220811.3.1遗传算法概述10167521.3.2遗传算法的特点10300131.3.3遗传算法的应用领域11183032遗传算法的根本原理13242382.1根本流程14108652.2编码1486122.3适应度函数15167092.4遗传算子15216732.4.1选择算子16322102.4.2交叉算子17270792.4.3变异算子17315632.5参数控制18254782.5.1群体规模18157882.5.2交叉概率18315262.5.3变异概率1945142.6算法结束条件控制1924033求解实现背包问题的遗传算法20145153.10_1背包问题中染色体的表示20202393.2算法求解01背包问题时用到的参数20111883.3选择操作20233763.4交叉操作21199103.5精英策略22115063.6变异操作23318653.7代际更新23216843.8算法的终止2335243.9仿真结果与测试2468503.9.1不同交叉概率下所的测试结果2548453.9.2极端数据对结果的影响27138043.9.3仿真结果总结3012192结论3119166致谢323777参考文献3313876附录341绪论1.1引言现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规那么生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。遗传算法是计算数学中用于解决最正确化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而开展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解〔称为个体〕的抽象表示〔称为染色体〕的种群向更好的解进化。传统上，解用二进制表示〔即0和1的串〕，但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体〔基于它们的适应度〕，通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。背包问题(Knapsackproblem)是一种组合优化的NP完全问题,对这个问题的求解前人己经研究出了不少的经典的方法,例如解析法，穷举法等，但是这些传统的优化方法存在一些缺点，如算法复杂度太高。与传统的优化算法相比，遗传算法具有以下优点:在每一时刻，GA同时在多个子空间内进行搜索，对初始值不作要求;根本不用搜索空间的知识或其他辅助信息，而仅用适应度来评估个体优劣;具有很强的鲁棒性。因此遗传算法在背包问题求解方面的应用研究，对于构造适宜的遗传算法框架、建立有效的遗传作以及有效地解决背包问题等有着多方面的重要意义[5]。1.2背包问题概述1.2.1背包问题的描述它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一局部物品并将它们放到背包中来加密消息。背包中的物品总重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而引人注目。背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最适宜的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能到达V？它是在1978年由Merkel和Hellman提出的。1.2.1.101背包问题概述题目有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。根本思路这是最根底的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。那么其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]}这个方程非常重要，根本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中〞这个子问题，假设只考虑第i件物品的策略〔放或不放〕，那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中〞，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中〞，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰〞字去掉，在转移方程中就要再参加一项f[v-1]，这样就可以保证f[N][V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。优化空间复杂度以上方法的时间和空间复杂度均为O(N*V〕，其中时间复杂度根本已经不能再优化了，但空间复杂度却可以优化到O(N〕。先考虑上面讲的根本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[v]时〔也即在第i次主循环中推f[v]时〕能够得到f[v]和f[v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：fori=1..Nforv=V..0f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么那么成了f[i][v]由f[i][v-c[i]]推知，与此题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。总结0/1背包问题是最根本的背包问题，它包含了背包问题中设计状态、方程的最根本思想，另外，别的类型的背包问题往往也可以转换成0/1背包问题求解。1.2.1.2完全背包问题题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。根本思路这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。这跟01背包问题一样有O(N*V〕个状态需要求解，但求解每个状态的时间那么不是常数了，求解状态f[v]的时间是O(v/c〕，总的复杂度是超过O(VN〕的。将01背包问题的根本思路加以改良，得到了这样一个清晰的方法。这说明01背包问题的方程确实是很重要，可以推及其它类型的背包问题。但我们还是试图改良这个复杂度。简单有效的优化完全背包问题有一个很简单有效的优化，是这样的：假设两件物品i、j满足c<=c[j]且w>=w[j]，那么将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高的j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。总结完全背包问题也是一个相当根底的背包问题，它有两个状态转移方程，分别在“根本思路〞以及“O(VN〕的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。1.2.1.3多重背包问题题目有N种物品和一个容量为V的背包。第i种物品最多有n件可用，每件体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。根本算法这题目和完全背包问题很类似。根本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n+1种策略：取0件，取1件……取n件。令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值，那么：f[v]=max{f[v-k*c]+k*w|0<=k<=n}。复杂度是O(V*∑n〕。转化为01背包问题另一种好想好写的基该方法是转化为01背包求解：把第i种物品换成n件01背包中的物品，那么得到了物品数为∑n的01背包问题，直接求解，复杂度仍然是O(V*∑n〕。但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成假设干件物品，使得原问题中第i种物品可取的每种策略——取0..n件——均能等价于取假设干件代换以后的物品。另外，取超过n件的策略必不能出现。方法是：将第i种物品分成假设干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1〕，n-2^k+1，且k是满足n-2^k+1>0的最大整数。例如，如果n为13，就将这种物品分成系数分别为1,2,4,6的四件物品。分成的这几件物品的系数和为n，说明不可能取多于n件的第i种物品。另外这种方法也能保证对于0..n间的每一个整数，均可以用假设干个系数的和表示，这个证明可以分0..2^k-1和2^k..n两段来分别讨论得出，并不难，希望你自己思考尝试一下。这样就将第i种物品分成了O(logn〕种物品，将原问题转化为了复杂度为O(V*∑logn〕的01背包问题，是很大的改良。O(VN〕的算法多重背包问题同样有O(VN〕的算法。这个算法基于根本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O⑴的时间求解。小结这里我们看到了将一个算法的复杂度由O(V*∑n〕改良到O(V*∑logn〕的过程，还知道了存在应用超出NOIP范围的知识的O(VN〕算法。希望你特别注意“拆分物品〞的思想和方法，自己证明一下它的正确性，并用尽量简洁的程序来实现。1.2.1.4混合三种背包问题问题如果将P01、P02、P03混合起来。也就是说，有的物品只可以取一次〔01背包〕，有的物品可以取无限次〔完全背包〕，有的物品可以取的次数有一个上限〔多重背包〕。应该怎么求解呢？01背包与完全背包的混合考虑到在P01和P02中最后给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN〕。伪代码如下：fori=1..Nif第i件物品是01背包forv=V..0f[v]=max{f[v],f[v-c]+w};elseif第i件物品是完全背包forv=0..Vf[v]=max{f[v],f[v-c]+w};再加上多重背包如果再加上有的物品最多可以取有限次，那么原那么上也可以给出O(VN〕的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用P03中将每个这类物品分成O(logn〕个01背包的物品的方法也已经很优了。小结有人说，困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不管，但它在本讲中已经得到了充分的表达。本来01背包、完全背包、多重背包都不是什么难题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要根底扎实，领会三种根本背包问题的思想，就可以做到把困难的题目拆分成简单的题目来解决。

1.2.1.5二维费用的背包问题问题二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值〔背包容量〕。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a和b。两种代价可付出的最大值〔两种背包容量〕分别为V和U。物品的价值为w。算法费用加了一维，只需状态也加一维即可。设f[v]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：fi[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。物品总个数的限制有时，“二维费用〞的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数〞的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多项选择m件时可得到的最大价值，那么根据物品的类型〔01、完全、多重〕用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。另外，如果要求“恰取M件物品〞，那么在f[0..V][M]范围内寻找答案。小结事实上，当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比拟通用的方法。1.2.1.6分组的背包问题问题有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。这些物品被划分为假设干组，每组中的物品互相冲突，最多项选择一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。算法这个问题变成了每组物品有假设干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，那么有f[k][v]=max{f[k-1][v],f[k-1][v-c]+w|物品i属于第k组}。使用一维数组的伪代码如下：for所有的组kforv=V..0for所有的i属于组kf[v]=max{f[v],f[v-c]+w}另外，显然可以对每组中的物品应用P02中“一个简单有效的优化〞。小结分组的背包问题将彼此互斥的假设干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题〔例如P07〕，由分组的背包问题进一步可定义“泛化物品〞的概念，十分有利于解题。1.2.1.7有依赖的背包问题简化的问题这种背包问题的物品间存在某种“依赖〞的关系。也就是说，i依赖于j，表示假设选物品i，那么必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。算法这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件〞，依赖于某主件的物品称为“附件〞。由这个问题的简化条件可知所有的物品由假设干主件和依赖于每个主件的一个附件集合组成。按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。〔事实上，设有n个附件，那么策略有2^n+1个，为指数级。〕考虑到所有这些策略都是互斥的〔也就是说，你只能选择一种策略〕，所以一个主件和它的附件集合实际上对应于P06中的一个物品组，每个选择了主件又选择了假设干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。再考虑P06中的一句话：可以对每组中的物品应用P02中“一个简单有效的优化〞。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合〞先进行一次01背包，得到费用依次为0..V-c所有这些值时相应的最大价值f'[0..V-c]。那么这个主件及它的附件集合相当于V-c+1个物品的物品组，其中费用为c+k的物品的价值为f'[k]+w。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为V-c+1个物品的物品组，就可以直接应用P06的算法解决问题了。更一般的问题更一般的问题是：依赖关系以图论中“森林〞的形式给出〔森林即多叉树的集合〕，也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品〔只有一个主件〕且不出现循环依赖。解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品了。假设这个附件也有附件集合，那么它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品〞的思想。看完P08后，你会发现这个“依赖关系树〞每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。小结用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。

1.2.1.8泛化物品定义考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0..V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v〕。这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0..V]，给它费用v，可得到价值h[V]。一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品，那么它可以看成这样一个函数，仅当v被c整除时有h(v)=v/c*w，其它函数值均为0。如果它是多重背包中重复次数最多为n的物品，那么它对应的泛化物品的函数有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)=max{h(k)+l(v-k)|0<=k<=v}。可以看到，f也是一个由泛化物品h和l决定的定义域为0..V的函数，也就是说，f是一个由泛化物品h和l决定的泛化物品。由此可以定义泛化物品的和：h、l都是泛化物品，假设泛化物品f满足f(v)=max{h(k)+l(v-k)|0<=k<=v}，那么称f是h与l的和，即f=h+l。这个运算的时间复杂度是O(V^2〕。泛化物品的定义说明：在一个背包问题中，假设将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s，那么答案就是s[0..V]中的最大值。1.2.1.9背包问题的泛化物品一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说，给定了所有条件以后，就可以对每个非负整数v求得：假设背包容量为v，将物品装入背包可得到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品——或者说问题所对应的一个定义域为非负整数的函数——包含了关于问题本身的高度浓缩的信息。一般而言，求得这个泛化物品的一个子域〔例如0..V〕的值之后，就可以根据这个函数的取值得到背包问题的最终答案。小结综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为假设干泛化物品的和然后求之。1.2.1.10关于本文本文讨论的是0-1背包问题，问题描述如下：指定给n件物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为C，求从这n件物品中选取一局部物品且对每件物品,或者选取,或者不选,每种物品只能装入背包一次,且要求满足放入背包中的物品总重量不超过背包容量。求出装入背包中物品价值总和最大的方案。注意：在此题中，所有的重量值均为整数。数学模型限制条件为：所求表达式为：其中，表示物品放入背包，表示物品未放入背包。1.2.2研究背包问题的意义背包问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最大值。虽然它陈述起来很简单，但求解却很困难，并且已经被证明是NP完全问题。至今尚未找到有效的求解方法，在理论上枚举法可以解这一问题，但是当n较大时，解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短，能满足实际问题精度要求的解，成为解决该问题的主要途径[8]。背包问题的求解，一直以来倍受人们的关注。对于这样一个典型的、易于描述却难以处理的NP难题，有效地解决它在可计算理论上有着重要的理论价值。并且，背包问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。背包问题也可描述为决定性问题，相似问题经常出现在商业、投资组合优化、组合数学，计算复杂性理论、密码学和应用数学等领域中，因此具有广泛的实际应用领域。1.3遗传算法1.3.1遗传算法概述遗传算法〔GA〕是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，也是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术。它是在1975年首次由美国密西根大学的D.J.Holland教授和他的同事们借鉴生物界自然选择和进化机制根底之上提出的。经过近30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息[19]。遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应度值。算法将根据适应度值对它进行寻优的过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的，它的搜索能力由选择算子和杂交算子决定，变异算子那么保证了算法能够搜索到问题空间的每一个点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Holland提出的模式定理(SchemaTheorem)和隐式并行性得以解释。近年来，遗传算法从理论到实际都已经取得了许多重要成果。由于它具有良好的全局搜索能力，是目前解决各种优化问题的最有效的方法，已经成为研究热点。1.3.2遗传算法的特点从整体上来讲，遗传算法是进化算法中产生最早、影响最大、应用也比拟广泛的一个研究方向和领域，它不仅包含了进化算法的根本形式和全部优点，同时还具备假设干独特的性能。[16]1)在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有优化函数倒数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解过程；2)假设遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约个模式,具有很高的并行性，因而具有显著的搜索效率；3)在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力；4)对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者参加特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普适性和易扩充性；5〕遗传算法的根本思想简单，运行方式和实现步骤标准，便于具体使用；遗传算法的这些特点使得它一经提出即在理论上引起了高度重视，能够应用于一些到目前为止人们知之甚少的困难问题领域，产生大量的成功案例。1.3.3遗传算法的应用领域遗传算法的主要应用领域包括以下几个方面：函数优化问题。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用例子。很多人构造出了各种各样的复杂形式的测试函数来评价遗传算法的性能。而且对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。组合优化问题。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最正确工具之一。实践证明，遗传算法对于求解组合优化问题非常有效。遗传算法已经在求解旅行商问题、图形划分问题等方面得到成功的应用。生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以求解，也会因简化太多而使求解结果与实际相差甚远。由于可以采用字符编码，而且不必使用恰好的目标函数估值，遗传算法也成为解决复杂调度问题的有效工具。在单件生产车间调度、流水线生产车间调度、生产规划、任务分配、虚拟企业中的伙伴选择方面遗传算法都得到了有效的应用。自动控制。在自动控制领域有很多与优化相关的问题需要求解，而且这些优化问题通常要么是通过积分表达的，要么是写不出明确而严格的解析表达式。遗传算法在求解这类自动控制问题方面已显示出其独特的优点。例如，用遗传算法进行航空控制系统的优化、用遗传算法优化设计透平机械、设计模糊控制器等，都取得了较好的效果。机器学习。学习能力是高级自适应系统所应具备的特征之一。基于遗传算法的机器学习在很多方面都得到成功应用。例如，遗传算法被用于学习模糊控制规那么、确定模糊集的隶属函数、改良模糊系统的性能;被用来调整人工神经网络的连接权及网络拓扑优化。此外，遗传算法还被应用到反问题求解、机器人学习、生物计算、图像处理、人工智能以及遗传编程等领域。2遗传算法的根本原理在遗传算法里，优化问题的解被称为个体，它表示为一个变量序列，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的依赖于特殊问题的表示方法适用，这一过程称为编码。首先，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，以提高初始种群的质量。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，适应度高的在前面。这里的“高〞是相对于初始的种群的低适应度来说的。下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成的，其中繁殖包括交配(crossover，在算法研究领域中我们称之为交叉操作〕和突变(mutation)。选择那么是根据新个体的适应度进行的，但同时并不意味着完全的以适应度上下作为导向，因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟。作为折中，遗传算法依据原那么：适应度越高，被选择的时机越高，而适应度低的，被选择的时机就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入交配过程。一般的遗传算法都有一个交配概率〔又称为交叉概率〕，范围一般是0.6~1，这个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为0.8，那么80%的“夫妻〞会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老〞个体，而不交配的个体那么保持不变。交配父母的染色体相互交换，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体那么正好相反。不过这里的半段并不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。再下一步是突变，通过突变产生新的“子〞个体。一般遗传算法都有一个固定的突变常数〔又称为变异概率〕，通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一个字节〔0变到1，或者1变到0〕。经过这一系列的过程〔选择、交配和突变〕，产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向开展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。一般终止条件有以下几种：进化次数限制；计算消耗的资源限制〔例如计算时间、计算占用的内存等〕；一个个体已经满足最优值的条件，即最优值已经找到；适应度已经到达饱和，继续进化不会产生适应度更好的个体；人为干预；以及以上两种或更多种的组合。2.1根本流程遗传算法需要涉及五大要素:编码、群体初始化、适应性函数的设定、遗传操作的设计和控制参数的设定。具体步骤如下：(l)编码，把问题的解转化成位串表示形式;(2)定义适应性函数;(3)确定遗传算法的各算子及参数，包括选择、交叉、变异方法，交叉率、变异率、群体容量、最大遗传代数等;(4)随机初始化群体;(5)计算群体中每一个染色体的适应值;(6)按照遗传操作形成下一代群体;①从当前群体中由事先设定好的选择方法选出两个染色体;②根据给定的交叉率，对选出的两个染色体进行交叉操作;③根据给定的变异率，对每个染色体进行变异操作;④重复①、②、③步，直到新的一代群体被创立出来;判断新产生的群体是否能满足结束指标，如果满足，那么算法结束，如果不满足，那么返回步骤(6)。2.2编码按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与遗传算法的染色体位串结构之间建立关系，即确定编码和解码运算。编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的编码空间相对应，编码的选择是影响算法性能与效率的重要因素。常用的编码方法有如下几种：①二进制编码：二进制编码将问题空间的参数表示为基于字符集{0,1}构成的染色体位串，是最常用的一种编码方式。②大字符集编码:除基于字符集{0,1}的二进制编码之外，可以结合实际问题的特征采用D进制数或字符集来表示长度为L的位串。③序列编码：用排列法进行编码显得更为自然、合理。④实数编码：实数编码具精度高、大空间搜索的优点。⑤树编码：树编码是一种非固定常用编码模式，其表示空间是开放的。在搜索过程中树可以自由生长，但是不便于形成更具有结构化和层次性的问题解，实际应用中往往可以加以限制。⑥自适应编码：实现选择适宜的固定编码方式对潜在的遗传算法用户来说是一个难题。事实上，提出适宜的编码同解决问题本身一样困难。因此，许多用户认为既然要用遗传算法解决问题，为什么不让它同时调整编码呢?一些专家就采用了自适应编码[11]。2.3适应度函数适应度评价是通过适应度函数对个体质量的一种测量，是进化过程中自然的唯一依据。因此适应度函数的选择至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。对目标函数值域的某种映射变换称为适应度的尺度变换。适应度函数的设计主要满足以下条件：①单值、连续、非负、最大化:这个条件是容易理解和实现的。②合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达成比拟难以衡量。③计算量小：适应度函数设计应尽可能简单，这样可以减小计算时间和空间上的复杂性，降低本钱。④通用性强：适应度函数对具体问题应尽可能具有通用性，最好无需使用者改变适应度函数中的参数。适应度函数的尺度变换有线性变换法、幕函数变换法、指数变换法[10]。2.4遗传算子标准的遗传算子一般都包括选择、交叉和变异三种。它们构成了遗传算法的核心，使得算法具有强大的搜索能力。2.4.1选择算子选择操作就是用来确定如何从父代种群中按照某种方法选取哪些个体遗传到下一代种群的遗传运算。它是根据个体适应度函数值的大小正比于其被放入候选的概率的过程。在备选集中按照一定的选择概率进行操作，这个概率取决于种群中个体的适应度及其分布。其主要作用是防止了基因缺失，提高全局收敛性和计算效率。选择算子可看作是种群空间到父体空间的随机映射，它按照某种准那么或概率分布从当前种群中以高的概率选取那些好的个体组成不同的父体以供生成新的个体。目前常用的选择策略有赌盘赌选择算子、排序选择算子、最优保存选择算子和锦标赛选择算子等[8]。在遗传算法中，目前常用的选择机制有以下几种：①适应度比例方法适应度比例方法是目前遗传算法中最根本也是最常用的选择方法。它也叫赌轮或蒙特卡罗选择。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度值为fi，那么i被选择的概率psi为：psi=fi/∑fi〔4-1〕显然，概率psi反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大，其被选择的概率就越高，反之那么被选择的概率越低。②最正确个体保存方法最正确个体保存进化策略的根本思想是当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。具体操作过程是：1)找出当前群体中适应度最高的个体和适应度最低的个体。2)假设当前群体中最正确个体的适应度比总的迄今为止的最好个体的适应度还要高，那么以当前群体中的最正确个体作为新的迄今为止的最好个体。3)用迄今为止的最好个体替换掉当前群体中的最差个体。③期望值方法在赌轮选择机制中，当个体数不太多时，依据产生的随机数有可能会出现不正确地反映个体适应度的选择，即存在统计误差。也就是说，适应度高的个体也有可能被淘汰(当然，适应度低的个体也有可能被选择)，为克服这种误差，期望值方法用了如下思想。1)计算群体中每个个体在下一代生存的期望数目：M=fi/=fi/∑fi/n〔4-2〕2)假设某个体被选中并要参与配对和交叉，那么它在下一代中的生存的期望值数目减去0.5；假设不参与配对和交叉，那么该个体的生存期望数目减去1。3)在2)的两种情况下，假设一个个体的期望值小于0时，那么该个体不参与选择。④排序选择机制排序选择方法的主要着眼点是个体适应度之间的大小关系，对个体适应度是否取正值或负值以及个体适应度之间的数值差异程度并无特别要求。排序选择机制的主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个体被选中的概率。其具体操作过程是：1)对群体中的所有个体按其适应度大小进行降序排序。2)根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体。3)以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于这些概率值用比例选择的方法来产生下一代群体。是指在计算每个个体的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概率。2.4.2交叉算子交叉操作是遗传算法中最主要的遗传操作。它是模仿自然界有性繁殖的基因重组过程，对两个父代个体进行基因操作，其作用在于把原有优良基因遗传到下一代种群中，并生成包含更复杂基因结构的新个体。交叉算子可看作是父体空间到个体空间的随机映射，它通常的作用方式是：随机地确定一个或多个分量位置为交叉点，由此将一对父体的两个个体分为有限个片断再以概率〔称为交叉概率〕交换相应片断得到新的个体。2.4.3变异算子在生物种群中总是存在着变异，变异指的是子代和父代之间具有某些不相似的现象，即因为存在着变异现象，所以子代和父代之间中总是不完全相同的。变异是生物进化过程中不可缺少的，它为生物的进化和开展创造了条件。在遗传算法中，变异是指父代染色体中的某些基因片，以相对较小的概率发生随机改变的操作过程。所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。在遗传算法中使用变异算子主要有以下两个目的：①改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题的最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这时假设再使用变异算子来调整个体编码串中的局部基因值，就可以从局部的角度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索能力。②维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有基因值，从而可以改变个体编码串的结构，维持群体的多样性，这样就有利于防止出现早熟现象。2.5参数控制在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组参数在初始阶段或种群进化过程中需要合理地选择和控制。主要包括种群规模n、交叉概率pc以及变异概率pm。2.5.1群体规模大种群含有较多模式，为遗传算法提供了足够的模式采样容量，可以改良GA搜索的质量，防止早熟前收敛。但大种群增加了个体适应性评价的计算量，从而使收敛速度降低。2.5.2交叉概率交叉概率pc控制着交叉算子的应用频率，在每一代新的种群中，需要对个体的染色体结构进行交叉操作。交叉概率越高，种群中新结构的引入越快，已获得的优良基因结构的丧失速度也相应升高。而交叉概率太低那么可能导致搜索阻滞。一般pc=0.60—1.00。2.5.3变异概率变异操作是保持种群多样性的有效手段，交叉结束后，交配池中的全部个体位串上的每位等位基因按概率随机改变，因此每代中大约发生n次变异。变异概率太小，可能使某些基因位过早丧失的信息无法恢复；而变异概率过高，那么搜索将变成随机搜索。一般取pm=0.05—0.2。2.6算法结束条件控制终止代数是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前种群中的最优个体作为所求问题的最优解输出。由于遗传算法不同于传统的优化算法，它没有利用目标函数的梯度等信息，所以在遗传进化过程中，很难有明确的搜索终止准那么。常用的方法是预先给定算法的终止进化代数。一般来说，预先给定算法的终止进化代数只能找到问题在给定时限内所能寻求的相对满意解，但不一定是问题的最优解或较高精度的近似解。为了获得较高精度的近似解，通常可依据种群适应度的稳定来适时调整终止进化代数的设置，或者在连续进化数代以后，如果解的适应度没有明显的改良，那么终止进化过程。终止进化代数一般的取值范围是100-1000。3求解实现背包问题的遗传算法3.10_1背包问题中染色体的表示用向量X来表示染色体，X=｛x1，x2，……，xn｝。，xi∈｛0,1｝，xi=1表示物品i装入了背包，xi=0表示物品i未装入背包。每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的适应度。程序中定义了这样的一个结构来表示染色体：typedefstruct{ intWeight; //染色体代表的物品的总重量 intFitness; //染色体代表的物品的价值〔适应度〕 intGene[NUMG];//用元素取值于定义域｛0,1｝的数组表示染色体。}GENE;3.2算法求解01背包问题时用到的参数POPSIZE：种群大小，即的可行解的个数。NUMG：染色体中基因的个数，即物品的总数。CAPACITY：背包的容量。MAXB：二进制表示的染色体换算之后的最大十进制整数。用于随机产生一个整数，进而转换作染色体。SIM：染色体之间的相似度阈值。当染色体之间的相似度到达阈值时，算法即停止运行。PC=1.0：交叉概率为100％。PM=0.2：变异概率为20％，变异可以保证种群的多样性，从而防止算法收敛于某个局部解。3.3选择操作选择操作采用了赌轮选择〔Roulette-wheelselection〕的方法。函数selectIndex()中包含了选择染色体的具体过程。其流程图如图1所示。图1赌轮选择流程图 程序中用一个Begin来代表当前赌轮上的指针的位置，End那么用来使赌轮循环转动。用summaryBE表示当前赌轮上的指针转过的染色体的总价值。用summaryF表示当前全部染色体的价值总和。用randProb作为染色体选择的阈值。randProb为介于[0,1]之间的随机数。选择使summaryBE/summaryF大于阈值randProb的染色体作为要选择的染色体。3.4交叉操作单点交叉操作的简单方式是将被选择出的两个个体S1和S2作为父母个体，从[0，1]中产生一个随机数p，如果p<pc，将两者的局部基因码值进行交换。假设如下两个父代：父代1:11421386325434324父代2:1123568563185633随机选择一个交叉点为11，交叉后为：子代1:11421386325485633子代2:1123568563134324交叉过程的目的就是希望新的基因是由旧的基因中好的局部组合而成的，从而新的基因比原先的基因要好。当然把旧的种群中的一局部基因完全保存到下一代中去也是很有意义的。程序中采用了单点交叉的策略。如下程序代码所示：for(intj=0;j<partPos;j++){ nextGenome[i].Gene[j]=parentGenome[Father].Gene[j]; nextGenome[i+POPSIZE/2].Gene[j]=parentGenome[Mother].Gene[j];}for(;j<NUMG;j++){ nextGenome[i].Gene[j]=parentGenome[Father].Gene[j]; nextGenome[i+POPSIZE/2].Gene[j]=parentGenome[Mother].Gene[j];}partPos为随机产生的整数，代表交叉的位置。第一个for循环将partPos位置之前的基因遗传给一个后代，而第二个循环那么将partPos位置之后的基因进行了交换。calculateCapacity函数用于计算交叉操作后的染色体的容量。calculateFitness函数用于计算交叉操作后的染色体的适应度。checkCapacity函数那么用于检查交叉后的染色体的合理性，容量超出背包的染色体是不合理的。这里没有使后代死亡，而是随机地调整了染色体中的基因。使得基因能够适应环境〔背包的容量〕而继续生存。3.5精英策略精英策略为了不使最优解在交叉的过程中，不会丧失最优解而采取的策略。其思想是保存上一代中的适应性强的染色体。相应地取代下一代中适应性弱的染色体。程序中精英策略由keepBestParents函数和sortFiness函数来实现。需要说明的是sortFitness仅仅对种群的索引进行了排序。然后用父代中20%的适应度较大的优秀染色体替换子代中20%的适应性弱的染色体。3.6变异操作染色体的变异可以保持种群的多样性，防止最优解的丧失以及算法收敛到局部最优解。变异操作由mutation函数实现。首先产生一个介于0和1之间的随机数prob，假设prob小于MP那么进行变异操作：随机产生一个位置partPos，然后变异前染色体的partPos位置的基因为1，那么变异为0，否那么变异为1；相应地要进行适应度和染色体容量的变化。3.7代际更新代际之间的更新，即用新生成的种群代替取代旧的种群。这个操作在updateGeneration函数中实现，同时这个操作使用了前面提及的精英策略。实际上，父代种群中优秀的染色体已被保存，updateGeneration中只是用新种群中的优秀染色体来代替父代中的染色体。由于对父代和子代的染色体都进行了排序，因此程序中将子代的80％视作优秀，将父代中的前20％视作优秀。3.8算法的终止程序中采用了一个HASH表来对子代种群的适应度进行HASH操作。HASH表中的头结点纪录了头结点所指向的单链表的信息。如下代码中的注释：typedefstructHead{ intmaxFitness;//单链表中的最大的Fitness intCount; //HASH到该结点的染色体的数目 intDiff; //单链表中有多少不同的Fitness HASHNODE*Next;}HEAD;用这样的一个HASH表结构可以只需遍历HASH表中的头结点，即可知当前的种群的适应度最大的染色体是否集中。具体地，如checkFitness函数中的下面几行代码：index=maxFitness(hashTable);doubleCPount=hashTable[index].Count/(double)POPSIZE;doublepDiff=hashTable[index].Diff/(double)POPSIZE;if(CPount>=0.9&&pDiff<=0.1){ sameFlag=false;}如果当前maxFitness最大的头结点满足if语句中的判断条件，那么sameFlag置为真，即算法停止迭代的条件得到了满足。TraverseHashTable函数那么用于遍历HASH表。算法终止的另一个条件是迭代的次数。程序中设定了算法的最大迭代次数为1000。3.9仿真结果与测试试验中用到的物品的重量和价值分别存储于以下两个数组之中。intWeight[NUMG]={6,9,8,8,6,1,10,5,7,1}; intValue[NUMG]={2,20,5,4,19,14,18,8,11,6};父代种群存储于parentGenome[NUMG]中，子代种群存储于nextGenome[NUMG]中。程序的初始状态和结束状态如下面的表格所示：初始的种群:WeightValue染色体中的基因21520010110101222300110001012240000110001122530100010110264510100110012453110001001122530100010110232510110100002648101011010025290111000000初始的HASH表:头结点索引maxFitnessCountDiff单链表中的结点内容0521152:1534253:403291129:6451145:9481148:10231123:12251125:3.9.1不同交叉概率下所的测试结果在程序实现上，本文采用VC++6.0作为程序开发工具，测试是在奔腾2.8G，512M以上内存的微机上进行的，操作系统是WinXP。当PM=0.2时，程序在运行了16次后停止运行。停止时的种群:WeightValue染色体中的基因29780100110111297801001101112978010011011129780100110111297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止时的HASH表:头结点索引maxFitnessCountDiff单链表中的结点内容0789178:12641164:当PM=0.1时，程序在运行了3次后停止运行。停止时的种群:WeightValue染色体中的基因22530100010110225301000101102453110001001124531100010011225301000101102253010001011024531100010011225301000101102253010001011026481010110100停止时的HASH表:头结点索引maxFitnessCountDiff单链表中的结点内容1539178:9481148:当PM=0.15时，程序在运行了26次后停止运行。停止时的种群:WeightValue染色体中的基因29780100110111297801001101112978010011011129780100110111297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止时的HASH表:头结点索引maxFitnessCountDiff单链表中的结点内容0789178:12641164:当PM=0.18时，程序在运行了13次后停止运行。停止时的种群:WeightValue染色体中的基因2978010011011129780100110111297801001101112872010010110297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止时的HASH表:头结点索引maxFitnessCountDiff单链表中的结点内容0789178:7721172:对于不同变异概率下运行次数和所得值如下列图所示：从上图我们可以总结出：变异概率太小，可能是某些基因位过早丧失的信息无法恢复，导致无法获得最优解变异概率过高，那么搜索将变成随机搜索，增大了搜索次数，但能得到最优解3.9.2极端数据对结果的影响当初始种群全是零时：WeightValue染色体中的基因000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000所得结果：当初始种群为：WeightValue染色体中的基因000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000160000000001所得结果：分析：超过最大迭代次数，但相似度还没到达0.9，所以只有一个估计值〔最大值〕当初始种群为：WeightValue染色体中的基因611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111所得结果：分析：超过最大迭代次数，但相似度还没到达0.9，所以只有一个估计值〔最大值〕3.9.3仿真结果总结通过对以上各种情况分析，我们可知：当前01背包问题的最优解为 X=｛0,1,0,0,1,1,0,1,1,1｝对应的最优值是78，即当前能够装入背包的最大价值。通过上述仿真实验和数据测试，可以得出利用本文算法求解背包问题能够获得较满意的效果。本文的算法不但有很快的收敛速度，而且在进化过程中种群的多样性保持很好，具有良好的全局搜索能力。因此，我们认为本文算法是可行的和有效的。结论用遗传算法解最优化问题，首先应对可行域中的个体进行编码，然后在可行域中随机挑选指定群体大小的一些个体组成作为进化起点的第一代群体，并计算每个个体的目标函数值，即该个体的适应度值。接着就像自然界中的遗传规律一样，利用选择机制从群体中随机挑选个体作为繁殖过程前的个体样本。选择机制保证适应度较高的个体能够保存较多的样本；而适应度较低的个体那么保存较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算法对挑选后的样本进行交换和基因突变。交叉算法交换随机挑选的两个个体的某些位，变异算子那么直接对一个个体中的随机挑选的某一位进行突变。这样通过选择和繁殖就产生了下一代群体。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。与其他算法相比，遗传算法主要有以下四个方面的不同：遗传算法所面向的对象是参数集的编码,而不是参数集本身；遗传算法的搜索是基于假设干个点，而不是基于一个点；遗传算法利用目标函数的信息，而不是导数或者其他辅助信息；遗传算法的转化规那么是概率性的，而不是确定性的。我们通过上述例子，严格按照遗传算法对背包问题进行了完整的求解，事实说明，用遗传算法来解决此类组合优化问题也是比拟有效的，而且非常好用，它的解的空间比拟大，而且在最后能无限度地接近最优解。所以，用遗传算法来解决背包问题是一个很好的方法。遗传算法作为一种对生物进化现象进行仿真的程序，取得了人工遗传的模拟效果，具有自适应性。在遗传算法的结构中遗传操作和选择机制是两个重要的因素，其联系可用"遗传算法=遗传操作+选择过程"这个逻辑关系来表示。如果一个应用问题不能求得目标函数的全局最优值,而只能或只希望求一定意义下的"满意解"，这时,可供选择的方法之一自然是遗传算法，因为遗传算法比其他算法有更多的优势。可喜的是,近年来遗传算法在商业应用方面取得了一系列重要成果。遗传算法的商业应用五花八门,覆盖面甚广。遗传算法具有隐并行性，它可容易改造成为并行/分布式算法，用来解决那些复杂性问题。到目前，遗传算法的理论机制仍不是很清楚，这可能和生命科学的研究一样，将是一个永恒的研究课题，但也是一个难题。致谢在论文即将完成之际，我非常感谢所有帮助过和支持过我的人。首先，我衷心地感谢我的指导老师孔芝老师，我的整个论文都是在孔芝老师的关心和细心指导下完成的。孔老师从论文的选题到完成，在各方面都给予了我大力的支持、耐心的帮助和热情地勉励，使我能够面对各种问题和困难，顺利地完成论文写作。从一开始的开题报告辩论就一直磕磕碰碰，那个时候差点失去信心，不知道接下来的论文工作该如何进行，但孔老师还是用他的切身经历鼓励我，以他渊博的学识、科学严谨的治学态度、一丝不苟的工作作风和无私忘我的奉献精神深深地影响着我，将使我受益终身。同时，在整个论文完成的过程中，同学和朋友对我的帮助也使我收益良多，不光是精神上的鼓励，还有学术上的帮助，让我一步步走下来，克服了一个又一个的困难，这也是我所收获的。每一次，碰到一个困难，不知该如何继续的时候，总是身边的朋友鼓励我，帮助我查找相关资料，因为对人工智能不太熟悉，所以论文完成阶段也是困难重重，但通过网上论坛上咨询，朋友的帮助，也一步步克服了困难，所以在这里也要特别感谢那些帮助过我的认识的和不认识的朋友。在此，我也非常感谢家人对我的支持。最后，感谢所有在生活和学习上给予我帮助的人！参考文献[1]陈国良,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.5~10.[2]陈文清.遗传算法综述[J].武汉:华中科技大学,2003.57~58.[3]王丽微.遗传算法的研究与应用[D].博士学位论文，哈尔滨;哈尔滨工业大学，1994.[4]李敏强，寇纪松，林丹等.遗传算法的根本原理与应用[M].北京:科学出版社，2002.[5]郝翔.遗传算法及其在规那么优化中的应用研究[J].西安交通大学博士论文，1997.[6]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999[7]席裕庚,柴天佑等.遗传算法综述[J].控制理论与应用.1996,13(6):697—708.[8]吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21,(2):69～71[9]玄光南,程润伟著.遗传算法与工程优化[M].清华大学出版社,北京:2004.[10]印鉴，李明．基于遗传算法的最优布局求解[J]．计算机研究与开展，2002，39(1O)：126％．1273．[11]王小平,曹立明著.遗传算法:理论、应用与软件实现[M].西安交通大学出版社,西安:2002.[12]周云鹏，题正义．遗传算法在组合优化中的应用[M]．辽宁工程技术大学学报[13]肖美华，王命延，王洪发，等．基于遗传算法和模拟退火算法的布局问题研究[J]．计算机工程与应用，2003，39(36)：70--72．[14]姜灵敏，陈松乔．二重结构编码遗传算法及其在贷款组合优化决策中的应用[J]．小型微型计算机系统[15]Mitchell,M.(1998).AnIntroductiontoGeneticAlgorithms.Massachusettss:TheMITPress.[16]史今迟．背包问题的实用求解算法研究[J]．山东大学学报[17]严尉敏.C语言程序设计[M].北京:清华大学出版社,2001.[18]/soft/3/2023/2023122023684.html[19][20]附录源程序#include<iostream.h>#include<stdlib.h>#include<string.h>#include<time.h>#definePOPSIZE 10 //定义种群大小#defineNUMG 10 //每个染色体中基因的数量#defineMAXVOL10//物品大小的上限#defineMAXVAL20//物品价值的上限#defineCAPACITY30//背包的大小#defineMAXB (1024)//2的10次方，用来随机产生一个染色体时候很有用。#defineSIM0.90 //算法终止条件之一：染色体之间的相似度上限#defineMP0.2 //变异率#defineDIST13 //程序中HASH表的距离//程序中用到的HASH表中链表结点结构定义typedefstructNode{ intFitness; structNode*Next;}HASHNODE;//链表结点//程序中用到的HASH表中头结点结构定义typedefstructHead{ intmaxFitness; intCount; intDiff; HASHNODE*Next;}HEAD;//头结点//HASH表HEADhashTable[DIST];//染色体的基因结构定义typedefstruct{ intWeight; //每个染色体的大小 intFitness;//适应度 intGene[NUMG];//染色体中对应的基因}GENE;//染色体基因结构//这里使用固定生成的染色体基因组，便于调试;可自行编写随机生成染色体的函数来生成染色体GENEparentGenome[NUMG]={ {0,0,{0,0,1,0,1,1,0,1,0,1}}, {0,0,{0,0,1,1,0,0,0,1,0,1}}, {0,0,{0,0,0,1,1,0,0,0,1,1}}, {0,0,{0,1,0,0,0,1,0,1,1,0}}, {0,0,{1,0,1,0,0,1,1,0,0,1}}, {0,0,{1,1,0,0,0,1,0,0,1,1}}, {0,0,{0,1,0,0,0,1,0,1,1,0}}, {0,0,{1,0,1,1,0,1,0,0,0,0}}, {0,0,{1,1,1,0,1,1,0,1,0,0}}