遗传算法综述

1、遗传算法综述史俊杰摘要：进化论和集体遗传学中出现的基因算法是计算智能的重要组成部分，在很多领域受到了极大的关注。本文主要回顾了遗传算法的起源和发展过程，简述了遗传算法的基本原理和特点。进一步指出遗传算法存在的问题及相应的改进方案，论述了其实际应用，讨论了遗传算法的未来发展。关键词：遗传算法、适用性函数、神经网络1.遗传算法的起源遗传算法(Genetic Algorithm，GA)是模拟自然界生物进化机制的算法，遵循适者生存和适者生存的规律，即消除优化过程中有用的保存和无用的东西。在科学和生产实践中表示，在所有可能的解决方法中，寻找最适合该问题要求的解决方法，即寻找最佳解决方案。该算法是1960

2、年在霍兰提出的，最初的目的是研究自然系统的自适应行为，设计具有自适应功能的软件系统。2.遗传算法开发20世纪60年代起，紧密的近代教授霍兰德开始研究自然和人工系统的自适应行为，以开发用于制造一般程序和机器的理论。巴格从20世纪60年代中期到70年代后期，他发明了遗传算法这个词，并发表了第一篇关于遗传算法应用的论文。1975年，在遗传算法发展史上建立了两个里程碑，一个是霍兰德出版了经典着作adaptation in nature and artifiei system，另一个是Dejong指导的博士论文an analysis of the behavior of a clavior of a进入

3、80年代，以象征体系模仿人类智能的现有人工智能暂时陷入了困境，神经网络、机器学习、遗传算法等从生物界底层开始模拟智能的研究重新复活，获得了繁荣。进入90年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科学新范式得到了广义进化合成理论等学术界的普遍认同。遗传算法有效地解决了NPC类型的组合优化问题和非线性多模型、多目标函数优化问题，因此在很多领域受到了广泛关注。遗传算法特性遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究越来越成熟。遗传算法具有进化计算的所有特性，但具有自身的特性：(1)搜索过程不受优化函数连续性的约束，没有优化函数导数必须存在的要求。(2)遗传算法

4、使用多点搜索或分组搜索进行隐式并行处理，可以加快计算速度。(3)遗传算法是选择、交叉、变异等运算以概率方式执行的自适应搜索技术，提高了搜索过程的灵活性，具有较好的全局优化解决方案能力。(4)遗传算法直接检索目标函数值，对函数的性别没有要求，具有很好的普遍性和扩展性。(5)遗传算法更适合于大规模复杂问题的优化。遗传算法研究理论在自然中，由于生物群内各个体之间的差异，对环境的适应和生存能力不同，根据自然生物进化的基本原则，适者生存和适者生存将消除其最差的人，通过交配将父母优秀的染色体和基因遗传给后代，通过染色体核基因的重组，创造出一个生命力更强的新实体和由它们组成的新群体。在特定条件下，基因发生突

5、变，产生新的基因和具有更强生命力的新个体；但是突变不是遗传的，随着个体不断更新，向最佳方向进化，实际上模仿自然界的生物进化机制，进化到最佳状态。在该算法中，正在研究的系统的响应曲面作为一个组，其表面的每个点作为组的对象描述，对象作为多维向量或矩阵描述，构成矩阵和向量的参数对应于构成生物种染色体的基因，染色体作为固定长度的二进制字符串表示，通过交换或突变等遗传操作在参数的一定范围内随机搜索，数据结构不断改善，创建了不同的向量，目标函数值保持得更好，目标函数值更低的点进行了研究遗传算法是一种迭代算法，每次迭代都有一组解决方案，每次最初随机生成和迭代，通过模拟进化和继承的遗传操作创建一组新的解决方案

6、，每个解决方案都给定一个目标函数，一次迭代成为一代。典型算法的流程图如图1所示，步骤如下：步骤1初始化：使用任何方法创建初始群体的初始字符串。每个初始字符串称为个人。Step2可变计算：根据可变函数计算第一代群体的每个单独可变值，具有最高可变值的实体。选择Step3:父群体使用适宜性百分比方法选择子群体。这里选择的概率是。Step4交集变异：通过交叉运算在子种群中以相同概率选择两个实体，然后以这些实体之间预先指定的概率执行重组运算，创建两个新实体并重复此过程。变异运算根据特定变异率Pf随机翻转一个身体的一侧，生成新对象并重复此过程。然后，Step2中适应性最高的对象最终形成了下一代的集体机器：

