遗传算法综述

遗传算法综述摘要：20世纪70年代初，Holland首先提出了遗传算法。由于遗传算法是全新的模拟生物演化的仿生优化算法以及遗传算法既适合无表达又适合有表达的任何类函数，因此己成为许多学科共同关注的热点研究领域。本文详细阐述了遗传算法的起源、发展过程以及对标准遗传算法的基本原理、实现步骤、流程和特点。本文还对遗传算法收敛性进行分析，最后对遗传算法的应用领域和研究方向进行了概述。关键字：遗传算法；实现；分析Abstract：ThegeneticalgorithmispresentedbyHollandin1970s.Thegeneticalgorithmhasbecomethefocusofmanysubjects,forgeneticalgorithmisanewoptimalalgorithmtosimulatethebiologicalevolution,anditsuitsbothtofunctionswithoutexpressionsandtofunctionswithexpression.Thispaperdescribestheoriginofthegeneticalgorithm,aswellasthedevelopmentofthestandardgeneticalgorithmtothebasictenetsofimplementationsteps,processesandcharacteristics.Thispaperalsoconvergenceofthegeneticalgorithmanalysis,thefinalapplicationofgeneticalgorithmsandresearchareasofthedirectioninwhichoutlined.Keywords：GeneticAlgorithm；implement；analysis遗传算法的起源遗传算法是模拟生物在自然环境力的遗传和进化过程而形成的一种自适应全局优比概率搜索算法［1］。它最早由美国密执安大学Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架［2］。遗传算法的发展与现状遗传算法创建的目的是在人工适应系统中设计一种基于自然演化原理的搜索机制。Holland不仅设计了遗传算法的模拟与操作原理，而且对遗传算法的搜索机理进行了理论分析，为遗传算法的发展奠定了初步的理论基础。在Holland之后，遗传算法经历了一个相对平稳的发展时期。但到20世纪80年代末到至今，遗传算法已成为信息科学、计算机科学、运筹学、应用数学和人工生命等诸多学科所共同关注的热点研究领域。目前，遗传算法的研究分为三个方面。一是对遗传算法本身的改进；二是遗传算法的数学理论研究；三是遗传算法的应用。遗传算法的理论研究比以前有了一些新的进展，特别是在遗传算法一般模型的收敛性理论方面已得到了一系列的结论，这因为采用了新的研究方法即迭代方法。遗传算法的应用己几乎渗透到从工程到社会科学的诸多领域。对遗传算法的改进有很多种方法。有与其它优化方法如神经网络、模糊系统等相结合而产生的混合遗传算法。神经网络和遗传算法现有的结合工作主要是利用遗传算法辅助设计神经网络。或将神经网络结合到遗传算法中，以改进遗传算法的收敛性。一种融和神经网络的改进遗传算法［4］，是将神经网络和遗传操作相结合，具体方法是在个体遗传操作后，将新一代个体与相应父代个体组成训练模式进行神经网络学习，若训练成功，则由遗传算法产生少量个体，从神经网络抽取多个个体，若训练失败，则反之。另一方面，将遗传算法用于神经网络的训练。神经网络的学习包含了两个优化过程，分别是网络连接权重的优化和网络拓扑结构的优化。优化连接权重最著名的方法是反向传播法。但反向传播法算法的最大弱点是局部极小问题和无法学习网络拓扑结构。作为一种通用性和全局性良好的优化技术，遗传算法用于神经网络的训练就是很自然的事情。遗传算法用于神经网络的学习可分为三个不同的层次：连接权重的学习、网络拓扑的学习以及网络学习规则的学习。遗传算法可用于前向网络、径向基网络、Kohonen特征映射及Recurrent网络等各种人工神经网络的训练与设计中。采用遗传算法学习神经网络连接权，不仅发挥神经网络所具有的广泛映射能力，而且由于采用遗传算法，从而使网络具有快速收敛及增强式学习性能。模糊系统与遗传算法的结合工作是遗传算法已成功地用于隶属函数形状与参数的优化，系统相关权重的优化以及推理规则的选取。另外，模糊集技术也被用于遗传算法，以达到改进遗传算法的目的。机器学习与遗传算法相结合，把遗传算法用于机器学习产生了分类系统，并应用于人工生命、视觉系统的控制等方面。基于小生境技术的遗传算法［5］，采用神经网络方法将每个个体进行聚类分行，将解空间分为几个种群，选取平均适应度较大的若干种群建立为小生境，然后运用局部搜索方法产生新个体，最后将新旧个体进行遗传操作得到新一代群体。压缩遗传算法［6］，该算法将群体表示为解集上的概率分布。它独立处理每个基因并且比简单遗传算法要求更少的内存。这项研究为遗传算法引入了新的思想，使人们对标准遗传算法的复杂动态特性有了更多的了解，并为设计更高效的遗传算法打下了基础。运用自然鲍尔温效应［7］增强标准遗传算法的性能，并运用人工神经网络储存种群进化历史。标准遗传算法3.1生物学的基本概念与术语为了便于理解遗传算法，下面给出几个生物学的基本概念与术语［3］。适者生存：在算法停止时，最优目标值的解被保留的可能性最大。染色体(chromosome)：由多个基因组成，染色体所携带的遗传信息的全体称为一个基因组，是遗传物质的主要载体。对应目标函数解的编码(字符串、向量等)，也称染色体为染色体个体。基因(gene):或称为遗传因子。是DNA或RNA长链结构中占有一定位置的基本遗传单位。对应解的字符串编码中的每一个字符。个体(individual)：指染色体带有特征的实体，对应目标函数的解。群体：选定的一组解（群体的大小为群体中解的个数）。种群：个体的集合称为种群，也称作染色体群。是根据适应函数值选取的一组解。适应度（fitness）：是度量某个物种对于生存环境的适应程度，对应适应函数值。复制（reproduction）：遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。交叉（crossover）:在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组recombination，俗称“杂交”即通过交叉原则产生一组新解的过程。突变（mutation）:在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状，对应编码的某一个分量发生变化的过程。3.2标准遗传算法的基本原理Holland的经典遗传算法通常称为标准遗传算法［8］。标准遗传算法是一种由一个种群（或称染色体群）通过“自然选择”［9］的机制转化成为另一个种群的方法。在这里，“自然选择”是由遗传学中“选择”、“交叉”和“突变”几种作用共同完成的。称一个解的编码为一个染色体，组成编码的元素为基因。例如若解的编码用一个二进制串表示，则“基因”是指一位二进制代码（0或1）。编码的目的是用于优化问题解的表现形式和便于在遗传算法中计算。选择的作用是从种群中选出可以繁殖后代的个体，一般总是保证当前种群中具有较高适应值的个体以较大的概率产生出更多的后代。交叉作用用于交换两个编码之间的组成部分而达到产生下一代的目的。突变作用是指改变个体（染色体）上某一位置基因的值。标准遗传算法与其它启发式方法顺序搜索解空间的工作方式不同，标准遗传算法采用种群作为工作单元，使用模仿生物进化的适者生存原则指导搜索并改进目标，种群由代表个体的定长字符串组成，每个个体的质量通过依赖于问题目标函数的适应值函数来进行评估，然后，对种群模仿生物进化的规律，实施三种遗传操作，对应于使用3个基本算子：选择、交叉和变异。种群经过这3个基本算子的优化处理，从种群产生出新的优化了一代（即新的种群），增加找到全局最优解的可能性。经过这样一代代地不断进化，择优汰劣，最后得出非常优秀的群体和个体，从而得到问题的最优解。

