遗传算法综述(共14页).doc

《遗传算法综述(共14页).doc》由会员分享，可在线阅读，更多相关《遗传算法综述(共14页).doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精选优质文档-倾情为你奉上遗传算法综述史俊杰摘要：遗传算法来源于进化论和群体遗传学，是计算智能的重要组成部分，正受到众多学科的高度重视。本文主要回顾了遗传算法的起源和发展历程，并对遗传算法的基本原理及特点作了简要阐述。进一步指出了遗传算法存在的问题及相应的改进措施，讨论了遗传算法在实际中的应用，并对遗传算法的未来的发展进行了探讨。关键字：遗传算法，适应度函数，神经网络1.遗传算法的起源遗传算法(Genetic Algorithm，GA)是模拟自然界生物进化机制的一种算法，即遵循适者生存、优胜劣汰的法则，也就是寻优过程中有用的保留，无用的则去除。在科学和生产实践中表现为，在所有可能的解决方法中找

2、出最符合该问题所要求的条件的解决方法，即找出一个最优解。这种算法是1960年由Holland提出来的，其最初的目的是研究自然系统的自适应行为，并设计具有自适应功能的软件系统。2.遗传算法的发展过程从二十世纪六十年代开始，密切根大学教授Holland开始研究自然和人工系统的自适应行为，在这些研究中，他试图发展一种用于创造通用程序和机器的理论。在六十年代中期至七十年代末期，Bagly发明“遗传算法”一词并发表了第一篇有关遗传算法应用的论文。1975年竖立了遗传算法发展史上的两块里程碑，一是Holland出版了经典著作“Adaptation in Nature and Artifieial Syst

3、em”，二是Dejong完成了具有指导意义的博士论文“An Analysis of the Behavior of a Class of Genetie Adaptive System”。进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、机器学习和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科学新范式得到学术界普遍认同，如广义进化综合理论。由于遗传算法能有效地求解属于、NPC类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视。3.遗传算法特点遗传算法作

4、为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法具有进化计算的所有特征，同时又具有自身的特点：（1）搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度。（3）遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力。（4）遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性。（5）遗传算法更适合大规模复杂问题的优化。4.遗传算法研究理论 在自然界，由于组成生物

5、群体中各个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存、优胜劣汰，将要淘汰那些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下，基因会发生突变，产生新基因和生命力更强的新个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优方向进化，遗传算法是真实模拟自然界生物进化机制进行寻优的。在此算法中，被研究的体系的响应曲面看作为一个群体，相应曲面上的每一个点作为群体中的一个个体，个体用多维向量或矩阵来描述，组成矩阵和向量的参数相应于生物种组成染色体的基因，染色体用固

6、定长度的二进制串表述，通过交换、突变等遗传操作，在参数的一定范围内进行随机搜索，不断改善数据结构，构造出不同的向量，相当于得到了被研究的不同的解，目标函数值较优的点被保留，目标函数值较差的点被淘汰。由于遗传操作可以越过位垒，能跳出局部较优点，到达全局最优点。 遗传算法是一种迭代算法，它在每一次迭代时都拥有一组解，这组解最初是随机生成的，在每次迭代时又有一组新的解由模拟进化和继承的遗传操作生成，每个解都有一目标函数给与评判，一次迭代成为一代。典型的算法的流程图如图1所示，步骤有：Step1 初始化：采用随机法生成 个初始串作为初始群体，每个初始串称为一个个体。Step2 计算适应度：根据适应度函

7、数计算第 代种群每个个体的适应值，记具有最高适应值的个体为 。Step3 选择：由父种群采用适应度比例法选出子种群，其中被选中的概率为。Step4 交叉变异：交叉运算，从子种群中以相同的概率选出两个个体，这两个个体之间以事先给定的概率执行重组运算，产生两个新个体，重复这一过程。变异运算根据一定的变异率 Pf随机 地对 一个体的某一位进行翻转，产生一个新的个体，重复这一过程。然后并入Step2中最高适应值的个体最终形成新一代群体记 ：中具有最高适应度的个体为 。Step5 若遗传代数满足终止条件，则停止运算，输出 1作为近似最优个体；否则令 k= k+1转Step2。图1 遗传算法流程图4.1遗

8、传算法的原型John Holland教授通过模拟生物进化过程设计了最初的遗传算法，称之为标准遗传算法。标准遗传算法给出了遗传算法的基本框架，以后对于遗传算法的改进，都是基于此种算法。尽管遗传算法的实现在细节上有所不同，但都具有以下的共同结构：算法迭代更新一个假设池，这个假设池称为群体。在每一次的迭代中，根据适应度函数评估群体中的所有成员，然后从当前群体中用概率方法选取适应度最高的个体产生新一代群体。在这些选中的个体中，一部分保持原样地进入下一代群体，其他的被用作产生后代个体的基础。4.2遗传算法的基本要素 遗传算法的基本要素包括染色体编码方法、适应度函数、运行参数和遗传操作。 其中染色体编码方