7、中适应性最高的对象。当Step5遗传代数满足终止条件时，停止运算，将1输出为近似最优对象。否则，k=k 1将切换为Step2。图1遗传算法流程图4.1遗传算法的原型约翰霍兰教授模拟了生物进化过程，设计了第一种被称为标准遗传算法的遗传算法。标准遗传算法提出了遗传算法的基本框架，以后对遗传算法的改进基于此算法。遗传算法的实现取决于细节，但具有共同的结构。算法反复更新精简池。此精简池称为组。在每次迭代中，根据自适应函数评估组的所有成员，然后从当前组中选择最高自适应作为概率方法的对象生成下一代组。其中一些被选中的个体原封不动地进入下一代群体，而其他的则被用作创建后代个体的基础。4.2遗传算法的基本要素

8、遗传算法的基本要素包括染色体编码方法、适合性函数、操作参数、遗传操作等。这里染色体编码方法是指个体的编码方式，目前包括二进制法、实数法等。二进制方法是将对象编码为一个二进制字符串，实数方法是将对象编码为一个实数字符串。拟合优度函数是计算根据目标编写的各个拟合优度值的函数，通过拟合优度函数计算每个单独的拟合优度值，并将其提供给选择运算符。执行参数是遗传算法在初始化时确定的参数，主要包括组大小m、遗传代数g、交叉概率Pt和变异概率Pm。基因操作是指选择操作、交叉操作、突变操作。选取用于确定相交对象和选定对象将创建的子对象的数量。一般方法如下：(1)每个人的选择概率与相应的适宜性值成比例的可变性比例

9、方法。(2)最适合的对象保留方法，无需配对即可将最适应的对象直接复制到下一代。(3)计算每个人的适合性后，根据其适合性大小对组中的对象进行排序，并将预先设计的概率表依次指定为每个人的选择概率的排序选择方法。所有实体按适用性排序，但选择概率和适用性没有直接关系，仅与序号相关。(4)联赛选拔方法、运营思想是在集团中任意选择特定数量的个人，将适应性最高的个体保存到下一代。重复执行，直到存储的对象数达到预设数。交集表示重组两个父图元的某些结构以建立新物件的动作。交叉操作的作用是组合新的个体，GA是区别于其他进化算法的重要特征，在遗传算法中起关键作用的是基因操作。各种交集运算子包含两个基本内容。(1)在

10、选择操作形成的群体中，随机配对对象，并根据预设的交叉概率确定每对是否需要交叉操作。(2)设置成对对象的交点，并交换这些点前后成对对象的某些结构。典型的相交作业方法包括一点相交、两点相交、一致相交、2d相交和树状结构相交。变异会给组内个别序列的特定基因座的基因值带来变化。变异的目的有两个：(1)使遗传算法具有局部随机搜索功能。(2)保持集团的多样性；变异运算子的作业通常包含两个步骤。(1)在群体中所有对象的代码串内随机决定基因座。(2)该基因座的基因值变异为预设的变异概率。变异运算子有多种方法，例如基本变异运算子、反转运算子、自适应变异运算子等。遗传算法的应用遗传算法优化了BP神经网络近年来，人

11、工神经网络发展迅速，在经济、军事、工业生产、生物医学领域得到了广泛的应用和影响。学习能力是神经网络最值得关注的特征，因此在神经网络发展过程中，对学习算法的研究一直占据着重要的地位，上世纪80年代中期出现的后台(BP)算法通过从全多层神经网络有效地解决学习问题，极大地推动了这一领域的研究工作。但是本质上，BP算法属于梯度下降算法，其缺点是容易陷入局部最小值，收敛速度慢，错误函数必须是可诱导的，网络结构中的某一个必须对整形有理论指导。美国密歇根大学的holanjay。教授启动的遗传算法是稳健、成功解决全局优化问题的高效并行全局搜索算法。因此，遗传算法可以应用于神经网络中的学习过程。这使得现有的BP