3.3标准遗传算法实现步骤对于一个给定的优化问题，目标函数Maxf(x,y,z), (x,yz) ,FwR其中(x,y,z)为自变量，Q是(x,y,z)的定义域，x,y,z可以是数值，也可以是符号。函数值f是实数。f为解空间(x,y,z)WQ到实数域FwR的一种映射。下面是用标准遗传算法求解此问题的步骤［10］。3.3.1选择编码方式和编码遗传算法在求解之前，要将解以字符串的形式表达，也就是要将待求解问题的所有参数编码(为一定长的字符串)，编码方式［11］有多种，如二进制编码、Gray编码、动态编码、实数编码、有序串编码、结构式编码等,根据优化问题选择合适的编码方式。常使用的编码方式主要是二进制码［12］，这里我们选择二进制编码。二进制编码也就是一个由｛0,1｝组成的二进制串。设需求解的未知参数xW［a,b］,x对应的二进制编码的串长取决于x的精度，如果设定求解精确到n位小数，此时若有2m-1<(b-a)10n<2m则编码的二进制串长至少需要m位。将一个二进制串(bm1bm2……b0)转化为区间［a,b］内对应的实数值x，采取以下两步：(1)计算二进制串(bm-1bm-2……b0)对应的10进制数：(b b b)=(旷b2i) =x'm-1m-2 02i10i=0⑵二进制串(bm-1bm-2……b0)对应区间［a,b］内的实数值x按以下公式计b-a2b-a2m—12m—1其中m是编码的二进制串长。