9、法是指个体的编码方法，目前包括二进制法、实数法等。二进制法是指把个体编码成为一个二进制串，实数法是指把个体编码成为一个实数串。 适应度函数是指根据目标编写的计算个体适应度值的函数，通过适应度函数计算每个个体的适应度值，提供给选择算子进行选择。 运行参数是遗传算法在初始化时确定的参数，主要包括群体大小M，遗传代数G，交叉概率Pt，和变异概率Pm。 遗传操作是指选择操作、交叉操作和变异操作。 选择是用来确定交叉个体，以及被选个体将产生多少个子代个体。常用的方法有：（1）适应度比例方法，各个个体的选择概率和其适应度值成比例。（2）最佳个体保存方法，把群体中适应度最高的个体不进行配对交叉而直接复制到下

10、一代中。（3）排序选择方法，指在计算每个个体的适应度后，根据适应度大小对群体中个体排序，并把事先设计好的概率表按序分配给个体，作为各自的选择概率。所有个体按适应度排序，而选择概率和适应度无直接关系而仅与序号有关。（4）联赛选择方法，其操作思想是从群体中任意选择一定数目的个体，其中适应度最高的个体保存到下一代。并反复执行，直到保存到的个体数达到预先设定的数目为止。 交叉指把两个父代个体的部分结构加以替换重组而生成新个体的操作。交叉操作的作用是组合出新的个体，是GA 区别于其它进化算法的重要特征，遗传算法中起核心作用的是遗传操作。各种交叉算子都包括两个基本内容：（1）从由选择操作形成的群体中，对个

11、体随机配对并按预先设定的交叉概率来决定每对是否需要进行交叉操作。（2）设定配对个体的交叉点，并对这些点前后的配对个体的部分结构进行相互交换。常用的交叉操作方法有一点交叉、二点交叉、一致交叉、二维交叉、树结构交叉等等。 变异即对群体中个体串的某些基因座上的基因值作变动。变异的目的有两个：（1） 使遗传算法具有局部的随机搜索能力。（2） 保持群体的多样性。 变异算子的操作一般分两步：（1）在群体中所有个体的码串范围内随机确定基因座。（2）以事先设定的变异概率来对这些基因座的基因值进行变异。变异算子有很多方式，如基本变异算子、逆转算子、自适应变异算子等等。5. 遗传算法的应用遗传算法优化BP神经网络

12、 近年来人工神经网络发展迅速，在经济、军事、工业生产和生物医学等领域获得广泛应用，并产生深远的影响。由于学习能力是神经网络中最引人注意的特征，所以在神经网络的发展过程中，学习算法的研究一直占据重要地位，上个世纪80 年代中期出现的 BP（back-propagation）算法，有效地解决了前向多层神经网络地学习问题，从而极大地推动了这一领域的研究工作。但是从本质上讲，BP 算法属于梯度下降算法，不可避免地存在易陷入局部极小、收敛速度慢、误差函数必须可导、网络结构某有成型的理论指导等缺点。由美国密歇根大学的HollandJ。教授发起的遗传算法是一种高效的并行全局搜索算法，该算法具有很好的鲁棒性，

13、在解决全局优化问题方面取得了成功。所以可以将遗传算法应用于神经网络的学习过程中，这样可以避免传统的BP算法容易陷入局部极小的问题，并且由于适应度函数无需可导，因此基于遗传算法的学习算法适应的神经元激活函数类型更广。同时可以提高快 BP 算法的训练速度，降低收敛时间。5.1案例：利用遗传算法优化BP神经网络进行癌症诊断 样本：样本数据为包括十个量化特征的平均值、标准差、和十个量化特征的最坏值，共30个数据。明显，这30个输入自变量相互之间存在一定的关系，并非相互独立，因此，为了缩短建模时间，提高建模精度，有必要将30个输入自变量中起主要影响因素的自变量筛选出来参与最终的建模。 设计思路：利用遗传

14、算法进行优化计算，首先需要将解空间映射到编码空间，每个编码对应问题的一个解（即为染色体或个体）。这里，降编码长度设计为30，染色体的每一位对应一个输入自变量，每一位的基因取值为“1”或“0”，染色体为1，表示参与最终建模，否则，未参与。选取测试集数据均差的倒数作为遗传算法的适应度函数。 设计步骤：如图2所示：（1） 单BP模型建立 为了比较遗传算法优化前后的预测效果，先利用全部的30个输入自变量建立BP模型。（2） 初始种群产生 随机产生N个初始串结构数据，每个串数据结构即为一个个体，N个个体构成了一个种群。遗传算法以这N个串结构作为初始点开始迭代。（3） 适应度函数计算 这里选取测试集数据误

