改进遗传算法ppt课件.pptx

《改进遗传算法ppt课件.pptx》由会员分享，可在线阅读，更多相关《改进遗传算法ppt课件.pptx（34页珍藏版）》请在三一办公上搜索。

1、遗传算法的改进,遗传算法存在的问题,1. 适应度函数标定方式多种多样，没有一个简洁通用的方法2. 遗传算法的早熟现象（即很快收敛到局部最优解而不是全局最优解）是迄今为止最难处理的关键问题。3. 快要接近最优解时在最优解附近左右摆动，收敛较慢。开始时进化速度很快，甚至以指数级进化速度朝着最优解方向前进，但不久以后，进化速度就会变慢，临近全局最优解时则可能是几百代、上千代才向目标逼近一小步，有时甚至停滞不前，出现早熟收敛。,遗传算法改进方法,基于以上介绍可知，遗传算法通常需要解决以下问题：确定编码方案，适应度函数标定，选择遗传操作方式和相关控制参数，停止准则确定等，相应地，为改进简单遗传算法的实际

2、计算性能，很多的改进工作也是从参数编码、初始种群设定、适应度函数标定、遗传操作算子、控制参数的选择以及遗传算法的结构等方面提出的。基于不同的问题，遗传算法可以有不同的改进和变形，这也是遗传算法内容丰富和作用强大的原因。,人工智能及其应用,4,改进的遗传算法,编码方法的选择编码的修复适值函数的标定 选择策略停止准则的改进,1.编码方法,这里来介绍除了0-1编码以为的其他三种重要的编码方法1.顺序编码 顺序编码是用1到n的自然数来编码，此种编码不允许重复，又称为自然数编码，例如下面是一个染色体长度为n=7的顺序编码： X=(2 3 1 5 4 7 6) 对于有7个城市的旅行商问题，城市序号为1,2

3、，.，7，则上述编码可以表示一个行走的路线。该编码方法具有广泛的适应范围，如指派问题、旅行商问题和单机调度等问题。,2.实数编码对于染色体X=（x1,x2,，xi,xn）,1in, ，则称该染色体为实数编码。实数编码具有精度高、便于大空间搜索、运算简单的特点，特别适合于实优化问题，但是反应不出基因的特征。3.整数编码 对于染色体X=（x1,x2,，xi,xn）,1ini, ni 为第i位基因的最大取值，则称染色体为整数编码。显然不同位置上的基因取值可以不同。整数编码可以适应于新产品投入、时间优化和伙伴挑选等问题。,2.不合法编码的修复,对于普通的二进制编码，通常的交叉和变异不会改变编码的合法性

4、，但是对于顺序编码、实数编码，会造成编码的不合法或者超出可行域，因此必须对不合法的编码进行处理，通常的处理手段为拒绝或者修复。下面介绍修复的方法。顺序编码的合法性修复实数编码的合法性修复,1. 顺序编码的修复 顺序编码的合法性修复策略主要包括：交叉修复策略部分映射交叉顺序交叉循环交叉变异修复策略换位变异移位变异,交叉修复策略之部分映射交叉 部分映射交叉主要用于解决双切点交叉引起的非法性。可以解决子代的基因重复和部分基因的丢失问题，保证基因的多样性。其主要步骤为：选则切点，交换中间部分确定映射关系将未交换部分按映射关系恢复合法性,交叉修复策略之顺序交叉顺序交叉是部分映射交叉的变形，相当于使用了不

5、同的映射关系。其可以较好的保留相邻关系、先后关系，但是不能保留位值特征，可以用来解决旅行商之类的拓扑问题。旅行商问题在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本,顺序交叉的步骤如下：选则切点，交换中间部分从第二个切点后的第一个基因开始分别列出两个原来染色体的基因顺序，直到列完划掉各自交换部分的基因按划掉后的相对顺序从后开始补齐原来的染色体的基因,交叉修复策略之循环交叉 循环交叉的基本思想是子串位置上的值必须与父母相同位置上的值相一致。简单来说，就是父母代在进行交叉运算时按某种方式交换某些相同位置的基因，其余位置的基因不变，组成子代。这种交叉方式适合于解决指

6、派问题。在满足特定指派要求条件下，使指派方案总体效果最佳。其修复策略较麻烦，需要时可以查找文献，大家需要记住的是：循环交叉是用来解决指派这一类的问题的,2.变异修复策略 简单的二进制变异时候只需要把变成，变成，而顺序编码的变异策略不能这样进行，一般由下面两种策略：换位变异换位变异是随机在染色体上选则两个基因，交换它们的基因值移位变异移位变异是任意选则一个基因，将其移到最前面。,3.实数编码的合法性修复之凸组合交叉 实数编码的交叉操作（单切点交叉、双切点交叉）通常不会改变其合法性问题。但是，有时会导致解码后的值超出可行域。针对这样的问题，产生了凸组合交叉。简单来说，就是直接引用凸集理论，将父母两

7、个染色体对应的看成两个点，其子代只能位于这两个点的连线上。如：有双亲P1=（x1,x2,x3,，xn）P2=（y1,y2,x3,，yn）,则可以产生的两个后代是：C1=aP1+(1-a)P2C2=(1-a)P1+aP2这里，a要保证大于0且小于1. 这样做的不好处是导致种群的基因向中间汇聚，导致基因的分散性不好，逐步丢失很多基因。这是与基因的多样性相违背。,4.实数编码的合法性修复之变异不同于二进制编码，实数编码的变异可以是任意的，通常有如下两种变异方法：位值变异向梯度方向变异位值变异是随机选取染色体上某一位基因，在其上加上一个变异补补偿D，通常便已步长是按一定规律产生的呈一定分布规律的随机数

