遗传算法综述

遗传算法综述史俊杰摘要：遗传算法来源于进化论和群体遗传学，是计算智能的重要组成部分，正受到众多学科的高度重视。本文主要回顾了遗传算法的起源和发展历程，并对遗传算法的基本原理及特点作了简要阐述。进一步指出了遗传算法存在的问题及相应的改进措施，讨论了遗传算法在实际中的应用，并对遗传算法的未来的发展进行了探讨。关键字：遗传算法，适应度函数，神经网络1.遗传算法的起源遗传算法(GeneticAlgorithm，GA)是模拟自然界生物进化机制的一种算法，即遵循适者生存、优胜劣汰的法则，也就是寻优过程中有用的保留，无用的则去除。在科学和生产实践中表现为，在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法，即找出一个最优解。这种算法是1960年由Holland提出来的，其最初的目的是研究自然系统的自适应行为，并设计具有自适应功能的软件系统。2.遗传算法的发展过程从二十世纪六十年代开始，密切根大学教授Holland开始研究自然和人工系统的自适应行为，在这些研究中，他试图发展一种用于创造通用程序和机器的理论。在六十年代中期至七十年代末期，Bagly发明“遗传算法”一词并发表了第一篇有关遗传算法应用的论文。1975年竖立了遗传算法发展史上的两块里程碑，一是Holland出版了经典著作“AdaptationinNatureandArtifieialSystem”，二是Dejong完成了具有指导意义的博士论文“AnAnalysisoftheBehaviorofaClassofGenetieAdaptiveSystem”。进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、机器学习和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科学新范式得到学术界普遍认同，如广义进化综合理论。由于遗传算法能有效地求解属于、NPC类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视。3.遗传算法特点遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法具有进化计算的所有特征，同时又具有自身的特点：（1）搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度。（3）遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力。（4）遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性。（5）遗传算法更适合大规模复杂问题的优化。4.遗传算法研究理论在自然界，由于组成生物群体中各个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存、优胜劣汰，将要淘汰那些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下，基因会发生突变，产生新基因和生命力更强的新个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优方向进化，遗传算法是真实模拟自然界生物进化机制进行寻优的。在此算法中，被研究的体系的响应曲面看作为一个群体，相应曲面上的每一个点作为群体中的一个个体，个体用多维向量或矩阵来描述，组成矩阵和向量的参数相应于生物种组成染色体的基因，染色体用固定长度的二进制串表述，通过交换、突变等遗传操作，在参数的一定范围内进行随机搜索，不断改善数据结构，构造出不同的向量，相当于得到了被研究的不同的解，目标函数值较优的点被保留，目标函数值较差的点被淘汰。由于遗传操作可以越过位垒，能跳出局部较优点，到达全局最优点。遗传算法是一种迭代算法，它在每一次迭代时都拥有一组解，这组解最初是随机生成的，在每次迭代时又有一组新的解由模拟进化和继承的遗传操作生成，每个解都有一目标函数给与评判，一次迭代成为一代。典型的算法的流程图如图1所示，步骤有：Step1初始化：采用随机法生成0N个初始串作为初始群体，每个初始串称为一个个体。Step2计算适应度：根据适应度函数计算第k代种群每个个体的适应值)(ikXfkNi,...,2,1，记具有最高适应值的个体为*kX。Step3选择：由父种群kNkkXX,...,1采用适应度比例法选出子种群kNkkXX'1',...,，其中被选中的概率为kNiikikikNiXfXfXPk,...1,)()()(1。Step4交叉变异：交叉运算，从子种群中以相同的概率选出两个个体，这两个个体之间以事先给定的概率执行重组运算，产生两个新个体，重复这一过程。变异运算根据一定的变异率P~f随机地对一个体的某一位进行翻转，产生一个新的个体，重复这一过程。然后并入Step2中最高适应值的个体*kX最终形成新一代群体1111,...,kNkkXX记：1111,...,kNkkXX中具有最高适应度的个体为*1kX。Step5若遗传代数满足终止条件，则停止运算，输出1作为近似最优个体；否则令k=k+1转Step2。图1遗传算法流程图4.1遗传算法的原型JohnHolland教授通过模拟生物进化过程设计了最初的遗传算法，称之为标准遗传算法。标准遗传算法给出了遗传算法的基本框架，以后对于遗传算法的改进，都是基于此种算法。尽管遗传算法的实现在细节上有所不同，但都具有以下的共同结构：算法迭代更新一个假设池，这个假设池称为群体。在每一次的迭代中，根据适应度函数评估群体中的所有成员，然后从当前群体中用概率方法选取适应度最高的个体产生新一代群体。在这些选中的个体中，一部分保持原样地进入下一代群体，其他的被用作产生后代个体的基础。4.2遗传算法的基本要素遗传算法的基本要素包括染色体编码方法、适应度函数、运行参数和遗传操作。其中染色体编码方法是指个体的编码方法，目前包括二进制法、实数法等。二进制法是指把个体编码成为一个二进制串，实数法是指把个体编码成为一个实数串。适应度函数是指根据目标编写的计算个体适应度值的函数，通过适应度函数计算每个个体的适应度值，提供给选择算子进行选择。运行参数是遗传算法在初始化时确定的参数，主要包括群体大小M，遗传代数G，交叉概率Pt，和变异概率Pm。遗传操作是指选择操作、交叉操作和变异操作。选择是用来确定交叉个体，以及被选个体将产生多少个子代个体。常用的方法有：（1）适应度比例方法，各个个体的选择概率和其适应度值成比例。（2）最佳个体保存方法，把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。（3）排序选择方法，指在计算每个个体的适应度后，根据适应度大小对群体中个体排序，并把事先设计好的概率表按序分配给个体，作为各自的选择概率。所有个体按适应度排序，而选择概率和适应度无直接关系而仅与序号有关。（4）联赛选择方法，其操作思想是从群体中任意选择一定数目的个体，其中适应度最高的个体保存到下一代。并反复执行，直到保存到的个体数达到预先设定的数目为止。交叉指把两个父代个体的部分结构加以替换重组而生成新个体的操作。交叉操作的作用是组合出新的个体，是GA区别于其它进化算法的重要特征，遗传算法中起核心作用的是遗传操作。各种交叉算子都包括两个基本内容：（1）从由选择操作形成的群体中，对个体随机配对并按预先设定的交叉概率来决定每对是否需要进行交叉操作。（2）设定配对个体的交叉点，并对这些点前后的配对个体的部分结构进行相互交换。常用的交叉操作方法有一点交叉、二点交叉、一致交叉、二维交叉、树结构交叉等等。变异即对群体中个体串的某些基因座上的基因值作变动。变异的目的有两个：（1）使遗传算法具有局部的随机搜索能力。（2）保持群体的多样性。变异算子的操作一般分两步：（1）在群体中所有个体的码串范围内随机确定基因座。（2）以事先设定的变异概率来对这些基因座的基因值进行变异。变异算子有很多方式，如基本变异算子、逆转算子、自适应变异算子等等。5.遗传算法的应用——遗传算法优化BP神经网络近年来人工神经网络发展迅速，在经济、军事、工业生产和生物医学等领域获得广泛应用，并产生深远的影响。由于学习能力是神经网络中最引人注意的特征，所以在神经网络的发展过程中，学习算法的研究一直占据重要地位，上个世纪80年代中期出现的BP（back-propagation）算法，有效地解决了前向多层神经网络地学习问题，从而极大地推动了这一领域的研究工作。但是从本质上讲，BP算法属于梯度下降算法，不可避免地存在易陷入局部极小、收敛速度慢、误差函数必须可导、网络结构某有成型的理论指导等缺点。由美国密歇根大学的HollandJ。教授发起的遗传算法是一种高效的并行全局搜索算法，该算法具有很好的鲁棒性，在解决全局优化问题方面取得了成功。所以可以将遗传算法应用于神经网络的学习过程中，这样可以避免传统的BP算法容易陷入局部极小的问题，并且由于适应度函数无需可导，因此基于遗传算法的学习算法适应的神经元激活函数类型更广。同时可以提高快BP算法的训练速度，降低收敛时间。5.1案例：利用遗传算法优化BP神经网络进行癌症诊断样本：样本数据为包括十个量化特征的平均值、标准差、和十个量化特征的最坏值，共30个数据。明显，这30个输入自变量相互之间存在一定的关系，并非相互独立，因此，为了缩短建模时间，提高建模精度，有必要将30个输入自变量中起主要影响因素的自变量筛选出来参与最终的建模。设计思路：利用遗传算法进行优化计算，首先需要将解空间映射到编码空间，每个编码对应问题的一个解（即为染色体或个体）。这里，降编码长度设计为30，染色体的每一位对应一个输入自变量，每一位的基因取值为“1”或“0”，染色体为1，表示参与最终建模，否则，未参与。选取测试集数据均差的倒数作为遗传算法的适应度函数。设计步骤：如图2所示：（1）单BP模型建立为了比较遗传算法优化前后的预测效果，先利用全部的30个输入自变量建立BP模型。（2）初始种群产生随机产生N个初始串结构数据，每个串数据结构即为一个个体，N个个体构成了一个种群。遗传算法以这N个串结构作为初始点开始迭代。（3）适应度函数计算这里选取测试集数据误差平方和的倒数作为适应度函数为：niiittSEXf12ˆ11)(式中itˆ为测试集的预测集，it为为测试集的真实值，n为测试集的样本数目。图2GA优化BP神经网络设计步骤（4）选择操作选择操作选用比例选择算子，即个体被选中并遗传到下一代种群中的概率与该个体的适应度大小成正比，具体的操作过程是：①计算种群中所有适应度之和)(1rnkkXfF②利用上式计算种群中各个个体的相对适应度，并以此作为该个体被选中并遗传到下一代种群中的概率。FXfpkk)(k=1，2，···，n③采用模拟轮盘赌操作，产生（0，1)之间的随机数，来确定各个个体被选中的次数。显然，适应度大的个体，其选择的概率也大，能被多次选中，其遗传基因就会在种群中扩大。（5）交叉操作对于输入自变量的压缩降维，交叉操作采用最简单的单点交叉算子，具有操作过程为：①先对种群中的个体进行两两随机配对，初始种群大小为20，故有10个相互配对的个体组；②对每一对相互配对的个体，随机选取某一基因之后的位置作为交叉点；③对每一对相互配对的个体，根据②中确定的交叉点位置，相互交换两个个体的部分染色体，产生出两个新个体。（6）变异操作对于输入自变量的压缩降维，变异操作采用最简单的单点变异算子，操作过程为：①随机产生变异点；②根据①中的变异点位置，改变其对应的基因座上的基因值，变异后“1”变为“0”或“0”变为“1”。（7）优化结果输出经过一次次的迭代进化，当满足迭代终止条件时，输出的末代种群对应的便是问题的最优解或最近解，即筛选出的最具代表性的输入自变量组合。（8）优化BP模型建立根据优化计算得到的结果，将选出的参与建模的输入自变量对应的训练集和测试集数据提取出来，利用BP神经网络重新建立模型进行仿真测试，从而