15、差平方和的倒数作为适应度函数为：式中为测试集的预测集，为为测试集的真实值，n为测试集的样本数目。图2 GA优化BP神经网络设计步骤（4） 选择操作 选择操作选用比例选择算子，即个体被选中并遗传到下一代种群中的概率与该个体的适应度大小成正比，具体的操作过程是：计算种群中所有适应度之和利用上式计算种群中各个个体的相对适应度，并以此作为该个体被选中并遗传到下一代种群中的概率。 =1，2，n采用模拟轮盘赌操作，产生（0，1)之间的随机数，来确定各个个体被选中的次数。显然，适应度大的个体，其选择的概率也大，能被多次选中，其遗传基因就会在种群中扩大。（5） 交叉操作 对于输入自变量的压缩降维，交叉操作采用

16、最简单的单点交叉算子，具有操作过程为：先对种群中的个体进行两两随机配对，初始种群大小为20，故有10个相互配对的个体组；对每一对相互配对的个体，随机选取某一基因之后的位置作为交叉点；对每一对相互配对的个体，根据中确定的交叉点位置，相互交换两个个体的部分染色体，产生出两个新个体。（6） 变异操作 对于输入自变量的压缩降维，变异操作采用最简单的单点变异算子，操作过程为：随机产生变异点；根据中的变异点位置，改变其对应的基因座上的基因值，变异后“1”变为“0”或“0”变为“1”。（7） 优化结果输出 经过一次次的迭代进化，当满足迭代终止条件时，输出的末代种群对应的便是问题的最优解或最近解，即筛选出的最

17、具代表性的输入自变量组合。（8） 优化BP模型建立 根据优化计算得到的结果，将选出的参与建模的输入自变量对应的训练集和测试集数据提取出来，利用BP神经网络重新建立模型进行仿真测试，从而进行结果的分析。MATLAB程序如下,程序运行结果如下图3所示：% 遗传算法的优化计算输入自变量降维% 清空环境变量clear allclcwarning off% 声明全局变量global P_train T_train P_test T_test mint maxt S s1S=30;s1=50;% 导入数据load data。mata=randperm(569);Train=data(a(1:500)，:)

