遗传算法及其应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,遗传算法及其应用,1,、引言,2,、基本概念,3,、基本遗传算法,4,、基本遗传算法举例,5,、遗传算法的基本原理与方法,6,、遗传算法引用举例,1,、引言,遗传算法简称,GA,（,Genetic Algorithms,）是,1962,年由美国,Michigan,大学的,Holland,教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。,遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下三个方面：,（,1,）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。,（,2,）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。,（,3,）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。,遗传算法将,“,优胜劣汰，适者生存,”,的生物进化原理引入优化参数形成的编码串群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。,生物进化过程如下图,2,、基本概念,2.1,个体与种群,个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。,种群,(population),就是模拟生物种群而由若 干个体组成的群体,它一般是整个搜索空间 的一个很小的子集。,2.2,适应度与适应度函数,适应度,(fitness),就是借鉴生物个体对环境的适应程度,而对问题中的,个体对象,所设计的,表征其优劣的一种测度,。,适应度函数,(fitness function),就是问题中的全体个体与其适应度之间的一个对应关。它一般是一个实值函数。该函数就是遗传算法中指导搜索的,评价函数,。,2.3,染色体与基因,染色体（,chromosome,）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（,gene,）。,例如：,个体,(,表现型,),染色体（基因型）,9 -,1001,（,2,，,5,，,6,）,-010 101 110,2.4,遗传操作,亦称,遗传算,子,(genetic operator),，就是,关于染色体的运算。遗传算法中有三,种遗传操作,：,选择,-,复制,(selection-reproduction),交叉,(crossover,，,亦称交换、交配或杂交,),变异,(mutation,，亦称,突变,),选择-复制,通常做法是：对于一个规模为,N,的种群,S,按每个染色体,x,i,S,的选择概率,P,(,x,i,)所决定的选中机会,分,N,次从,S,中随机选定,N,个染色体,并进行复制,。,这里的选择概率,P,(,x,i,),的计算公式为,交叉,就是互换两个染色体某些位上的基因。,例如,设染色体,s,1,=01001011,s,2,=10010101,交换其后4位基因,即,s,1,=01000101,s,2,=10011011,可以看做是原染色体,s,1,和,s,2,的,子代,染色体。,变异,就是改变染色体某个(些)位上的基因。,例如,设染色体,s,=11001101,，,将其第三位上的0变为1,即,s,=11,0,01101,11,1,01101=,s,s,也可以看做是原染色体,s,的子代染色体。,3,基本,遗传算法,遗传算法基本流程框图,生成初始种群,计算适应度,选择-复制,交叉,变异,生成新一代种群,终止?,结束,基本,遗传,算法的步骤,步,1,在搜索空间,U,上定义一个适应度函数,f,(,x,),，给定种群规模,N,，交叉率,P,c,和变异率,P,m,，代数,T,；,步,2,随机产生,U,中的,N,个个体,s,1,s,2,s,N,，组成初始种群,S,=,s,1,s,2,s,N,，置代数计数器,t,=1,；,步,3,计算,S,中每个个体的适应,度,f(,x,),；,步,4,若终止条件满足，则取,S,中适应度最大的个体作为所求结果，,算法结束。否则，转步,5,。,步,5,按选择概率,P,(,xi,),所决定的选中机会，每次从,S,中随机选定,1,个个体并将其染色体复制，共做,N,次，然后将复制所得的,N,个染色体组成群体,S,1,；,步,6,按交叉率,P,c,所决定的参加交叉的染色体数,c,，从,S,1,中随机确定,c,个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体,S,2,；,步,7,按变异率,P,m,所决定的变异次数,m,，从,S,2,中随机确定,m,个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体,S,3,；,步,8,将群体,S,3,作为新一代种群，即用,S,3,代替,S,，,t,=,t,+1,，转步,3,；,4,基本遗传算法举例,例,4.1,一元函数优化实例（约束优化问题）,二维图形如图所示：,式,4.1,下面介绍求解该优化问题的遗传算法的构造过程：,第一步：,确定决策变量和约束条件。,式,4.1,给出，决策变量为,x,，约束条件为,-2x2,。,第二步：,建立优化模型。,式,4.1,已经给出了问题的数学模型。,第三步：,确定编码方法。,要进行编码工作，即将变量转换成二进制编码串。串的长度取决于所要求的精度。例如，变量,x,的区间是,a,，,b,，要求的精度是小数点后,1,位，也就意味着每个变量应该被分成至少（,b-a,）,10,1,个部分。用以下公式,第四步,：确定解码方法。,从二进制串返回一个实际的值可用下面的公式来实现：,Decimal,（,substring,）表示变量,x,的子串,substring,的十进制值。,这样，不妨设要求的精度为小数点后,4,位。,可得（,2-,（,-2,）,101=40,324064,，,m=6,因此，一个染色体串是,6,位，如下图所示。,对应的变量,x,的实值如下表,实值数为,变量,二进制数,十进制数,x,100010,34,初始种群可随机产生（假设种群大小为,10,）：,相对应的十进制的实际值为,第五步：,确定个体评价方法。,对一个染色体串的适应度评价由下列三个步骤组成：,（,1,）将染色体进行反编码，转换成真实值。在本例中，意味着将二进制串转为实际值：,（,2,）评价目标函数,f,（,x,k,）。,（,3,）将目标函数值转为适应度值。对于极小值问题，适应度就等于目标函数值，即,在遗传算法中，评价函数起着自然进化中环境的角色，它通过染色体的适应度对其进行评价。上述染色体的适应度值如下：,由以上数据可以看出，上述染色体中最健壮的是,U,3,，最虚弱的是,U,9,。,第六步：,设计遗传算子和确定遗传算法的运行参数。,（,1,）选择运算使用轮盘赌选择算子。,为基础的概率分配来选择新的种群。其步骤如下：,计算个染色体,U,k,的适应度值,eval,（,U,k,）：,计算群体的适应度值总和：,计算对应于每个染色体,U,k,的选择概率,P,k,；,计算每个染色体,U,k,的累积概率,Q,k,：,在实际工作中，选择新种群的一个染色体按以下步骤完成：,在,0,1,之间，产生一个均匀分布的伪随机数,r,；,若下述关系成立，则选择第,k,个染色体。,伪随机数表示指针,大小表示位置,所指向的染色体就是,待选择的染色体,针对本例题，首先计算适值之和,计算各染色体选择概率、积累概率,序号,NO.,适应度值,eval,选择概率,P,积累概率,Q,U,1,4.3701,0.1230,0.1230,U,2,3.7654,0.1060,0.2290,U,3,4.9184,0.1385,0.3675,U,4,4.5556,0.1283,0.4958,U,5,2.5802,0.0727,0.56845,U,6,3.4671,0.0976,0.6661,U,7,3.6203,0.1019,0.7680,U,8,3.6203,0.1019,0.8699,U,9,1.0000,0.0282,0.8981,U,10,3.6203,0.1019,1.0000,旋转转轮,10,次，每次选择一个染色体来构造新种群。,最后选出的种群如下：,（,2,）交叉算子使用单点交叉算子。,随机选择一个染色体串的节点，然后交换两个父辈节点右端部分来产生子辈。假设两个父辈染色体如下所示（节点随机选择在染色体串的第,3,位基因）：,设交叉率,p,c,=0.60,，即平均有,60%,的染色体进行交叉，对每个染色体产生一个,0,1,间的随机数，小于交叉率的则选作交叉对象。设随机数序列如下：,U,1,、,U,2,、,U,5,、,U,6,、,U,7,和,U,8,被选作参与交叉,在,1,5,之间产生一个随机位置（因染色体长位,6,），假设位,3,，则在,3,处，将染色体切断，并交换断点的右端,（,3,）变异算子使用基本位变异算子。,假设染色体,U1,的第,5,位基因被选作变异，即如果该位基因是,0,，则变异后就为,1,。于是，染色体在变异后将是：,设变异率,p,m,=0.01,，即种群中平均有,1%,的基因发生变异。每个染色体基因数：,6,，种群中染色体个数：,10,，总的基因：,60,，平均有,0.6,个基因发生变异。对每个基因产生一个,0,1,间的随机数，小于变异率的选作变异基因。,假设选择结果导致如下基因发生变异：,在完成变异后，得到了最终的下一代种群：,相对应的变量,x,的十进制值和适应度值为,至此，完成了遗传算法第一代的流程。,设计终止代数为,55,。在第,7,代，得到了最佳的染色体。,个体随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰，而适应度较高的一些个体会越来越多，并且更加集中在,U*,附近，最终就可搜索到问题的最优解,U*,。,U*,对应的十进制为,x*=0.069,，,得适应度值为,5.0047,。,即目标函数的最大值为,f,（,x,）,=5.0047,。,下面画出迭代后个体的最优解的变化和种群均值的变化。遗传算法的运行结果如下：,5,遗传算法的基本原理与方法,5.1,编码,编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。在遗传算法执行过程中，需要对不同的具体问题进行编码。编码的好坏直接影响选择、交叉和变异等遗传操作。,所谓的编码，就是把一个问题的可行解空间转换到遗传算法所能处理的搜索空间的转换方法。即解的遗传表示。,二进制编码方法,它是遗传算法中最主要的一种编码方法，它使用的编码符号集是由二进制符号,0,和,1,所组成的二值符号集,0,1,，它所构成的个体基因型是一个二进制编码符号串。,例如：,个体,(,表现型,),染色体（基因型）,9 -,1001,（,2,，,5,，,6,）,-010 101 110,5.2,选择,选择又称复制，是在群体中选择生命力强的个体产生新的群体的过程。,遗传算法使用选择算子（又称复制算子）来对群体中的个体进行优胜劣汰操作；根据每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代的概率较小。这样就可以使得群体中的适应值不断接近最优解。选择操作建立在对个体的适应度进行评价的基础之上。选择的操作的主要目的是为了避免有用遗传信息的丢失，提高全局收敛性和计算效率。,遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗被传到下一代群体中的遗传操作，用来确定重组和交叉的个体，以及被选中个体产生多少个子代。选择操作的策略与编码方式无关。,轮盘赌选择,轮盘赌选择方法是一种回放式随机采样方法，所有选择是从当前种群中根据个体的适应度值，按某种准则挑选出好的个体进入下一代种群。选择算子有多种，经典遗传算法中常用的是轮盘赌的选择方法，适应度值越高，被选中的可能性就越大，进入下一代的概率就越大。每个个体就像圆盘中的一个扇形部分，扇面的角度和个体的适应度值成正比，随机波动圆盘，当圆盘停止转动时指针所在扇面对应的个体被选中，轮盘赌式的选择方法由此得名。,由于群体规模有限和随机操作等原因，使得个体实际被选中的次数与它应该被选中的期望值 之间可能存在着一定的误差，因此这种选择方法的选择误差比较大，有时甚至适应度较高的个体也选不上。,轮盘赌选择示意图,5,.3,交叉,交叉又称重组，是按较大的概率从种群中选择两个个体，交换两个个体的某个或某些位。交叉运算产生子代，子代继承了父代的基本特征。交叉算子的设计包括如何确定交叉点位置和如何进行部分基因交换两个方面的内容。遗传算法中所谓的交叉，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。它是遗传算法中产生新个体的主要方法。,遗传算法中，在交叉操作之前还必须先对群体中的个体进行配对。目前常用的配对算子策略是随机配对。即从群体中的,M,个个体一随机的方式组成,M/2,对配对个体组。,单点交叉,单点交叉又称为简单交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。单点交叉的具体执行过程如下：,对个体进行两两配对，若群体大小位,M,，则共有,M/2,对相互配对的个体组。,对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点，若染色体的长度为,N,，则共有,N-1,个可能的交叉点位置。,对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。,单点交叉的示意图如下：,A,B,A,B,交叉点,交叉点,5.4,变异,遗传算法中所谓的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。如二进制编码中“,0”,变为“,1”,，“,1”,变为“,0”,，进而生成新的个体。,事实上，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但它是必不可少的一个步骤，因为它决定了遗传算法的局部搜索能力。交叉算子与变异算子相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完成最优化为题的寻优过程。,在遗传算方法中，变异算子的主要目的有两个：,改善遗传算法的局部搜索能力。,维持群体的多样性，防止出现早熟现象。,基本位变异,基本位变异是指对个体编码串中以变异概率、随机指定的某一位或某些位基因座上的值做变异运算，其具体过程如下：,对个的每一个基因座，一变异概率指定其为变异点。,对每一个指定的变异点，对其基因值做取反运算或用其它的等位基因值来替换，从而产生出新一代的个体。,例如,设染色体,s,=11001101,，,将其第三位上的0变为1,即,s,=11,0,01101,11,1,01101=,s,s,也可以看做是原染色体,s,的子代染色体。,5.5,适应度函数,在遗传算法中，使用适应度函数这个概念来度量群体中各个个体在优化计算中能达到或接近于或有助于找到最优解的优良程度。适应度较高的各个遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数。,适应度函数也成为评价函数，是根据目标函数值确定的用于区分群体中个体好坏的标准，是算法演化过程的驱动力，也是进行自然选择的唯一依据。适应度函数总是非负的，任何情况下都希望其值越大越好。而目标函数值可能有正有负，即有时求最大值，有时求最小值。因此需要在目标函数与适应度函数之间进行变换。,评价个体适应度的一般过程为：,对个体编码串进行解码处理后，可得到个体的表现型。,由个体的表现型可计算出对应个体的目标函数值。,根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。,例如：直接以待求解的目标函数,f,（,x,）,转化为,适应度函数,Fit,（,f,（,x,），令,目标函数为最小化问题,目标函数为最大化问题,这种适应度函数简单直观。,5.6,控制参数的选择,1,、交叉概率,优化过程中，交叉概率始终控制着遗传算法中其主要地位的交叉算子。较大的交叉概率可使各代充分交叉，但群体中的优良模式遭到破坏的可能性增大，以致产生较大的代沟，从而使搜索走向随机化；交叉概率越低，产生的代沟就越小，这样将保持一个连续的解空间，使找到全局最优解的可能性增大，但进化速度就越慢；若交叉率太低，就会使得更多的个体直接复制到下一代，遗传算法可能陷入停滞状态。一般建议,p,c,取值范围是,0.40.99,2,、变异概率,变异运算是对遗传算法的改进，对交叉过程中可能丢失的某种遗传基因进行修复和补充，也可以防止遗传算法尽快收敛到局部最优解。变异概率取值较大时，虽然能够产生较多的个体，增加了群体的多样性，但也有可能破坏掉很多好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若变异概率取值太小，则变异概率产生新的个体和抑制早熟现象的能力就会越差。一般建议的取值范围,pm,是,0.00010.1.,3,、群体规模,群体规模的大小直接影响到遗传算法的收敛性或计算效率。规模过小，容易收敛到局部最优解；规模过大，会造成计算速率降低。群体规模,N,可以根据实际情况在,10200,之间选定。,6,遗传算法应用举例,雷达目标识别问题,复杂目标的高分辨雷达回波信号在时域上出现多个峰值，这些峰值对应目标径向上的多个强散射中心。但是，当空中目标的位置发生变化时，目标的强散射点相对于雷达视角发生变化。因此，从数据库中寻找与待识别目标模式相匹配的模式的工作量很大，传统的匹配方法已经不能满足需要。本节利用遗传算法进行目标识别，具体步骤如下：,染色体编码与解码,假设数据库中已知目标类型有,m,种，每种类型目标在雷达视角,范围内的雷达回波信号为,n,个序列。对于两参数目标类型,i,m,和雷达视角编码,j,n,，设,k,1,为参数,i,的二进制编码长度，,k,2,为参数,j,的二进制编码长度，定义遗传算法的个体,I,k,基因型,G,k,为,则编码总长度为,k,1,+k,2,，即个体,I,k,基因型,G,k,的前,k,1,位的十进制解码为,i,，后,k,2,位的十进制解码为,j,。,2,、产生初始种群,一个个体由串长为,k,1,+k,2,的随机产生的二进制串组成染色体的基因码，可以产生一定数目的个体组成种群，设置群体大小,NIND=20,。,3,、个体适应度的检测评估,设,X,（,i,，,j,）为第,i,种目标在第,j,个雷达视角的高分辨雷达目标回波信号序列，对应的个体为,I,k,。待识别目标的高分辨雷达目标回波信号序列为,X,。,个体,I,k,的适应度函数可以定义为,式中，为序列,X,和,Y,的相关系数。,4,、遗传算子,选择遗传算子使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子或均匀变异算子。每个个体的选择概率为：,设置遗传算法的终止进化代数,MAXGEN=200,，交叉概率,p,c,=0.7,，变异概率,p,m,=0.023,，对群体进行操作。,实例：实验数据选自毫米波步进频率信号，带宽为,1GHz,，调频步长为,2MHz,。识别目标为轰炸机、歼击机和直升机的缩比模型。对三类飞机鼻锥方向,10,方位角变化范围内的雷达回波进行截取、去均值和归一化等预处理后，作为数据库中的数据。待识别目标的雷达回波数据为三类飞机的雷达回波加高斯白噪声。,遗传算法搜索最优解的过程如下图所示：,