毕业设计（论文）-基于遗传算法求解背包问题

理工类理工类理工类本科生毕业设计〔论文〕(2021届)题目：基于遗传算法求解背包问题学院：数理与信息工程学院专业：计算机科学与技术学生姓名：学号：06220313指导教师：职称：副教授合作导师：职称：完成时间：2021年3月31日成绩：HYPERLINK浙江师范大学本科毕业设计(论文)正文目录摘要……………………1英文摘要………………11引言………………12背包问题概述……………………22.1背包问题描述………………22.2研究背包问题的意义………23遗传算法概述……………………23.1遗传算法的特点……………33.2遗传算法的应用领域………34遗传算法的根本原理……………44.1根本流程……………………44.2编码…………54.3适应度函数…………………54.4遗传算子……………………6选择算子…………………6交叉算子…………………7变异算子…………………74.5参数控制……………………8群体规模………………8交叉概率………………8变异概率………………84.6算法结束条件控制…………95实现求解背包问题的遗传算法………………95.10_1背包问题中染色体的表示………………95.2遗传算法求解0_1背包问题时用到的参数………………95.3选择操作……………………95.4交叉操作……………………105.5精英策略……………………115.6变异操作……………………115.7代际更新……………………115.8算法终止……………………115.9仿真结果与测试……………12不同交叉概率下所得测试结果………13极端数据对结果的影响………………15仿真结果总结…………185.10问题总结……………………186展望………………18致谢…………………19参考文献……………20附源程序……………21基于遗传算法求解背包问题数理与信息工程学院计算机科学与技术专业〔06220313〕指导老师：〔副教授〕摘要背包问题(Knapsackproblem)是一种组合优化的NP完全问题,本文首先介绍了根本遗传算法的根本原理、特点及其根本实现技术，接着针对背包问题，论述了遗传算法在编码表示和遗传算子〔包括选择算子、交叉算子变异算子这三种算子〕等方面的应用情况。并且结合背包问题实例，给出了具体的编码方法，运行参数，群体大小，最大迭代次数，以及适宜的遗传算子。最后，简单说明了遗传算法在求解背包问题中的应用并对遗传算法解决背包问题的前景提出了展望。关键词：背包问题；遗传算法；遗传算子；编码GeneticAlgorithmforKPJinTianTianDirector:Prof.DaYongDeng(CollegeofMathematicsPhysicsAndInformationEngineering,ZhejiangAbstract:KP(KnapsackProblem)isacombinatorialoptimizationofNP-completeproblem.Theprimaryknowledge,characteristicsandthebasictechniquesofGAareintroducedfirstly.Theencodingmodelandgeneticoperators(includingselectionoperation,crossoveroperationandmutationoperation)solvingKParediscussedsecondly.Combinedwithexamplesofknapsackproblem,wehavegiventhespecificencodingmethod,operatingparameters,popsize,maxgeneration,andsuitablegeneticoperator.Atlast,theapplicationofgeneticalgorithmissimplepresented,andtheprospectforthefutureofgeneticalgorithminsolvingKPhasbeengiven.Keywords:KP,geneticalgorithm,geneticoperators,encoding1引言

现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规那么生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机搜索算法。背包问题(Knapsackproblem)是一种组合优化的NP完全问题,对这个问题的求解前人己经研究出了不少的经典的方法,例如解析法，穷举法等，但是这些传统的优化方法存在一些缺点，如算法复杂度太高。与传统的优化算法相比，遗传算法具有以下优点:在每一时刻，GA同时在多个子空间内进行搜索，对初始值不作要求;根本不用搜索空间的知识或其他辅助信息，而仅用适应度来评估个体优劣;具有很强的鲁棒性。因此遗传算法在背包问题求解方面的应用研究，对于构造适宜的遗传算法框架、建立有效的遗传作以及有效地解决背包问题等有着多方面的重要意义[5]。2背包问题概述2.1背包问题的描述背包问题又称子集合问题，最早是由Dantzing于20世纪50年代首次提出的，已成为计算机学科中一个经典的NP问题，本文讨论的是0-1背包问题，问题描述如下：指定给n件物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为C，求从这n件物品中选取一局部物品且对每件物品,或者选取,或者不选,每种物品只能装入背包一次,且要求满足放入背包中的物品总重量不超过背包容量。求出装入背包中物品价值总和最大的方案。注意：在此题中，所有的重量值均为整数。数学模型限制条件为：所求表达式为：其中，表示物品放入背包，表示物品未放入背包。2.2研究背包问题的意义背包问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最大值。虽然它陈述起来很简单，但求解却很困难，并且已经被证明是NP完全问题。至今尚未找到有效的求解方法，在理论上枚举法可以解这一问题，但是当n较大时，解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短，能满足实际问题精度要求的解，成为解决该问题的主要途径[8]。背包问题的求解，一直以来倍受人们的关注。对于这样一个典型的、易于描述却难以处理的NP难题，有效地解决它在可计算理论上有着重要的理论价值。并且，背包问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。背包问题也可描述为决定性问题，相似问题经常出现在商业、投资组合优化、组合数学，计算复杂性理论、密码学和应用数学等领域中，因此具有广泛的实际应用领域。3遗传算法概述遗传算法〔GA〕是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，也是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术。它是在1975年首次由美国密西根大学的D.J.Holland教授和他的同事们借鉴生物界自然选择和进化机制根底之上提出的。经过近30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息[19]。遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应度值。算法将根据适应度值对它进行寻优的过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的，它的搜索能力由选择算子和杂交算子决定，变异算子那么保证了算法能够搜索到问题空间的每一个点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Holland提出的模式定理(SchemaTheorem)和隐式并行性得以解释。近年来，遗传算法从理论到实际都已经取得了许多重要成果。由于它具有良好的全局搜索能力，是目前解决各种优化问题的最有效的方法，已经成为研究热点。3.1遗传算法的特点从整体上来讲，遗传算法是进化算法中产生最早、影响最大、应用也比拟广泛的一个研究方向和领域，它不仅包含了进化算法的根本形式和全部优点，同时还具备假设干独特的性能。[16]1)在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有优化函数倒数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解过程；2)假设遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约个模式,具有很高的并行性，因而具有显著的搜索效率；3)在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力；4)对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者参加特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普适性和易扩充性；5〕遗传算法的根本思想简单，运行方式和实现步骤标准，便于具体使用；遗传算法的这些特点使得它一经提出即在理论上引起了高度重视，能够应用于一些到目前为止人们知之甚少的困难问题领域，产生大量的成功案例。3.2遗传算法的应用领域遗传算法的主要应用领域包括以下几个方面：函数优化问题。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用例子。很多人构造出了各种各样的复杂形式的测试函数来评价遗传算法的性能。而且对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。组合优化问题。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最正确工具之一。实践证明，遗传算法对于求解组合优化问题非常有效。遗传算法已经在求解旅行商问题、图形划分问题等方面得到成功的应用。生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以求解，也会因简化太多而使求解结果与实际相差甚远。由于可以采用字符编码，而且不必使用恰好的目标函数估值，遗传算法也成为解决复杂调度问题的有效工具。在单件生产车间调度、流水线生产车间调度、生产规划、任务分配、虚拟企业中的伙伴选择方面遗传算法都得到了有效的应用。自动控制。在自动控制领域有很多与优化相关的问题需要求解，而且这些优化问题通常要么是通过积分表达的，要么是写不出明确而严格的解析表达式。遗传算法在求解这类自动控制问题方面已显示出其独特的优点。例如，用遗传算法进行航空控制系统的优化、用遗传算法优化设计透平机械、设计模糊控制器等，都取得了较好的效果。机器学习。学习能力是高级自适应系统所应具备的特征之一。基于遗传算法的机器学习在很多方面都得到成功应用。例如，遗传算法被用于学习模糊控制规那么、确定模糊集的隶属函数、改良模糊系统的性能;被用来调整人工神经网络的连接权及网络拓扑优化。此外，遗传算法还被应用到反问题求解、机器人学习、生物计算、图像处理、人工智能以及遗传编程等领域。4遗传算法的根本原理遗传算法GA把问题的解表示成“染色体〞，并且在执行遗传算法之前。给出一群“染色体〞，作为假设解，然后，把这些假设解置于问题的“环境〞中，并按适者生存的原那么，从中选择出较适应环境的“染色体〞进行复制，再通过交叉和变异过程产生更适应环境的新一代“染色体〞群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体〞上，它就是问题的最优解[9]。4.1根本流程遗传算法需要涉及五大要素:编码、群体初始化、适应性函数的设定、遗传操作的设计和控制参数的设定。具体步骤如下：(l)编码，把问题的解转化成位串表示形式;(2)定义适应性函数;(3)确定遗传算法的各算子及参数，包括选择、交叉、变异方法，交叉率、变异率、群体容量、最大遗传代数等;(4)随机初始化群体;(5)计算群体中每一个染色体的适应值;(6)按照遗传操作形成下一代群体;①从当前群体中由事先设定好的选择方法选出两个染色体;②根据给定的交叉率，对选出的两个染色体进行交叉操作;③根据给定的变异率，对每个染色体进行变异操作;④重复①、②、③步，直到新的一代群体被创立出来;(7)判断新产生的群体是否能满足结束指标，如果满足，那么算法结束，如果不满足，那么返回步骤(6)。4.2编码按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与遗传算法的染色体位串结构之间建立关系，即确定编码和解码运算。编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的编码空间相对应，编码的选择是影响算法性能与效率的重要因素。常用的编码方法有如下几种：①二进制编码：二进制编码将问题空间的参数表示为基于字符集{0,1}构成的染色体位串，是最常用的一种编码方式。②大字符集编码:除基于字符集{0,1}的二进制编码之外，可以结合实际问题的特征采用D进制数或字符集来表示长度为L的位串。③序列编码：用排列法进行编码显得更为自然、合理。④实数编码：实数编码具精度高、大空间搜索的优点。⑤树编码：树编码是一种非固定常用编码模式，其表示空间是开放的。在搜索过程中树可以自由生长，但是不便于形成更具有结构化和层次性的问题解，实际应用中往往可以加以限制。⑥自适应编码：实现选择适宜的固定编码方式对潜在的遗传算法用户来说是一个难题。事实上，提出适宜的编码同解决问题本身一样困难。因此，许多用户认为既然要用遗传算法解决问题，为什么不让它同时调整编码呢?一些专家就采用了自适应编码[11]。4.3适应度函数适应度评价是通过适应度函数对个体质量的一种测量，是进化过程中自然的唯一依据。因此适应度函数的选择至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。对目标函数值域的某种映射变换称为适应度的尺度变换。适应度函数的设计主要满足以下条件：①单值、连续、非负、最大化:这个条件是容易理解和实现的。②合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达成比拟难以衡量。③计算量小：适应度函数设计应尽可能简单，这样可以减小计算时间和空间上的复杂性，降低本钱。④通用性强：适应度函数对具体问题应尽可能具有通用性，最好无需使用者改变适应度函数中的参数。适应度函数的尺度变换有线性变换法、幕函数变换法、指数变换法[10]。4.4遗传算子标准的遗传算子一般都包括选择、交叉和变异三种。它们构成了遗传算法的核心，使得算法具有强大的搜索能力。选择算子选择操作就是用来确定如何从父代种群中按照某种方法选取哪些个体遗传到下一代种群的遗传运算。它是根据个体适应度函数值的大小正比于其被放入候选的概率的过程。在备选集中按照一定的选择概率进行操作，这个概率取决于种群中个体的适应度及其分布。其主要作用是防止了基因缺失，提高全局收敛性和计算效率。选择算子可看作是种群空间到父体空间的随机映射，它按照某种准那么或概率分布从当前种群中以高的概率选取那些好的个体组成不同的父体以供生成新的个体。目前常用的选择策略有赌盘赌选择算子、排序选择算子、最优保存选择算子和锦标赛选择算子等[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)以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于这些概率值用比例选择的方法来产生下一代群体。是指在计算每个个体的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概率。交叉算子交叉操作是遗传算法中最主要的遗传操作。它是模仿自然界有性繁殖的基因重组过程，对两个父代个体进行基因操作，其作用在于把原有优良基因遗传到下一代种群中，并生成包含更复杂基因结构的新个体。交叉算子可看作是父体空间到个体空间的随机映射，它通常的作用方式是：随机地确定一个或多个分量位置为交叉点，由此将一对父体的两个个体分为有限个片断再以概率〔称为交叉概率〕交换相应片断得到新的个体。变异算子在生物种群中总是存在着变异，变异指的是子代和父代之间具有某些不相似的现象，即因为存在着变异现象，所以子代和父代之间中总是不完全相同的。变异是生物进化过程中不可缺少的，它为生物的进化和开展创造了条件。在遗传算法中，变异是指父代染色体中的某些基因片，以相对较小的概率发生随机改变的操作过程。所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。在遗传算法中使用变异算子主要有以下两个目的：①改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题的最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这时假设再使用变异算子来调整个体编码串中的局部基因值，就可以从局部的角度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索能力。②维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有基因值，从而可以改变个体编码串的结构，维持群体的多样性，这样就有利于防止出现早熟现象。4.5参数控制在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组参数在初始阶段或种群进化过程中需要合理地选择和控制。主要包括种群规模n、交叉概率pc以及变异概率pm。群体规模大种群含有较多模式，为遗传算法提供了足够的模式采样容量，可以改良GA搜索的质量，防止早熟前收敛。但大种群增加了个体适应性评价的计算量，从而使收敛速度降低。交叉概率交叉概率pc控制着交叉算子的应用频率，在每一代新的种群中，需要对个体的染色体结构进行交叉操作。交叉概率越高，种群中新结构的引入越快，已获得的优良基因结构的丧失速度也相应升高。而交叉概率太低那么可能导致搜索阻滞。一般pc=0.60—1.00。变异概率变异操作是保持种群多样性的有效手段，交叉结束后，交配池中的全部个体位串上的每位等位基因按概率随机改变，因此每代中大约发生n次变异。变异概率太小，可能使某些基因位过早丧失的信息无法恢复；而变异概率过高，那么搜索将变成随机搜索。一般取pm=0.05—0.2。4.6算法结束条件控制终止代数是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前种群中的最优个体作为所求问题的最优解输出。由于遗传算法不同于传统的优化算法，它没有利用目标函数的梯度等信息，所以在遗传进化过程中，很难有明确的搜索终止准那么。常用的方法是预先给定算法的终止进化代数。一般来说，预先给定算法的终止进化代数只能找到问题在给定时限内所能寻求的相对满意解，但不一定是问题的最优解或较高精度的近似解。为了获得较高精度的近似解，通常可依据种群适应度的稳定来适时调整终止进化代数的设置，或者在连续进化数代以后，如果解的适应度没有明显的改良，那么终止进化过程。终止进化代数一般的取值范围是100-1000。5实现求解背包问题的遗传算法5.10_1背包问题中染色体的表示 用向量X来表示染色体，X=｛x1，x2，……，xn｝。，xi∈｛0,1｝，xi=1表示物品i装入了背包，xi=0表示物品i未装入背包。每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的适应度。程序中定义了这样的一个结构来表示染色体：typedefstruct{ intWeight; //染色体代表的物品的总重量 intFitness; //染色体代表的物品的价值〔适应度〕 intGene[NUMG];//用元素取值于定义域｛0,1｝的数组表示染色体。}GENE;5.2遗传算法求解01背包问题时用到的参数POPSIZE：种群大小，即的可行解的个数。NUMG：染色体中基因的个数，即物品的总数。CAPACITY：背包的容量。MAXB：二进制表示的染色体换算之后的最大十进制整数。用于随机产生一个整数，进而转换作染色体。SIM：染色体之间的相似度阈值。当染色体之间的相似度到达阈值时，算法即停止运行。PC=1.0：交叉概率为100％。PM=0.2：变异概率为20％，变异可以保证种群的多样性，从而防止算法收敛于某个局部解。5.3选择操作 选择操作采用了赌轮选择〔Roulette-wheelselection〕的方法。函数selectIndex()中包含了选择染色体的具体过程。其流程图如图1所示。图1赌轮选择流程图 程序中用一个Begin来代表当前赌轮上的指针的位置，End那么用来使赌轮循环转动。用summaryBE表示当前赌轮上的指针转过的染色体的总价值。用summaryF表示当前全部染色体的价值总和。用randProb作为染色体选择的阈值。randProb为介于[0,1]之间的随机数。选择使summaryBE/summaryF大于阈值randProb的染色体作为要选择的染色体。5.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函数那么用于检查交叉后的染色体的合理性，容量超出背包的染色体是不合理的。这里没有使后代死亡，而是随机地调整了染色体中的基因。使得基因能够适应环境〔背包的容量〕而继续生存。5.5精英策略精英策略为了不使最优解在交叉的过程中，不会丧失最优解而采取的策略。其思想是保存上一代中的适应性强的染色体。相应地取代下一代中适应性弱的染色体。程序中精英策略由keepBestParents函数和sortFiness函数来实现。需要说明的是sortFitness仅仅对种群的索引进行了排序。然后用父代中20%的适应度较大的优秀染色体替换子代中20%的适应性弱的染色体。5.6变异操作染色体的变异可以保持种群的多样性，防止最优解的丧失以及算法收敛到局部最优解。变异操作由mutation函数实现。首先产生一个介于0和1之间的随机数prob，假设prob小于MP那么进行变异操作：随机产生一个位置partPos，然后变异前染色体的partPos位置的基因为1，那么变异为0，否那么变异为1；相应地要进行适应度和染色体容量的变化。5.7代际更新代际之间的更新，即用新生成的种群代替取代旧的种群。这个操作在updateGeneration函数中实现，同时这个操作使用了前面提及的精英策略。实际上，父代种群中优秀的染色体已被保存，updateGeneration中只是用新种群中的优秀染色体来代替父代中的染色体。由于对父代和子代的染色体都进行了排序，因此程序中将子代的80％视作优秀，将父代中的前20％视作优秀。5.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。5.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:不同交叉概率下所得测试结果在程序实现上，本文采用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:对于不同变异概率下运行次数和所得值如下列图所示：从上图我们可以总结出：变异概率太小，可能是某些基因位过早丧失的信息无法恢复，导致无法获得最优解变异概率过高，那么搜索将变成随机搜索，增大了搜索次数，但能得到最优解极端数据对结果的影响当初始种群全是零时：WeightValue染色体中的基因000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000所得结果：当初始种群为：WeightValue染色体中的基因000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000160000000001所得结果：分析：超过最大迭代次数，但相似度还没到达0.9，所以只有一个估计值〔最大值〕当初始种群为：WeightValue染色体中的基因611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111所得结果：分析：超过最大迭代次数，但相似度还没到达0.9，所以只有一个估计值〔最大值〕仿真结果总结通过对以上各种情况分析，我们可知：当前01背包问题的最优解为 X=｛0,1,0,0,1,1,0,1,1,1｝对应的最优值是78，即当前能够装入背包的最大价值。通过上述仿真实验和数据测试，可以得出利用本文算法求解背包问题能够获得较满意的效果。本文的算法不但有很快的收敛速度，而且在进化过程中种群的多样性保持很好，具有良好的全局搜索能力。因此，我们认为本文算法是可行的和有效的。5.10问题总结用遗传算法解最优化问题，首先应对可行域中的个体进行编码，然后在可行域中随机挑选指定群体大小的一些个体组成作为进化起点的第一代群体，并计算每个个体的目标函数值，即该个体的适应度值。接着就像自然界中的遗传规律一样，利用选择机制从群体中随机挑选个体作为繁殖过程前的个体样本。选择机制保证适应度较高的个体能够保存较多的样本；而适应度较低的个体那么保存较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算法对挑选后的样本进行交换和基因突变。交叉算法交换随机挑选的两个个体的某些位，变异算子那么直接对一个个体中的随机挑选的某一位进行突变。这样通过选择和繁殖就产生了下一代群体。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。与其他算法相比，遗传算法主要有以下四个方面的不同：遗传算法所面向的对象是参数集的编码,而不是参数集本身；遗传算法的搜索是基于假设干个点，而不是基于一个点；遗传算法利用目标函数的信息，而不是导数或者其他辅助信息；遗传算法的转化规那么是概率性的，而不是确定性的。我们通过上述例子，严格按照遗传算法对背包问题进行了完整的求解，事实说明，用遗传算法来解决此类组合优化问题也是比拟有效的，而且非常好用，它的解的空间比拟大，而且在最后能无限度地接近最优解。所以，用遗传算法来解决背包问题是一个很好的方法。6展望遗传算法作为一种对生物进化现象进行仿真的程序，取得了人工遗传的模拟效果，具有自适应性。在遗传算法的结构中遗传操作和选择机制是两个重要的因素，其联系可用"遗传算法=遗传操作+选择过程"这个逻辑关系来表示。如果一个应用问题不能求得目标函数的全局最优值,而只能或只希望求一定意义下的"满意解"，这时,可供选择的方法之一自然是遗传算法，因为遗传算法比其他算法有更多的优势。可喜的是,近年来遗传算法在商业应用方面取得了一系列重要成果。遗传算法的商业应用五花八门,覆盖面甚广。遗传算法具有隐并行性，它可容易改造成为并行/分布式算法，用来解决那些复杂性问题。到目前，遗传算法的理论机制仍不是很清楚，这可能和生命科学的研究一样，将是一个永恒的研究课题，但也是一个难题。致谢在论文即将完成之际，我非常感谢所有帮助过和支持过我的人。首先，我衷心地感谢我的指导老师邓大勇老师，我的整个论文都是在邓大勇老师的关心和细心指导下完成的。邓老师从论文的选题到完成，在各方面都给予了我大力的支持、耐心的帮助和热情地勉励，使我能够面对各种问题和困难，顺利地完成论文写作。从一开始的开题报告辩论就一直磕磕碰碰，那个时候差点失去信心，不知道接下来的论文工作该如何进行，但邓老师还是用他的切身经历鼓励我，以他渊博的学识、科学严谨的治学态度、一丝不苟的工作作风和无私忘我的奉献精神深深地影响着我，将使我受益终身。同时，在整个论文完成的过程中，同学和朋友对我的帮助也使我收益良多，不光是精神上的鼓励，还有学术上的帮助，让我一步步走下来，克服了一个又一个的困难，这也是我所收获的。每一次，碰到一个困难，不知该如何继续的时候，总是身边的朋友鼓励我，帮助我查找相关资料，因为对人工智能不太熟悉，所以论文完成阶段也是困难重重，但通过网上论坛上咨询，朋友的帮助，也一步步克服了困难，所以在这里也要特别感谢那些帮助过我的认识的和不认识的朋友。在此，我也非常感谢家人对我的支持。最后，感谢所有在生活和学习上给予我帮助的人！参考文献：[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/2021/2021122021684.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}}, {0,0,{1,1,1,1,0,0,0,0,0,0}}};GENEnextGenome[NUMG];//新的染色体//需要装入背包的物品的大小和价值intWeight[NUMG]={6,9,8,8,6,1,10,5,7,1};intValue[NUMG]={2,20,5,4,19,14,18,8,11,6};intindexPF[POPSIZE];//父染色体索引intindexCF[POPSIZE];//子染色体索引//计算染色体的大小voidcalculateCapacity(GENE*Genome,intiD){ Genome[iD].Weight=0; for(intj=0;j<NUMG;j++){ if(Genome[iD].Gene[j]==1){ Genome[iD].Weight+=Weight[j]; } }}//计算染色体的适应度voidcalculateFitness(GENE*Genome,intiD){ Genome[iD].Fitness=0; for(intj=0;j<NUMG;j++){ if(Genome[iD].Gene[j]==1){ Genome[iD].Fitness+=Value[j]; } }}//染色体大小检查voidcheckCapacity(GENE*Genome,intiD){ while(Genome[iD].Weight>CAPACITY){ intidModify=rand()%NUMG; if(Genome[iD].Gene[idModify]==1){ Genome[iD].Gene[idModify]=0; Genome[iD].Weight -=Weight[idModify]; Genome[iD].Fitness-=Value[idModify]; } }}//初始化HASH表voidinitHashTable(HEAD*hashTable){ for(inti=0;i<DIST;i++){ hashTable[i].maxFitness=0; hashTable[i].Count=0; hashTable[i].Diff=0; hashTable[i].Next=NULL; }}//在HASH表头结点中搜索最大的适应度intmaxFitness(HEAD*hashTable){ intmaxF=hashTable[0].maxFitness; intindex=0; for(inti=1;i<DIST;i++){ if(hashTable[i].maxFitness>maxF){ maxF=hashTable[i].maxFitness; index=i; } } returnindex;}//判断适应度Fitness是否已经在HASH头结点对应的链表中HASHNODE*isAlreadyExist(HASHNODE*pHead,intFitness){ HASHNODE*lastPos=NULL; while(NULL!=pHead){ if(pHead->Fitness==Fitness){ break; } //cout<<pHead->Fitness<<endl; lastPos=pHead; pHead=pHead->Next; } returnpHead;}//遍历HASH表voidTraverseHashTable(HEAD*hashTable){ intindex=0; HASHNODE*lastPos=NULL; cout<<"I:"<<"MAX:"<<"C:"<<"D:"<<"O"<<endl; for(inti=0;i<DIST;i++){ if(hashTable[i].Count==0){ continue; } cout<<i<<":"<<hashTable[i].maxFitness<<":"<<hashTable[i].Count<<":"<<hashTable[i].Diff<<":"; lastPos=hashTable[i].Next; cout<<"Content:"; while(NULL!=lastPos){ cout<<lastPos->Fitness<<":"; lastPos=lastPos->Next; } cout<<endl; }}//检查种群中的适应度是否SIMboolcheckFitness(){ HASHNODE*pNode=NULL; intindex=0; boolsameFlag=true; initHashTable(hashTable); for(inti=0;i<POPSIZE;i++){ index=parentGenome[i].Fitness%DIST; hashTable[index].Count++; pNode=isAlreadyExist(hashTable[index].Next,parentGenome[i].Fitness); if(NULL==pNode){ pNode=newHASHNODE; hashTable[index].Diff++; pNode->Next=hashTable[index].Next; pNode->Fitness=parentGenome[i].Fitness; if(parentGenome[i].Fitness>hashTable[index].maxFitness){ hashTable[index].maxFitness=parentGenome[i].Fitness; } hashTable[index].Next=pNode; } } index=maxFitness(hashTable); doubleCPount=hashTable[index].Count/(double)POPSIZE; doublepDiff=hashTable[index].Diff/(double)POPSIZE; if(CPount>=0.9&&pDiff<=0.1){ sameFlag=false; } TraverseHashTable(hashTable); returnsameFlag;}//赌轮选择函数代码段intBegin=0;intEnd=1;//计算从Begin－End位置的染色体的适应度之和intsummaryFitness(intBegin,intEnd){ intsummaryF=0; if(Begin<End){ for(inti=Begin;i<End;i++){ summaryF+=parentGenome[i].Fitness; } }else{ for(inti=Begin;i<POPSIZE;i++){ summaryF+=parentGenome[i].Fitness; } for(i=0;i<End;i++){ summaryF+=parentGenome[i].Fitness; } } returnsummaryF;}//赌轮选择染色体以便于交叉操作intselectIndex(){ doublerandProb=0.0; doublecrossProb=0.0; intsummaryBE=0; intsummaryF=0; intindex; boolflag=true; randProb=rand()%1000/1000.0; summaryF=summaryFitness(0,POPSIZE); while(flag){ summaryBE=summaryFitness(Begin,End); crossProb=(double)summaryBE/(double)summaryF; if(crossProb>randProb){ index=End; Begin=End; flag=false; } End++; if(End>POPSIZE){ End=1; } } returnindex;}//排序辅助数组boolvisitedFlag[POPSIZE];//获取当前HASH表中的最大Fitness的索引intselectedMaxFitness(GENE*Genome){ intmaxPos=0; for(inti=0;i<POPSIZE;i++){ if(!visitedFlag[i]){ maxPos=i; i=POPSIZE; } } for(i=0;i<POPSIZE;i++){ if(!visitedFlag[i]&&Genome[maxPos].Fitness<Genome[i].Fitness){ maxPos=i; } } returnmaxPos;}//索引排序voidsortFitness(int*indexFitness,GENE*Genome){ memset(visitedFlag,false,NUMG*sizeof(bool)); for(inti=0;i<POPSIZE;i++){ indexFitness[i]=selectedMaxFitness(Genome); visitedFlag[indexFitness[i]]=true; }}//精英策略：保持优秀的父染色体voidkeepBestParents(){ for(inti=POPSIZE*8/10;i<POPSIZE;i++){ parentGenome[indexPF[i]].Fitness=parentGenome[indexPF[i-POPSIZE*8/10]].Fitness; parentGenome[indexPF[i]].Weight=parentGenome[indexPF[i-POPSIZE*8/10]].Weight; for(intj=0;j<NUMG;j++){ parentGenome[indexPF[i]].Gene[j]=parentGenome[indexPF[i-POPSIZE*8/10]].Gene[j]; } }}//更新当前的父代染色体voidupdateGeneration(){ keepBestParents(); for(inti=0;i<POPSIZE*8/10;i++){ parentGenome[indexPF[i]].Fitness=nextGenome[indexCF[i]].Fitness; parentGenome[indexPF[i]].Weight=nextGenome[indexCF[i]].Weight; for(intj=0;j<NUMG;j++){ parentGenome[indexPF[i]].Gene[j]=nextGenome[indexCF[i]].Gene[j]; } }}//交叉操作voidcrossOver(){ intpartPos; sortFitness(indexPF,parentGenome); for(inti=0;i<POPSIZE/2;i++){ partPos=rand()%NUMG; intFather=selectIndex(); intMother=selectIndex(); 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]; } calculateCapacity(nextGenome,i); calculateFitness(nextGenome,i); checkCapacity(nextGenome,i); calculateCapacity(nextGenome,i+POPSIZE/2); calculateFitness(nextGenome,i+POPSIZE/2); checkCapacity(nextGenome,i+POPSIZE/2); } sortFitness(indexCF,nextGenome);}//变异操作voidmutation(){ for(inti=0;i<POPSIZE;i++){ doubleprob=(rand()%1000)/1000.0; if(prob<MP){ intpartPos=rand()%NUMG; if(nextGenome[i].Gene[partPos]==1){ nextGenome[i].Gene[partPos]=0; nextGenome[i].Weight-=Weight[partPos]; nextGenome[i].Fitness-=Value[partPos]; }else{ if(nextGenome[i].Weight+Weight[partPos]<CAPACITY){ nextGenome[i].Gene[partPos]=1; nextGenome[i].Weight+=Weight[partPos]; nextGenome[i].Fitness+=Value[partPos]; }else{ //don'tmutate! } } } }}//打印所有的父代染色体voidprintGenome(){ for(inti=0;i<POPSIZE;i++){ cout<<parentGenome[i].Weight<<"-"; cout<<parentGenome[i].Fitness<<"-"; for(intj=0;j<NUMG;j++){ cout<<parentGenome[i].Gene[j]; } cout<<endl; }}voidmain(){ intnGenerations=1000; intnCount=0; boolflag=true; intindexMaxResult=0; //初始化染色体种群 for(inti=0;i<POPSIZE;i++){ for(intj=0;j<NUMG;j++){ if(parentGenome[i].Gene[j]==1){ parentGenome[i].Weight+=Weight[j]; parentGenome[i].Fitness+=Value[j]; } } checkCapacity(parentGenome,i); } //generateChromosomes();用于随机产生染色体 //generatePopulation();//用于随机产生种群 printGenome(); flag=checkFitness(); cout<<"-------"<<nCount<<"-------"<<endl; while(flag&&nCount<nGenerations){ nCount++; //当前循环次数 crossOver(); //交叉 mutation(); //变异 updateGeneration(); //更新种群 printGenome(); //打印种群中染色体 flag=checkFitness();//产看是否满足SIM cout<<"-------"<<nCount<<"-------"<<endl; } cout<<nCount<<endl; indexMaxResult=maxFitness(hashTable);//所得的01背包问题的最大值 if(nCount<nGenerations){//成功 cout<<"ThemaxValueis"<<hashTable[indexMaxResult].maxFitness<<endl; cout<<"TheinformationinGenomeisasbelow:"<<endl; printGenome(); }else{//失败 cout<<"OH,Sorry!"; cout<<"ThemaxValuemaybe"<<hashTable[indexMaxResult].maxFitness<<endl; cout<<"TheinformationinGenomeisasbelow:"<<endl; printGenome(); }}09/2011:46102机体齿飞面孔双卧多轴组合机床及CAD设计09/0