18、;Test=data(a(501:end)，:);% 训练数据P_train=Train(:，3:end);T_train=Train(:，2);% 测试数据P_test=Test(:，3:end);T_test=Test(:，2);% 显示实验条件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(

19、find(T_test=2);disp(实验条件为：);disp(病例总数： num2str(569)。 良性： num2str(total_B)。 恶性： num2str(total_M);disp(训练集病例总数： num2str(500)。 良性： num2str(count_B)。 恶性： num2str(count_M);disp(测试集病例总数： num2str(69)。 良性： num2str(number_B)。 恶性： num2str(number_M);% 数据归一化P_train，minp，maxp，T_train，mint，maxt=premnmx(P_train，T_

20、train);P_test=tramnmx(P_test，minp，maxp);% 创建单BP网络t=cputime;net_bp=newff(minmax(P_train)，s1，1，tansig，purelin，trainlm);% 设置训练参数net_bp。trainParam。epochs=1000;net_bp。trainParam。show=10;net_bp。trainParam。goal=0。1;net_bp。trainParam。lr=0。1;net_bp。trainParam。showwindow=0;% 训练单BP网络net_bp=train(net_bp，P_train

21、，T_train);% 仿真测试单BP网络tn_bp_sim=sim(net_bp，P_test);% 反归一化T_bp_sim=postmnmx(tn_bp_sim，mint，maxt);e=cputime-t;T_bp_sim(T_bp_sim1。5)=2;T_bp_sim(T_bp_sim1。5)=2;T_ga_sim(T_ga_sim1。5)=1;result_ga=T_ga_sim T_test;% 结果显示（优化BP网络）number_b_sim=length(find(T_ga_sim=1 & T_test=1);number_m_sim=length(find(T_ga_sim

22、=2 &T_test=2);disp(2)优化BP网络的测试结果为：);disp(良性乳腺肿瘤确诊： num2str(number_b_sim)。 误诊： num2str(number_B-number_b_sim)。 确诊率p1= num2str(number_b_sim/number_B*100) %);disp(恶性乳腺肿瘤确诊： num2str(number_m_sim)。 误诊： num2str(number_M-number_m_sim)。 确诊率p2= num2str(number_m_sim/number_M*100) %);disp(建模时间为： num2str(e) s )

23、;图3 程序结果图由此可得到结论：遗传算法优化BP神经网络的识别率比单纯的BP神经网络高，而且识别速度较快。6. 遗传算法的改进与未来6.1遗传算法的改进虽然遗传算法已经取得了广泛的应用，但存在着收敛速度慢及算法稳定性差等缺陷。用遗传算法进行路径规划时，随机产生初始种群，为了避免陷入局部极值点，种群数量要达到一定的规模。但种群规模大会导致搜索空间较大，删除冗余个体的能力较差，大大影响路径规划的速度。特别在环境较为复杂的情形下，这种缺点就更加明显。针对标准遗传算法的不足，在吸收前人研究成果的基础上，对于遗传算法的求解过程，我们提出了如下改进措施与步骤:(1)人工方法产生初始群体先将优化问题的初始

24、解转化为个体，然后在问题的解空间中用人工方法产生初始种群的其它个体，使初始群体的个体模式阶次较高、模式数目较大，具有多样性。这样通过适当选择字符串长度和群体规模，可以在开始的几代内找到各极值点所在的区域，加快搜索速度。(2)上代群体的处理 对于上代群体，计算其个体的适应度，判别其是否满足终止条件。如果满足终止条件，停止遗传操作，输出最优解。否则，将上代群体全部放入中间群体，并对上代群体独立进行优选父代交换和大突变操作。(3)优选父代交换 优选父代交换的主要思想是指在进行交换操作时，提高父代的质量，即选择较优的父代个体参与交换。具体过程是:从上代群体中随机选取两个个体，然后比较其适应度，保留适应

25、度大的个体，再从上代群体中随机选取两个个体，同样保留适应度大的个体，以保留下来的两个个体作为父代个体。产生0，1之间均匀分布的随机数s，如果sPc，则两者进行交换，将交换后的两个新个体加入到中间群体，否则直接将保留下来的两个个体加入到中间群体。(4)大突变操作 理论上，遗传算法的突变操作可以产生新个使算法跳出“早熟”。但为了保持算法的稳定性，突变操作的突变率通常取得很小，单靠传统的突变操作需要很多代才能变异出一个不同于其它个体的新个体。大突变操作的思想是:对上代群体，以一个远大于通常的突变概率的概率进行一次突变操作，并将突变后产生的新个体加入到中间群体。大突变操作能够随机、独立地产生许多新个体

26、，从而能始终保持群体的多样性，使群体脱离“早熟”。(5)基于Metropolis判别准则的复制策略 对于中间群体，运用基于Metropolis判别准则的复制策略，产生下一代群体。基于Metropolis判别准则的复制策略分为两步:a.实施最优保留策略将中间群体中性能最好的个体无条件地复制到下一代群体中，这样就会保留中间群体中的最好解，使遗传算法可以以概率1收敛到全局最优解，保证了算法的收敛。b.实施Metropolis判别准则的复制策略在中间群体中随机选取个体i和j，i和j竞争进入下一代群体的准则采用Metropolis判别准则:产生0，1之间均匀分布的随机数s，如果s=min(1，exp(-

27、 (f(i) -f(j)/T)(式中，f(i)，f(j)分别为个体i和j的适应度，T为控制参数)，则个体i复制到下一代群体，否则个体j复制到下一代群体。改进后遗传算法的基本流程如图4所示。图4 改进的遗传算法6.2遗传算法的未来遗传算法的未来发展还有很大的空间，我们可以探索研究以下几个方面：(1)基于遗传算法的机器学习：这一新的研究方向把遗传算法从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生产功能崭新的机器学习算法。(2)遗传算法与其他计算智能方法的相互渗透和结合：遗传算法正日益和神经网络、模糊推理以及混沌理论等其他职能计算方法相互渗透和结合，以到达取长补短的作用。(3)并行处理遗传

28、算法：并行处理的遗传算法的研究不仅是遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的，遗传算法在操作上具有高度的并行性。(4)遗传算法与人工生命的渗透：基于遗传算法的进化模型是研究人工生命现象的基础。参考文献1席裕庚,柴天佑,恽为民.遗传算法综述J.控制理论与应用.1996(13)06:697-7082常洪江.遗传算法综述J.电脑学习.2010(06)3:115-1163李华昌,谢淑兰，易忠胜.遗传算法的原理与应用J.矿冶.2005(14)01:87-904徐宗本,陈志平,章祥荪.遗传算法基础理论研究的新近发展J.数学进展. 2004(29)2: 97-1145李伟超,宋大猛,陈斌.基于遗传算法的人工神经网络J.计算机工程与设计.2006(27)2: 316-3186李敏强，徐博艺，寇纪淞.遗传算法与神经网络的结合J.系统工程理论与实践.1999(02) 2:65-697韩万林，张幼蒂.遗传算法的改进J.中国矿业大学学报.2000(29)1:102-105专心-专注-专业