3.3.2产生初始种群t=0时，由计算机随机产生N个初始字符串［13］，每个字符串称为一个个体，这N个个体就构成了一个群体p(0)(称为初始群体)。种群p(t)代表优化问题的一些可能解的集合。群体中个体的数目称为群体的大小。群体的大小可根据优化问题事先设定，如果事先设定群体的大小为N,则由计算机随机产生N个初始字符串。一般来说，初始群体p(t)的素质很差，遗传算法从初始群体出发，即从这N个字符串作为初始点开始迭代计算。模拟进化过程，择优汰劣，最后得出非常优秀的群体和个体，满足优化的要求。3.3.3选择适应度函数以评价种群对种群p(t)中每个个体给出评价，评价规则也就是根据优化问题选择适应度函数。如果某个体的适应度函数值越高，表示该个体的适应度越高，如果适应度收敛到某一稳定值，则此稳定值对应所求优化问题的解。一般来说，对于不同的问题，适应度函数的定义方式不同，目的是使适应度越高的个体越接近问题的解。种群进化选择的依据是个体的适应度。常用的适应度函数有以下三种，方法是将目标函数变换成适应度函数。将求解的目标函数直接转化为适应度函数Fit(f(x,y,z))。定义若求目标函数f(x,y,z)的最大值时，则适应度函数Fit(f(x,y,z))=f(x,y,z)。若求目标函数f(x,y,z)的最小值时，则适应度函数Fit(f(x,y,z))=-f(x,y,z)但此方法存在两个问题，其一是由此计算出的适应度函数值有可能为负值，导致选择概率为负，这与概率非负的性质矛盾。其二是若求解函数的函数值范围很广，由种群计算出的平均适应度不能近似反映目标函数的平均值，因而影响算法的性能。根据上面定义适应度函数时存在的问题，对适应度函数的定义作如下改进定义若目标函数f(x,y,z)为最小值问题时，则适应度函数为Fit(f(Fit(f(x,y,z))=c -f(x,y,z)<max0f(x,y,z)<cmaxf(x,y,z)>cmax其中c 是f(x,y,z)的最大估计值，也称c的界线值。maxmax由上式可知，当f(x)<c 时，Fit(f(x,y,z))为c -f(x,y,z)>0,TOC\o"1-5"\h\zmax max:・Fit((x,y,z))^0，V(x,y,z)三Q,所以可保证由适应度定义的选择概率非负。并且由Fit(f(x,y,z))=c -f(x,y,z)，当f(x,y,z)<c 时，max max可知当适应度函数值Fitf(x,y,z))越大，则函数值f(x,y,z)越小。因为适应度越高的个体被选择的概率越大，此时个体对应的函数值越小，所以最后搜索到的最佳个体是函数f(x,y,z)最小值点。同理可对最大值问题给出定义.定义若目标函数f(x,y,z)为最大值问题，则Fit(fFit(f(x,y,z))=f(x,y,z)-c.min0f(x,y,z)>cminf(x,y,z)<cmin其中c.为f(x,y,z)的最小值估计，也称c.为界限值这种方法通常称为“界限构造法”此方法的问题是界限值c，c.maxmin预先难以估计以及估计精确。c.依据同样的思路，对适应度函数给出另一种定义定义若目标函数f(x,y,z)为最小值问题，则适应度函数(公式1)Fit(fFit(f(x,y,z))=11+C+f(x,y,z)c>0,c+f(x,y,z)>0若目标函数f(x,y,z)为最大值问题，则适应度函数(公式2)Fit(fFit(f()x,y,z)=11+C—f(x,y,z)c>0,c-f(x,y,z)>0其中If(x,y,z)IWc,c是f(x,y,z)的最小上界。c是预先给定的目标函数f(x,y,z)的界限的估计值。从上公式1可知，若适应度函数值Fitf(x,y,z))越高，则函数值f(x,y,z)越小，所以，最后搜索到的最佳个体是目标函数f(x,y,z)的最小值。从上面公式2可知，若适应度函数值Fitf(x,y,z))越高，则函数值f(x,y,z)越大，所以最后搜索到的最佳个体是目标函数f(x,y,z)的最大值。一般来说，适应度函数的设计主要满足以下条件：单值、连续、非负、最大化。这个条件可通过上面适应度函数的定义来理解。合理、一致性。适应度值应能反映解的优劣程度，这一点往往难以衡量。计算量小。适应度函数的设计应尽可能简单，以降低计算成本。通用性强，对某类具体问题，设计的适应度函数可以通用。3.3.4选择(或复制)选择是指从大小为N的种群p(t)中随机选择出N=2M个个体，组成M对个体，用于繁殖后代，若以概率1交配，则产生N个新的个体构成新的下一代种群p(t+l)。一个由N个个体组成的种群，这其中哪个个体被保留(即复制)下来用以繁殖后代，哪个被淘汰，是根据对它们的各自的适应度函数值来决定。个体的适应度函数值大，说明其对环境的适应能力强，它也就有更多的机会被保留下来用以复制后代。反之，则其被淘汰。选择是遗传算法的关键，它体现了自然界中适者生存的思想。具体选择时，为了体现这个思想，选择个体的概率定义为正比于个体的适应值。从N个个体组成的种群中选出适应度高的个体用于繁殖后代，分为两步来实现。第一步确定个体选择概率的定义方法。常用的定义方法有两种［⑶。第二步确定选择方法。选择方法有多种方式，常用的有轮盘赌选择法［⑶。个体选择概率常用的定义方法有如下两种：按比例的适应度分配定义设时刻t种群p(t)大小为N,个体i对应的适应度函数值为f个体i对应的选择概率为从，则 1fk

P= 匚,i=1,……,Nii=1其中k三1,k是比率参数，可根据优化问题预先设定i=1,…,N。称此方法为按比例的适应度分配。基本排序的适应度分配基于排序的适应度分配是对种群中每个个体按适应度函数值从小到大排序记为1至N,此时个体i的选择概率P=^—,i=1,……,Ni=1基于排序的适应度分配的好处有两个：因为VigN,i>0,「.选择概率p>0。避免了按比例的适应度分配i方法中。若目标函数值为负值，需对其作变换，以保证适应度函数值$0。当选择压力(即最佳个体选中的概率与平均选中概率的比值)太小时，即最佳个体被选中的可能性太小时，会产生过早收敛。过早收敛是指

遗传算法在执行过程中会出现群体中的个体过早地在一个非最优点上达到完全相同或接近完全相同的现象。一旦出现该现象，利用遗传算法就不能求得问题的全域最优解。排序方法避免了这个问题，因为排序方法是以个体的序号作为适应度值，选择概率定义为正比于个体适应度(即个体序号)，因此排序方法实际上是引入了种群均匀尺度，使搜索不会过早地陷入局部搜索，避免过早收敛的发生。排序方法比比例方法表现出更好的鲁棒性，不失为一种好的选择方法。下面计算个体i产生下一代的个体数目D(i)[14]。定理设种群p(t)的大小为N,个体i的适应度为片，个体选择概率i1=1,n,则个体产生下一代个体数目i1=1,n,则个体产生下一代个体数目D(i)=1兰Ni=1推论1如果个体i的适应度f为平均适应度f，则此个体i产生下一代的个体数D(i)=1。推论2新生下一代种群p(t+l)的个体总数N仝f。i=1f3.3.5交叉(基因重组)对通过选择操作而得到的新一代用于繁殖的种群p(t+l)中的每一对个体，根据交叉概率pc决定是否交叉产生两个新的后代，若决定交叉，则c随机地选定一个位置n(1WnWm),m是基因串即个体的长度。将两个个体在该位置上交叉互换右端(或左端)的基因串，得到两个后代。如两个个体(或称染色体)分别为100|00100和111|11111，随机选定的位置是第三位，交换第三位右端的基因串，得到100|11111和111|00100此交叉方法称为单点交叉。交叉操作粗略地模拟了两个单倍体生物进行繁殖时染色体(即个体)的配对过程。具体方法是首先把选择出的N个个体自由排列，这样可以得到N对2个体组合，对于每一对组合根据给定的交叉率Pc进行单点交叉，也就是c说，并不是种群中每对个体（字符串）都发生交叉。若交叉率越大，交叉操作发生的可能性越大，产生交叉操作的个体就越多，因而得到的新个体也就多些。交叉点的位置随机选取，交叉的目的是使来自父代的个体组合到一起以产生更优良的个体。交叉实质上具有破坏性，但正因为此破坏性，才可能产生新品种的优良个体，促进搜索全局解空间，而不陷于局部解空间，避免过早收敛的发生。交叉率的选择决定了交叉操作的频率，频率越高，可以越快地收敛到最有希望的最优解区域。因此一般选取较大的交叉率，但若频率太高也可能导致过早收敛。交叉率一般取值0.4~0.9。除单点交叉外，交叉算子还有二点交叉、多点交叉、均匀交叉、匹配交叉、顺序交叉、循环交又、洗牌交叉、缩小代理交叉等。3.3.6突变从群体p（t+l）中随机选取若干个体，对于选中的个体的每一个基因，按一定的突变概率pm决定是否产生变异。若决定变异，则在该位进行取m反运算，即由1〜6,或由o〜1。遗传算法的搜索能力主要是由选择和交叉赋予的，突变为新个体的产生提供了机会，有利用保持种群的多样性。因此突变算子能保证算法能搜索到问题解空间的每一点，从而使算法具有全局最优，避免过早收敛的发生。虽然选择复制和交叉操作可以产生新的基因串（染色体），但是不能产生新的基因。如果所有基因串中某一位置的基因都相同，则这一基因所表征的特性就永远不会改变。变异算子的引入打破了僵局，但突变率（或步长）不能取得太大，如果突变率大于6.5，遗传算法就退化为随机搜索，会引起不稳定，突变一般是以较小的概率进行，突变率一般取6.661~6.1。突变操作除了是对基因串的某一位基因作取反运算外，也可采用更复杂的算子，如逆转算子、自适应变异算子等［15］。标准遗传算法的过程［16］见图3.1。位串 适应值排序1101101101121100011100301110101014位串 适应值排序1101101101121100011100301110101014011001001038.3343.7254.5134.64图3.1标准遗传算法的过程3.4标准遗传算法的流程标准遗传算法的流程分为以下6个步骤：随机生成N=2M个长度为m的字符串(或个体)，组成初始群体。将种群中的每个字符串代入适应度函数，计算适应度。判断是否满足终止条件，若是，则适应度值最大的字符串对应的候选解就是需要的满意解。若否，则步骤4重复下列步骤直至产生了N个后代。选择：根据个体选择概率匚，从当前种群中随机选出两个个体作为父体。选择概率P.应该是正比于适应度。交叉：对选中的父体，按交叉概率P决定是否交叉产生两个新的后代。若决定交叉，则随机决定交叉位置(也可采用其它交叉方式)；若不交叉，则两个后代是两个父体的严格复制。突变：对产生的两个后代，分别在每个位置，按突变概率Pm决定是否发生突变，得到的两个后代放入下一代新的种群中。

生成N个新的个体后，用新的种群代替原来的种群。(6)转向步骤2。终止条件可是指定的迭代代数，一般为50—500个代数。也可是指定的误差条件。标准遗传算法的流程图如图3.2所示。编码和初始化种群不满足终止条件计算终止编码和初始化种群不满足终止条件图3.2标准遗传算法流程解决实际问题时遗传算法包括两个决策步骤：将求解问题模型化为符合遗传算法的框架，可行解空间的定义，适应值函数的表现形式，解的字符串的表达方式。遗传算法参数的设计，如种群的大小，选择交叉、突变的概率选择,进化最大代数，终止准则设定等。3.5标准遗传算法特点标准遗传算法有如下特点：遗传算法是对参数的编码进行操作，而不是对参数本身。对参数的编码操作是直接对对象的结构进行操作。具有自组织、自适应、自学习性。遗传算法利用进化过程获得的信息，自行组织搜索，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。遗传算法具有并行计算的特点。许多传统搜索方法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。求解所需问题的信息量少，因而应用范围较广。这是因为遗传算法是利用所求问题的适应度函数值来评估个体，进行搜索求解的。而不像传统优化方法需要一些辅助信息如连续、导数等，一旦所需信息不存在，这些方法就会失败而无法被执行。从这个意义上讲，遗传算法几乎可以处理任何问题，既可以是数学解析式所表达的显函数，也可以是映射矩阵甚至是神经网络等隐函数，因而应用范围较广。所进行的操作简单、可靠，并利用概率的变迁规则来指导搜索方向。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向，并且仅使用复制、交换和突变这三种简单可靠的操作方法。遗传算法正是使用这些简单的随机操作来指导搜索，向着问题的最优解前进。适于求解复杂问题而且效率高。正是由于遗传算法具有上述特点，所以它最善于搜索求解复杂问题，并可以很快地从这一问题所形成的复杂地域中找出期望值高的区域，最终快速找出复杂问题的最优解。3.6标准遗传算法存在的问题及改进途径尽管遗传算法具有较多的优点，并在实际中得到了大量的应用，但它也存在着许多急待解决的问题。3.6.1标准遗传算法存在的问题重要参数如N(群体规模)、pc(交叉概率)、Pm(变异概率)如何选择。这些重要参数的选择将直接影响遗传算法的性能。交叉算子和变异算子如何协调工作。如何改进操作手段或引入新的操作手段来提高遗传算法的执行效果。如何避免算法初期的过早收敛的产生，后期的搜索迟钝以及局部搜索能力较弱的问题。单一的群体更新方式难以兼顾多样性和收敛性的要求，收敛速度较慢的问题。如何将遗传算法与其它传统优化方法有机地结合起来。以便各显所能，得到解决问题的最佳方案。如何从数学上更加完善地对遗传算法进行定量分析，为遗传算法获得更好的实际应用奠定基础。如何更广泛地开辟遗传算法的实际应用新领域。3.6.2对标准遗传算法改进的新算法针对标准遗传算法所存在的缺陷［17］，许多学者提出了各种改进方法以改善遗传算法的性能，主要从初始解群的产生、选择、交叉和变异算子的改进、重要参数选择等方面寻求改进。对标准遗传算法改进的新算法，主要有启发式遗传算法、递级分布式遗传算法、连续繁殖式遗传算法、基于分裂选择的遗传算法、自适应遗传算法、并行遗传算法、基于迁移和人工选择的遗传算法。3.6.3标准遗传算法的改进途径改变遗传算法的组成成分或使用技术，如选用优化控制参数，适合问题特性的编码技术等。采用动态自适应技术，在进化过程中调整算法控制参数和编码粒度。采用非标准的遗传操作算子。采用混合遗传算法。这一研究的目的是既发挥遗传算法的全局性特点又发挥某类特定方法对于特定问题的有效收敛性，以便快速、稳定地搜索到问题的全局最优解。如Poon和Park［i8］。将遗传算法GA和模拟退火SA进行了比较，结果显示，在运行初期遗传算法GA的收敛较快，而模拟退火SA却往往能发现更好的解，但计算代价较高，原因是遗传算法GA能够产生平均适应值高的种群，但缺少寻找最出色个体的“杀手铜”因此Dejong［i9］建议，应该将遗传算法GA的全局搜索效能与其它局部搜索方法结合起来。如将遗传算法与模拟退火综合，构成混合方法模拟退火—遗传算法。类似还有神经网络—并行遗传算法、进化编程—遗传算法、遗传编程—遗传算法、爬山法—遗传算法、模糊—遗传算法。采用并行遗传算法。并行遗传算法包括以下四类：a、整体并行遗传算法：这种模型只有一个种群，个体计算和遗传算子的应用显示并行化，并行地指派个体的子集到每个有用处理器，每个个体有机会与其它个体匹配，这种方法适用于其享和分布式计算机。b、粗粒度并行遗传算法：粗粒度并行遗传算法的主要特征是群体之间的并行性和引入迁移算子的作用。C、细粒度并行遗传算法：细粒度并行遗传算法是开发一个群体中的并行性。种群被划分成许多小群体，此模型需要巨型并行机。d、混合并行遗传算法：该方法是组合两种并行算法，构造出混合并行遗传算法。一种混合并行遗传算法是在粗粒度的群体上进行整体并行化，如同粗粒度并行遗传算法，迁移在群体之间发生，个体计算是并行处理。4遗传算法一般模型的收敛性分析4.1基于简化的遗传算法模型的收敛性分析近些年，在基于简化的遗传算法模型的收敛性分析方面取得了突破，运用的数学工具是Markov链。Coldberg和Segrest[20]首先使用了Markov链分析了遗传算法。Eiben等用Markov链证明了最优个体的遗传算法的概率性全局收敛，Rudolph用齐次有限Markov链证明了带有复制、交换、突变操作的标准遗传算法不收敛到全局最优解，不适合于静态函数优化问题，建议改变复制策略以达到全局收敛。BaCk和Muhlenbin研究了达到全局最优解的遗传算法的时间复杂性问题。4.2遗传算法一般模型的收敛性分析上面基于简化的遗传算法模型的收敛性结果，都是通过马尔可夫链的极限理论来分析的。近几年，对于遗传算法一般模型的收敛性，由张文修[2122]等进行了深入的研究，用鞍方法与迭代方法得到了一系列的结果。给出了遗传算法一般模型的收敛条件，并应用这些条件证明了杰出者遗传算法、整体退火遗传算法、最佳值遗传算法、广义模拟退火遗传算法这四种混合遗传算法的概率收敛性定理。例如对于标准遗传算法子，当变异概率1P三P>0时，有r二pln(p<-)，于是，满足概率收敛定理的条件，因而mn2有结论：若变异不变遗传算法采用概率收敛定理的算法，则几乎处处强收敛到全局最优解集。对于遗传算法首次到达最优解集的时间，用首达时间的期望值表示，可得到这样的结论：求目标函数f(x)= 1x的极大值，ji=1j=1xG［0,1］，首达时间的期望值的上界是l的多项式。目标函数厂f(x)=<+1,11xII1=1 的首达时间的期望值被指数下界所控制。l-IIxII,11xIIVl11就遗传算法的目标来看，是寻求全局最优解，而完成的过程是一个随机搜索过程。因而是一个下鞅序列，利用鞅收敛定理进一步证明遗传算法的收敛性。为了保证遗传算法的收敛性，有两个参数是非常重要的：一个参数是过程进入满意解后下一步脱离满意解集的可能性。另一个参数是过程未进入满意解时下一步仍不能进入满意解的可能性。这两个参数的匹配构成了遗传算法收敛的一般理论。用这种方法研究收敛性变为纯概率的方法，直观且简练地证明了多种遗传算法的收敛性。Markov链在分析遗传算法中的具体形式：设S=£,12为个体空间，E=SN为种群空间。一般用X，Y，Z或X.，Y.,Z.表示个体，用X,Y,Z,表示种群，显然种群是个体空间上的一个N..维向量，记为X=(X,X，…,X),个体X.是｛0,1｝上的l维向量，记为X=1 2 N . .(X.1,X.2,...,X.l)。若P是SN上的概率测度，则(SN,P)构成概率空间。设G:(SN,P)T(SN,P)n是随机遗传算子，GN可通过选择、交叉、变异等随机算子构成。于是得到遗传算法的种群序列显然｛x(n)｝为状态SN上的Markov链。4.3十进制退传算法的收敛性分析黄友锐㈡］用Markov链分析十进制遗传算法，得到了十进制遗传算法是一个遍历的Markov链。即不论其初始分布如何，状态链最终收敛于一个确定的终了状态，而各状态都是非零概率可达的。并且证明了标准十进制遗传算法不收敛到全局最优值。而每代保留最优的改进十进制遗传算法能收敛于全局最优。标准遗传算法虽不保证全局最优收敛，但在一定的约束条件下，遗传算法可以收敛到全局最优值。5应用与展望5.1遗传算法的应用领域由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面是遗传算法的一些主要应用领域。1、函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。2、组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。80年代以来，遗传算法的应用领域不断扩大。目前遗传算法所涉及的主要领域有自动控制、规划设计、组合优化、图象处理、信号处理、人工生命等。可见，遗传算法的应用研究已从初期的组合优化求解拓展到了许多更新。更工程化的应用方面。5.2遗传算法的研究展望遗传算法虽已取得了一些可喜的成果，但可以说遗传算法的研究是一个发展中的领域，目前遗传算法的研究仅仅是一个开端，对于未来的研究工作，我们可以从以下几个方面来努力。遗传算法在人工生命中的应用研究。特别是研究如何采用混合遗传算法使人工生命外部系统虚拟生物的遗传进化模型更接近自然生命的多样性及其赖以生存的复杂环境和自然法则。目前这方面的研究只限于基本简单的虚拟生物模型，要深入研究还需要做很多的工作。有必要开拓其它遗传算法研究方法，为遗传算法的研究引入新的思想。如利用数学知识，将群体表示为解集上的概率分布，这样比简单遗传算法要求更少的内存，在这方面需作更深入的探讨。目前遗传算法的研究可以说仅仅是一个开端，遗传算法对生物演化的模拟还只是形式，未能深入到生物演化内部规律的模拟，未能对神经元思维的学习过程进行模拟，因此，需要对遗传算法模型本身作更深入的探讨。如果这方面有所突破，将对智能机器人的产生和其它许多科学产生深远的影响。目前一些学者已对遗传算法一般模型的收敛性进行了分析，证明了多种遗传算法的概率收敛性定理，但有的概率收敛性定理还需要进行实例验证。通过理论指导应用，反过来，由应用推动理论的发展，必然使遗传算法的研究