8、,向梯度方向的变异较好的考虑了问题本身的性质，效率比较高简单来说，就是把某个染色体看成一个具有n个分量的点，然后求目标函数在这个点处的梯度对于最大化问题，就是染色体本身加上这个点处的梯度乘以一个随机数（0到1之间）对于最小化问题，就是染色体本身加上这个点处的负梯度乘以一个随机数（0到1之间）,3.适值函数的标定,1.标定的目的 将目标函数映射为适值函数，从而能够直接将适值函数与群体中的个体优劣相联系。 对目标函数进来标定，来调节选择压力。2.选择压力的概念 选择压力是指种群中好、坏个体被选中的概率之差，如果差别较大，则称选择压力大例如：五个染色体构成的一个种群，其目标函数值分别为 f1=101

9、0,f2=1008,f3=1002,f4=1005,f5=1015,因为5个个体的适应值相差不大，选中概率基本上在0.2左右，概率差别很小，即选择压力小，这将导致遗传算法的选优功能被弱化。所以要对目标函数进行标定，来调节选择压力。 可以进行如下标定：F=f -1000，这时标定后的染色体被选中的概率差别大幅度增加，即选择压力增大了，通过以上分析可以看到，适值函数的标定可以调节选择压力的大小，而通过调节选择压力的大小能够实现遗传算法中局部搜索和广域搜索的调节。,一般来说，遗传算法在开始时应该注重广域搜索，通过使用较小的选择压力来实现，随着迭代的进行，逐步偏重于局部搜索，通过使用较大的选择压力来实

10、现,2.适值得标定方法 线性标定 动态线性标定 幂律标定 对数标定 指数标定,线性标定标定方法：F=af+b其中，f为目标函数，F为标定后的适值函数，参数a和b要根据不同的问题进行设定。最大化问题 对于最大化问题 ，可以令a=1, ，则适值函数为 其中， 是一个较小的数目的是使种群中最差的个体仍然有繁殖的机会，增加种群的多样性。,最小化问题对于最小化问题 ，可以令a=-1， ，则适值函数为 其中， 也是一个较小的数，其意义与最大化问题中的设置相同,动态线性标定 线性标定中的参数随着迭代次数的增加而变化时就得到了动态线性标定。可以表述如下 其中，上标k为迭代指标，表明参数是随着迭代次数的增加而变

11、化的最大化问题 对于最大化问题，可以令 =1， ，则适值函数为,其中， 是第k代的最小目标函数值， 是一个较小的数，目的与线性标定中的 相同， 是使种群中最差的个体仍然有一点点繁殖的机会，从而增加种群的多样性。最小化问题 对于最小化问题 ，可以令a=-1，b= ，则适值函数为 其中， 也是一个较小的数，其意义和最大化问题设置相同。,对于调节选择压力的作用 的引入能够调节选择压力，即好坏个体选择概率的差，使广域搜索范围宽，保持种群的多样性，而局部搜索细致，保持收敛性。 在算法开始运行的时候，希望选择压力较小，所以 取值较大，使不同个体间的选择概率相差不大，到种群进化的后期，希望选择压力较大，所以

12、 取值较小，使不同个体间的选择概率相差变大，种群将很快达到收敛，从而解决了在最优解附近收敛较慢的问题。,幂律标定幂律标定是采用如下的构造方式 其中， 是用来调节选择压力的， 1时，选择压力加大， 1时，选择压力减小，此标定比较费时，要针对不同问题使用。,对数标定对数标定可以用于缩小目标函数值得差别，其一般形式为参数a和b根据具体问题而定。指数标定指数标定作用是扩大目标函数的差值，其一般形式为 参数a、b和c根据具体问题而定。,4.选择策略,传统的遗传算法的选择和遗传是以前进行的，即使后代不如父代，也无法纠正，现在改变选择策略，先遗传后选择，这样做的好处是样本空间扩大了，可供选择的个体增多了。一

13、般有三种选择策略：截断选择顺序选择正比选择,截断选择选择最好的前T个个体，让每一个有1/T的选择概率，即平均每个得到NP/T个繁殖机会。例如：NP=100，T=50，那么前50个染色体每个的选择概率为1/50，每个染色体平均被选中两次不足之处的是在适应值得排序上要花费较多的时间。顺序选择从好到坏排序NP个个体，然后定义最好个体的选择概率为q，在根据公式 ，可以计算出第j个个体的选择概率。,优点：选择概率可以离线计算，可以节省算法执行时间，同时选择压力可调缺点：选择概率固定化，导致在算法的执行过程中选择压力不可调节。正比选择其选择方式和旋轮法一样，即每个个体被选中进行遗传运算的概率为该个体的适应值和群体中所有个体的适应值总和的比例，只是跟传统的遗传算法不同的是选择操作是在遗传操作之后进行，用动态标定来调节选择压力,在基本的遗传算法中，一般采用最大迭代次数作为算法的停止准则，此方法不太准确，因为可能在在最大的迭代次数之前算法已经收敛，也可能在最大迭代次数时还没收敛，因此采用另外一种停止准则，即根据种群的收敛程度，种群适应值得一致性来判断是否算法停止。在算法的执行过程中保留历史上最好的个体，观察指标,5.停止准则,其中， 为种群中所以个体适应值得平均值， 为所以个体适应值得最大值，当上述指标趋近于1时，说明种群收敛，此时算法停止。,谢谢,