12、算法不容易陷入局部问题，适应性函数也不需要引导，因此基于遗传算法的学习算法适用的神经元激活函数类型更广。提高了快速BP算法的教学速度，缩短了收敛时间。5.1例：利用遗传算法优化BP神经网络诊断癌症样例：样例数据是最差的，包含10个量化要素的平均值、标准偏差和10个量化要素，共30个数据。显然，这30个输入参数彼此之间有一定的关系，并且彼此不独立，因此，为了缩短建模时间并提高建模精度，必须在30个输入参数中筛选导致主要影响因素的参数，以参与最终建模。设计理念：要使用遗传算法优化计算，首先需要将解决方案空间映射到编码空间，并且需要每个编码对应问题的解决方案(染色体或单独)。这里解码长度为30，染色

13、体的每个位置都有输入参数，每个位置都有“1”或“0”，染色体设计为1，参与最终建模，否则不参与。选择测试集数据差异的倒数作为遗传算法的适用性函数。设计阶段：如图2所示：(1)构建单个BP模型为了比较遗传算法优化前后的预测效果，首先利用全部30个输入参数构建BP模型。(2)初始人口生成随机生成n个初始字符串结构数据。每个字符串数据结构都是一个对象，n个对象构成一个群体。遗传算法使用这n个字符串结构作为初始点开始迭代。(3)适宜性函数计算选择测试集数据误差平方数的倒数作为适合性函数包括：样式是测试集中的预测集，测试集中的实际值，n是测试集中的样品数。图2 GA优化BP神经网络设计阶段(4)选择任务

14、选择操作选择比率选择运算符，即选择实体并将其继承到下一代群体的概率与该实体的适合性大小成正比，具体的工作流程如下：计算人口所有适应能力的总和利用常识计算群体内个别个体的相对适合性，将其选为个体，计算遗传给下一代的概率。=1，2，n通过模拟轮盘操作，产生(0，1)之间的随机数，决定每个物体被选择的次数。很明显，适应能力越大的个体，被选择的次数越多，其遗传基因在群体中就越大。(5)交叉操作对于输入引数的压缩缩减维度，交集作业使用具有以下作业程序的最简单单点交集运算子：首先将人口中的个人分成两个随机对。初始人口大小为20，因此有10个相互配对的个别群体。对于每对配对的每对，随机选择特定基因后的位置作

15、为交点。对于每对相互配对的夫妇，根据确定的交叉位置，交换两个个体的部分染色体，产生两个新的个体。(6)转移作业对于输入参数的压缩降维，转换操作使用以下最简单的单点转换运算符：随机生成变异点。根据波动点的位置，改变相应基因座的基因值，变异后“1”变为“0”或“0”。(7)优化结果输出迭代进化后，如果满足迭代结束条件，则输出的最后一个总体对应于问题的最佳解决方案或最近的解决方案，即过滤后的最具代表性的输入参数组合。(8)优化BP模型构建根据优化计算的结果，系统将选择与建模中涉及的输入参数相对应的培训集和测试提取数据，使用BP神经网络重新构造模型进行仿真测试，以执行结果分析。MATLAB程序如下所示

16、，程序运行的结果如图3所示。%遗传算法的优化计算输入自变量降维清除%环境变量Clear allClcWarning off%全局变量声明global p _ train t _ train p _ testt _ test mint maxt S1S=30S1=50获取%数据加载数据。垫子a=randperm(569)；train=data(a(1336500)，)；Test=data (a (50: end)，)；%培训数据P_train=Train(: end)；T_train=Train(:2)；%测试数据P_test=Test(: end)；T_test=Test(:2)；显示%实验条

17、件Total_B=length(find(data(:2)=1)；Total_M=length(find(data(:2)=2)；count _ B=length(find(T _ train=1)；count _ M=length(find(T _ train=2)；number _ B=length(find(T _ test=1)；number _ M=length(find(T _ test=2)；Disp(实验条件：)Disp(总案例数：num 2 str(569)。即可从workspace页面中移除物件。即可从workspace页面中移除物件。阳性：num2str(total_B)。即可从workspace页面中移除物件。即可从workspace页面中移除物件。恶意：num 2 str(total _ M)；Disp(培训集案例总数：num 2 str(500)。即可从workspace页面中移除物件。即可从works