遗传算法详解PPT学习课件.ppt

1.,遗传算法,遗传算法（,genetic algorithms,简称,GA）,是人工智能的重要分支，是基于达尔文进化论，在微型计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存、优胜劣汰等自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决或明显失效的非常复杂问题，特别是最优化问题，,GA,提供了一个行之有效的新途径。近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业控制工程领域的成功应用，这种算法受到了广泛的关注。,1,.1.1 基本遗传学基础,遗传算法是根据生物进化的模型提出的一种优化算法。自然选择学说是进化论的中心内容，根据进化论，生物的发展进化主要有三个原因，即遗传、变异和选择。,遗传是指子代总是和亲代相似。遗传性是一切生物所共有的特性，它使得生物能够把其特性、性状传给后代。遗传是生物进化的基础。,变异是指子代和亲代有某些不相似的现象，即子代永远不会和亲代完全一样。它是一切生物所具有的共有特性，是生物个体之间相互区别的基础。引起变异的原因主要是生活环境的影响及杂交等。生物的变异性为生物的进化和发展创造了条件。,选择决定生物进化的方向。在进化过程中，有的要保留，有的要被淘汰。自然选择是指生物在自然界的生存环境中适者生存，不适者被淘汰的过程。通过不断的自然选择，有利于生存的变异就会遗传下去，积累起来，使变异越来越大，逐步产生了新的物种。,生物就是在遗传、变异和选择三种因素的综合作用过程中，不断地向前发展和进化。选择是通过遗传和变异起作用的，变异为选择提供资料，遗传巩固与积累选择的资料，而选择则能控制变异与遗传的方向，使变异和遗传向着适应环境的方向发展。遗传算法正是吸取了自然生物系统,“,适者生存、优胜劣汰,”,的进化原理，从而使它能够提供一个在复杂空间中随机搜索的方法，为解决许多传统的优化方法难以解决的优化问题提供了新的途径。,1,.1.2 遗传算法的原理和特点,遗传算法将生物进化原理引入待优化参数形成的编码串群体中，按着一定的适值函数及一系列遗传操作对各个体进行筛选，从而使适值高的个体被保留下来，组成新的群体，新群体包含上一代的大量信息，并且引入了新的优于上一代的个体。这样周而复始，群体中各个体适值不断提高，直至满足一定的极限条件。此时，群体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理，使它能够在复杂空间进行全局优化搜索；另外，遗传算法对于搜索空间，基本上不需要什么限制性的假设（如连续、可微及单峰等）。,遗传算法的特点,同常规优化算法相比，遗传算法有以下特点：,遗传算法是对参数的编码进行操作，而非对参数本身。,遗传算法是从许多点开始并行操作，并非局限于一点，从而可有效防止搜索过程收敛于局部最优解。,遗传算法通过目标函数计算适值，并不需要其它推导和附加信息，因而对问题的依赖性较小。,遗传算法的寻优规则是由概率决定的，而非确定性的。,遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索。,遗传算法对所求解的优化问题没有太多的数学要求。,遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度。,1,.1.3 遗传算法的基本操作,一般的遗传算法都包含三个基本操作：复制,(,reproduction),、,交叉,(,crossover),和变异,(,mutation),。,1.,复制,复制（又称繁殖），是从一个旧种群（,old population,）,中选择生命力强的字符串（,individual string,）,产生新种群的过程。或者说，复制是个体位串根据其目标函数,f,（,即适值函数）拷贝自己的过程。直观地讲，可以把目标函数,f,看作是期望的最大效益的某种量度。根据位串的适值所进行的拷贝，意味着具有较高适值的位串更有可能在下一代中产生一个或多个子孙。显然，在复制操作过程中，目标函数,(,适值,),是该位串被复制或被淘汰的决定因素。,复制操作的初始种群,(,旧种群,),的生成往往是随机产生的。例如，通过掷硬币,20,次产生维数,n,4,的初始种群如下,(,正面,=1,，背面,=0),：,01101,11000,01000,10011,显然，该初始种群可以看成是一个长度为五位的无符号二进制数，将其编成四个位串，并解码为十进制的数：,位串,1,：,01101 13,位串,2,：,11000 24,位串,3,：,01000 8,位串,4,：,10011 19,通过一个,5,位无符号二进制数，可以得到一个从,0,到,31,的数值,x,，,它可以是系统的某个参数。计算目标函数或适值,f,(,x,)=,x,2,，,其结果如表,6-1,所示。计算种群中所有个体位串的适值之和，同时，计算种群全体的适值比例，其结果示于表中。,转轮法,转轮法把种群中所有个体位串适值的总和看作一个轮子的圆,周，而每个个体位串按其适值在总和中所占的比例占据轮子,的一个扇区。按表,6,-1,可绘制如图的转轮。,复制时，只要简单地转动这个按权重,划分的转轮,4,次，从而产生,4,个下一代,的种群。例如对于表,6,-1,中的位串,1,，,其适值为,169,，为总适值的,14.4%,。,因此，每旋转一次转轮指向该位串,的概率为,0.144,。每当需要下一个后,代时，就旋转一下这个按权重划分,的转轮，产生一个复制的候选者。,这样位串的适值越高，在其下代中,产生的后代就越多。,图,1,-1,当一个位串被选中时，此位串将被完整地复制，然后将复制位串送入匹配集（缓冲区）中。旋转,4,次转轮即产生,4,个位串。这,4,个位串是上代种群的复制，有的位串可能被复制一次或多次，有的可能被淘汰。在本例中，位串,3,被淘汰，位串,4,被复制一次。如表,6-2,所示，适值最好的有较多的拷贝，即给予适合于生存环境的优良个体更多繁殖后代的机会，从而使优良特性得以遗传，反之，最差的则被淘汰。,2.交叉,简单的交叉分两步实现。第一步是将新复制产生的位串个体随机两两配对；第二步是随机选择交叉点，对匹配的位串进行交叉繁殖，产生一对新的位串。具体过程如下：设位串的字符长度为,l,，,在,1,，,l,1,的范围内，随机地选取一个整数值,k,作为交叉点。将两个配对串从第,k,位右边部分的所有字符进行交换，从而生成两个新的位串。例如，在表,6-2,中，已知位串的字符长度,l,=5,，,随机选取,k,=4,，,对两个初始的位串个体,A,1,和,A,2,进行配对，交叉操作的位置用分隔符,“,|,”,表示为A,1,=0110|1,A,2,=1100|0,交叉操作后产生了两个新的字符串为：,A,1,=01100,A,2,=11001,一般的交叉操作过程：,遗传算法的有效性主要来自于复制和交叉操作。复制虽然能够从旧种群中选择出优秀者，但不能创造新的个体；交叉模拟生物进化过程中的繁殖现象，通过两个个体的交换组合，来创造新的优良个体。,表6-3列出了交叉操作之后的结果数据，从中可以看出交叉操作的具体过程。首先，随机配对匹配集中的个体，将位串1、2配对，位串3、4配对；然后，随机选取交叉点，设位串1、2的交叉点为,k,=4，,二者只交换最后一位，从而生成两个新的位串，即,图,1,-2,交叉操作,位串,3,、,4,的交叉点为,k=2,，,二者交换后三位，生成两个新的位串，即,单点交叉与多点交叉,上述例子中交叉的位置是一个，称单点交叉。即指个体切断点有一处，由于进行个体间的组合替换生成两个新个体，位串个体长度为,l,时，单点交叉可能有,l,1,个不同的交叉。,多点交叉是允许个体的切断点有多个，每个切断点在两个个体间进行个体的交叉，生成两个新个体。,3.变异,尽管复制和交叉操作很重要，在遗传算法中是第一位的，但不能保证不会遗漏一些重要的遗传信息。在人工遗传系统中，变异用来防止这种遗漏。在简单遗传算法中，变异就是在某个字符串当中把某一位的值偶然的（概率很小的）随机的改变，即在某些特定位置上简单地把1,变为,0,，或反之。当它有节制地和交叉一起使用时，它就是一种防止过度成熟而丢失重要,概念的保险策略。例如，随,机产生一个种群，如表所示。在,该表所列种群中，无论怎样交叉，,在第,4,位上都不可能得到有,1,的位串。,若优化的结果要求该位是,1,，,显然仅靠交叉是不够的，还需要有变,异，即特定位置上的,0,和,1,之间的转变。,变异在遗传算法中的作用是第二位的，但却是必不可少的。变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机改变遗传基因（即位串个体中某一位）的值。通过变异操作，可确保种群中遗传基因类型的多样性，以使搜索能在尽可能大的空间中进行，避免丢失在搜索中有用的遗传信息而陷入局部解。根据统计，变异的概率为,0.001,，即变异的频率为每千位传送中只变异一位。在表,6-3,的种群中共有,20,个字符（每位串的长度为,5,个字符）。期望变异的字符串位数为,20,0.001=0.02,（位），所以在此例中无位值的改变。从表,6-2,和表,6-3,可以看出，虽然仅进行一代遗传操作，但种群适值的平均值和最大值却比初始种群有了很大的提高，平均适值由,293,变到,439,，最大值由,576,变到,729,。这说明随着遗传运算的进行，种群正向着优化的方向发展。,遗传算法在以下几个方面不同于传统优化方法,遗传算法只对参数集的编码进行操作，而不是参数集本身。,遗传算法的搜索始于解的一个种群，而不是单个解，因而可以有效地防止搜索过程收敛于局部最优解。,遗传算法只使用适值函数，而不使用导数和其它附属信息，从而对问题的依赖性小。,遗传算法采用概率的、而不是确定的状态转移规则，即具有随机操作算子。,图,1,3,遗传算法的工作原理示意图,1,.,2,.1 目标函数值到适值形式的映射,适值是非负的，任何情况下总希望越大越好；而目标函数有正、有负、甚至可能是复数值；且目标函数和适值间的关系也多种多样。如求最大值对应点时，目标函数和适值变化方向相同；求最小值对应点时，变化方向恰好相反；目标函数值越小的点，适值越大。因此，存在目标函数值向适值映射的问题。1,.,2,遗传算法应用中的一些基本问题,首先应保证映射后的适值是非负的，其次目标函数的优化方向应对应于适值增大的方向。,对最小化问题，一般采用如下适值函数,f,(,x),和目标函数,g,(,x,),的映射关系：,(1,-6),其中：,c,max,可以是一个输入参数，或是理论上的最大值，或是到目前所有代（或最近的,k,代）之中见到的,g,(,x,),的最大值，此时,c,max,随着代数会有所变化。,对最大化问题，一般采用下述方法：,(,1,-7),式中:,c,min,既可以是输入值也可以是当前最小值或最近的,k,代中的最小值。,对指数函数问题，一般采用下述方法：,其中：,c,一般取1.618或2（最大化），0.618（最小化）。这样，既保证了,f,(,x,)0,又使,f,(,x,),的增大方向与优化方向一致。,1,.,2,.2 适值的调整,为了使遗传算法有效地工作，必须保持种群内位串的多样性和位串之间的竞争机制。现将遗传算法的运行分为开始、中间和结束三个阶段来考虑：在开始阶段，若一个规模不太大的种群内有少数非凡的个体（适值很高的位串），按通常的选择方法（选择复制的概率为,f,i,/,f,i,，,期望的复制数为,f,i,/,），,这些个体会被大量地复制，在种群中占有大的比重，这样就会减少种群的多样性，导致过早收敛，从而可能丢失一些有意义的搜索点或最优点，而进入局部最优；在结束阶段，即使种群内保持了很大的多样性，但若所有或大多数个体都有很高的适值，从而种群平均适值和最大适值相差无几，则平均适值附近的个体和具有最高适值的个体，被选中的机会相同，这样选择就成了一个近乎随机的步骤，适值的作用就会消失，从而使搜索性能得不到明显改进。因此，有必要对种群内各位串的适值进行有效调整，既不能相差太大，又要拉开档次，强化位串之间的竞争性。,1,.,2.,3 编码原则,遗传算法参数编码原则有两种：深层意义上的建筑块原则和最小符号表原则。而后者是一种应用广泛的实用原则。,最小符号表原则要求选择一个使问题得以自然表达的最小符号编码表。在前面讨论中使用的都是二进制符号编码表0,1，任何一个长度为,l,的位串都包含在0,1,l,中。根据遗传算法的模式理论，遗传算法能有效工作的根本原因，在于其能有效的处理种群中的大量模式，尤其是那些定义长度短、确定位数少、适值高的模式（即建筑块）。因此，编码应使确定规模的种群中包含尽可能多的模式。,表6-5给出了一个参数的二进制编码和非二进制编码的对比情况，即将0,31上的二进制整数一一对应地映射到一个有32个字母的符号表中，这个符号表包含26个英文字母（,AZ）,和6个数字（16）。在二进制编码中，通过编码表中小部分关键编码可以找到重要的相似性而在非二进制编码中，只能看到单一编码的符号表，看不出编码中的相似性。,为了进一步了解二进制编码的数学意义，假设有一个非二进制的包含,k,个字母编码的符号表,V,及二进制编码的符号表,V,，,即,V,=,a,1,a,2,a,k,V,=0,1,1,.,3,.1 复制方法的改进,1稳态复制法,该方法保证种群中最优秀的个体在进化过程中不被删除，这在很大程度上减少了有效基因的丢失。在经过交叉、变异产生的新种群中，只有一个或两个优秀个体被选进下一代种群，替代原有种群中的最差个体。,2,选择种子法,该法也称最优串复制法，它保证了最优的个体被选进下一代进化种群。其执行过程如下：,随机初始化种群,N,(0)，,种群大小为,n,。,计算种群中所有个体适值。,对以后的种群,N,(,t,),进行如下操作，直至满足条件或达到进化代数。根据个体适值大小随机选出,n,个个体组成种群,N,0,(,t,)，,并复制一份为,N,1,(,t,)，,对种群,N,0,(,t,),实施交叉操作，对种群,N,1,(,t,),实施基因突变，用以防止有效基因丢失。,计算种群,N,0,(,t,)、,N,1,(,t,),和,N,(,t,),的个体适值，从中选出最好的,n,个个体构成下一代种群,N,(,t,1)，,转至。,3,确定性复制法,在确定性复制法中，复制的概率按常规计算为：,P,i,f,i,/,f,i,。,对个体,A,i,，,其期望的后代数目,e,i,，,计算为：,e,i,nP,i,。,每一位串个体按,e,i,的整数部分分配后代数，种群的其余部分按顺序表由高到低来填充。,4,置换式余数随机复制法,这方法开始与上述确定性复制法一样，期望的个体数如前分配为,e,i,的整数部分；但,e,i,的余数部分用来计算转轮法中的权值，以补充种群总数。,5,非置换式余数随机复制法,这方法开始也与上述确定性复制法一样，而,e,i,的余数部分按概率来处理。换句话说，个体至少复制一个与,e,i,整数部分相等的后代，然后以,e,i,的余数部分为概率来复制其余的后代，直至种群的总数达到,n,。,例如一个具有期望复制值为1.5的个体，它可以复制产生一个后代，并以0.5概率产生另一个后代。试验表明，这种方法优于其它复制方法。,1,.,3,.2 高级,GA,算法,为改善,GA,的遗传性，在复制、交叉和变异运算的基础上，再考虑两种类型的基因运算，即为微运算和宏运算。多点交叉微运算是在个体级别上的运算，重组宏运算是在种群级别上的运算。,1,.,4,基于遗传算法的系统在线辨识,1,.,4,.1 遗传算法在参数辨识中的应用,1,.,4,.2 遗传算法参数辨识仿真示例,1,.,4,.1 遗传算法在参数辨识中的应用,1离散系统参数估计,设线性离散系统的数学模型为：,(1,-18),式中：,d,为滞后时间，,(,k,),为零均值的噪声序列（方差为,2,），,z,-1,为后移算子。,假定,A,(,z,-1,)、,B,(,z,-1,),和,C,(,z,-1,),未知则待辨识参数向量包含,n,a,+,n,b,+,n,c,+1,个参数，即,(,1,-19),真参数为：,(,1,-20),要应用遗传算法对参数向量,进行在线优化的参数辨识，必须解决两个问题，一个是确定多参数编码映射方法，另一个是如何根据目标函数确定适值。,2.参数级联定点映射编码,采用多参数级联定点映射编码原则进行编码，可根据辨识精度确定每个参数的二进制编码长度。假如每个参数线性映射在-2,l,-1,+2,l,-1,范围内，且要求辨识精度2,-,m,，,则每个参数需要,m,+,l,位；若已知时滞,d,2,n,，,则时滞可用,n,位编码，则各参数编码组成一个整体位串的长为(,n,a,+,n,b,n,c,)(,l,+,m,)+,n,，,这个整体位串就是系统待辨识参数的一个解。,设整体位串构成的种群数为,N,，,第,p,代的第,j,个（1,j,N,）,位串所对应的参数为：,(,1,-21),根据辨识结果，有预测输出和预测输出误差，它们分别满足：,(,1,-22),(,1,-23),3.目标函数到适值形式的映射,为保证映射后的适值是非负的，选择目标函数的优化方向应对应于适值的增大方向。由式(,1,-6)的映射关系，可选择适值函数为：,(,1,-24),求和,m,+1,步的意义在于能进一步考察辨识参数与真参数的拟合情况。在遗传算法操作过程中，可能存在这样的参数，它离真值很远，但经线性组合后某步预测输出与实际输出相差不大，求和可以避免这样的参数集取得高适值以致出现错误的收敛。,m,的值越大，适值函数的可信度就越高，,m,的上限可取为,k,值，,c,max,值是一足够大的正数，它与问题的解有关。,在计算出种群中每个个体的适值后，需要对它们规范化，先求出其平均适值为：,(,1,-25),规范化适值为：,(,1,-26),用种群规范化适值与平均适值的偏差的平方和来定义收敛域，即,(,1,-27),其中：,是一个定义的收敛域，例如若设,0.0001，,则可认为种群已经收敛，这时种群中适值最大的个体就是当前收敛条件下的最优者。,1,.,4,.2 遗传算法参数辨识仿真示例,设线性离散系统的数学模型如式（,1,13）所示，其中,d=,2,采用伪随机二进制序列（,PRBS）,输入，辨识系统参数为,及时滞。设参数的范围是-2,+2，要求辨识精度0.02，则每个参数需要用8位的位串表示，若时滞,d,不大于4，则时滞可用2位的位串表示，所以参数集位串长度为48+2=34位。,取种群规模,N,=50，,交叉概率,P,c,=0.90；,变异概率,P,m,=0.001。,适值函数中的,c,max,值分段选取。在操作初期，主要强调个体之间的多样性，可将,c,max,值稍微取大些，,c,max,=1.85,m,；,操作后期，强调竞争性，,c,max,值取小些，,c,max,=1.6,m,。,兼顾计算速度和适值可信度，取10,m,30。,在操作初期，在每一代适值规范化之后，要保持种群个体中的无子女个体占种群的百分比为一定值，若超过该值，则认为是非成熟收敛。一般将这个临界值定义在20%左右。定义辨识收敛域，,135s,时，控制得到的模糊控制器用于系统效果变差。其主要原因是由于在寻优过程中，种群个体没有对系统输出在不同区域、不同变化速率的情况都进行目标函数估价。采用变期望输入的方法使控制器在寻优过程中能够对系统绝大部分状态变化做出响应。此时，期望输入按下式选取：,(,1,-33),图,1,-18,图,1,-17,基于函数归一化适值调整法和稳态复制法寻优得到的模糊规则表、系统输出响应分别如表,6,-8,和图,1,18,所示。从图,1,18,中可以看出当,y,d,=1,时，系统输出很好地跟踪了期望输入，其过渡过程短、稳态误差小，对其它的期望输入都有较好的输出响应。,4.仿真研究,以著名的75城市,TSP,为例，取群体规模为100，交叉概率在0.5,0.85，变异概率在0.2,0.01，个体接种疫苗概率在0.2,0.3，更新疫苗概率在0.5,0.8之间随进化过程自行调整；,M,和,分别取10和0.04，退温函数为,，,T,0,=,100，,其中,k,为进化代数。在基本参数保持不变的,前题下，对通用遗传算法和免疫算法进行比较，若群体的最佳适值在连续100次迭代中保持不变则认为搜索结束。同时，计算过程中每隔10代记录一次进化结果。图,1,-21显示了免疫遗传算法优化75城市,TSP,问题的免疫疫苗和优化结果。,仿真结果表明，免疫遗传算法经940代首次出现后来被认定的最佳个体，而通用遗传算法经3550代才出现该最佳个体，同时发现免疫遗传算法对提高搜索效率，消除通用遗传算法在后期的振荡现象具有明显的效果。,图,1,-21 优化75城市,TSP,问题的免疫疫苗和优化结果,