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