《第4章遗传算法.ppt》由会员分享，可在线阅读，更多相关《第4章遗传算法.ppt（35页珍藏版）》请在课桌文档上搜索。
1、第4章 遗传算法,遗传算法基本思想,建立在自然选择原理和自然进化机制上的迭代式自适应概率性搜索方法；生物进化理论：遗传、变异和适者生存；遗传与进化的几个特点：生物的所有遗传信息全部包含在其染色体中，染色体决定了生物的性状；染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；生物的繁殖过程是由其基因的复制过程来完成的；通过同源染色体之间的交叉或染色体的变异会产生新的物种对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多机会遗传到下一代。,遗传算法实例,个体编码：分别采用5位二进制编码方法0100000100(个体基因型)X=8,4(个体表现型)构造适应度函数：物种对
2、生存环境的适应程度称为适应度，物种适应度高的将获得更多的繁殖机会，反之则少。通过目标函数的适当数学变换来构造适应度函数，f(x1,x2)=F(x1,x2),遗传算法实例,群体初始化个体的集合称为群体，群体内个体的数量称为群体的大小，生物的进化以群体进行。初始群体中的4个个体为（随机产生）：0110101101，1100011000，0100001000，1001110011,遗传算法实例,后代群体繁殖（1）选择：采用轮赌法 若：四个随机数为0.1，0.5，0.6，0.8,遗传算法实例,后代群体繁殖（2）交叉：两个同源染色体在某一个相同位置处被切断，其前后两串分别交叉组合形成两个新的染色体。,遗
3、传算法实例,后代群体繁殖（3）变异：复制时可能以很小的概率产生某些差错的现象。,遗传算法实例,群体进化收敛性判别计算前后两代群体的平均适应度变化率，如果连续几代的平均适应度变化率都很小，则可结束进化；最优个体转化为最优解在最后一代群体中选择最优个体，对最优个体进行转换，得到最优解和目标函数的最优值。,遗传算法的特点,以设计变量的编码作为运算对象；直接以目标函数值作为搜索信息；同时使用多个搜索点的搜索信息；使用概率搜索技术。,编码方法,把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码；编码决定了染色体的排列、解码方法；影响着遗传算子的运算方法及其效率；目前还没有一套
4、即严密又完整的指导理论及评价准则来帮助我们设计编码方案；编码方法分三类：二进制浮点数符号编码方法,编码方法二进制编码,编码符号集是由0和1所组成的二值符号集；符号串的长度与问题所要求的精度有关；若参数的取值范围是xmin,xmax,用长度为l的二进制编码符号串来表示该参数，则能产生2l种不同的编码，精度为：,0000000 xmin,0000011 xmin+,111111 2l-1 xmax,blbl-1bl-2b3b2b1 x,编码方法二进制编码,优点：编码、解码操作简单易行；遗传操作便于实现；符合最小字符集编码原则；便于利用模式定理对算法进行理论分析。缺点：存在汉明（Hamming）悬崖
5、；缺乏串长的微调功能；对于一些连续函数的优化问题，二进制编码不便于反映所求问题的结构特征。,编码方法格雷码,连续的两个整数的编码之间仅仅有一个码位是不同的。,由二进制码到格雷码的转换：,由格雷码到二进制码的转换：,表示异或运算,编码方法其他方法,符号编码：是指个体染色体编码串中的基因值取自一个无数值含义而只有代码含义的符号集。如：旅行商问题，n个城市记为：C1、C2、Cn，将各个城市的代号按其被访问的顺序连接在一起便可构成一个表示旅行路线的个体。如C1,C2,Cn就表示顺序访问城市C1、C2、Cn便于利用所求问题的专门知识；便于与相关近似算法之间的混合使用；遗传算子需要认真设计。浮点数编码：个
6、体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于设计的变量个数；多参数级编码：多参数级连编码多参数交叉编码,适应度函数构造方法,遗传算法在进行优化搜索中基本不利用外部信息，仅以适应度函数为依据，一般而言适应度函数f(x)是由目标函数F(x)变换而成的，对适应度函数值域的某种映射变换称为适应度的尺寸变换。几种常见的适应度函数构造方法直接法：f(x)=F(x)或 f(x)=F(x)可能不满足轮赌法有概率非负的要求；当待求解的函数其值在分布上相差很大时，平均适应度可能不利于体现种群的平均性能。界限构造法：f(x)=F(x)Cmin 或 f(x)=Cmax F(x)对直接法的改进，但存
7、在界限值估计困难、不可能精确的问题。倒数构造法：f(x)=1/(1+Cmax F(x)或 f(x)=1/(1+F(x)Cmin)适应度数值在01之间,适应度函数尺度变换,原因：遗传进化初级产生超强适应度的个体，而控制选择过程，影响算法的全局优化性能。遗传进化后期，个体的差异度较小，继续优化的可能性降低，容易获得某个局部的最优解。在不同的运行阶段需要对个体的适应度进行适当的扩大或缩小。线性变换：f=f+；满足以下条件：favg=favg，fmax=Cmult favg若某些个体的适应度远远小于平均值，变换后出现适应度为负的情况，可采用以下线性比例系数：,适应度函数约束条件处理,目前还未找到一种能
8、够处理各种约束条件的一般化方法，只能针对具体问题及约束选用不同方法。搜索空间限定法对搜索空间的大小加以限制，使搜索空间中表示一个个体的解与解空间中表示的一个可行解的点一一对应；实现方法：用编码方式来保证；用程序来保证。可行解变换法在由个体基因型到个体表现型的变换中，寻找一种从个体基因型到个体表现型之间多对一的变换关系，使进化过程中所产生的个体总能通过这种变换而转化成解空间中满足约束条件的一个可行解。罚函数法对解空间中无对应可行解的个体，在计算其适应度时，用罚函数来降低该个体适应度，减少其被遗传到下一代群体中的机会。f=f（满足条件）；f=f s（不满足条件）；,遗传操作选择,个体选择概率的确定
9、：比例分配法排序分配法个体选择的方法：轮赌法：首先计算累积概率，然后不断地产生0,1区间上的随机数来决定那个个体参加交配，直到需要选择的个体数目；遍历抽样法：设定指针的间距为1/n，第一个指针的位置由0，1/n区间上的均匀随机数决定。锦标赛选择法：每次随机地从种群中挑选一定数目的个体，然后最好的胜出作父个体，不断重复直到选出规定数量的个体位置；不需要计算选择概率和累积概率，但适应度最小的永远不会被选中。,遗传操作交叉/基因重组,交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体，是产生新个体的主要方法。交叉算子的设计和实现要求既不要太多地破坏个体编码串中表示优
10、良性状的模式，又要能产生出一些较好的模式，另外，交叉算子的设计要和个体的编码设计统一考虑。交叉算子的设计包括：如何确定交叉点的位置如何进行部分基因交换,遗传操作交叉/基因重组,离散重组：对于浮点数编码，子个体每个变量的数值以等概率随机地从两个父个体中挑选的方法。,遗传操作交叉/基因重组,中间重组：仅适用于浮点数编码。子个体1父个体11（父个体2父个体1）子个体2父个体22（父个体1父个体2）是比例因子，对于每个个体的每个变量都有重新选择一个值,遗传操作交叉/基因重组,线性重组：中间重组的特例，每个个体的所有变量都选择一个相同的值单点交叉：在相互配对的两个染色体编码串中随机设置一个交叉点，然后在
11、该点相互交换两个配对个体的部分染色体。,双点/多点交叉：在相互配对的两个染色体编码串中随机设置两个/多个交叉点，然后在该点相互交换两个配对个体的部分染色体。,遗传操作交叉/基因重组,均匀交叉：与离散重组交叉相同，只是离散重组交叉针对浮点数编码，而均匀交叉针对二进制编码。,遗传操作变异,在生物遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。遗传算法中的变异操作即模仿生物遗传和进化中的这个变异环节，引入变异算子来产生出新的个体。就产生新个体的能力方面来说：交叉运算是产生新个体的主要方
12、法，它决定了遗传算法的全局搜索能力，而变异运算只是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力。变异算子的设计包括：如何确定变异点的位置，如何进行基因值的替换。,遗传操作变异,基本位变异：最简单的变异算子，是指对个体编码串中以变异概率Pm随机指定的某一位基因值/符号作变异运算；对于二进制编码：某一位变异运算即对该位变量翻转；对于浮点算编码：X=X+,运行参数选择及自适应,基本遗传算法参数选择：编码方式采用固定长度的二进制编码。选择算子采用按适应度比例的轮赌法选择，交叉算子采用单点交叉算子，变异算子采用基本位变异算子。编码串长度L种群大小：种群中个体是数量；交叉概率Pc（0.40.99）
13、：个体参与交叉的概率（剩下的参与复制）；若Pc不变，则种群中参与交叉的个体数量 M Pc；变异概率Pm（0.00010.1）：通常讨论的是基因/字符的变异概率（相对于个体变异概率），基因/字符的突变概率是指个体中某个基因/字符发生变异的概率；中止代数/最大进化代数T。最优保存策略：当前群体中适应度最高的个体不参与交叉和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。自适应遗传算法：Pc和Pm等可以进行自适应调整。,基因模式定理,如果基因模式长度较短、基因模式阶次较低、基因模式的适应度值大于群体的平均适应度值，那么随着群体的进化，该基因模式在群体中出现的次
14、数将按指数规律增长。基因模式：在某些位置上具有确定特征的个体编码串的一个子集。如：H=11*1，描述了长度为5，且在位置1、2、5取值为1的所有字符串的集合11001,11011,11111。基因模式阶次：在基因模式H中具有确定基因值的位置数目，记为o(H)；基因模式长度：在基因模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离，记为(H)。H=11*1的长度是4，H=00*的长度是1。,基因模式定理,设当前群体A(t)中能与基因模式H匹配的个体数为m(H,t)，下一代群体A(t+1)中能与基因模式H匹配的个体数为m(H,t+1)，当前群体的平均适应度为=(f)/n，包含基因模
15、式的个体平均适应度为f(H)，选择算子完成选择操作后群体中的个体包含基因模式H的个体数为：m(H,t+1)=nm(H,t)f(H)/f=m(H,t)f(H)/假设f(H)=(1+c)，则有：m(H,t+1)=(1+c)m(H,t)=(1+c)2m(H,t-1),基因模式定理,交叉算子基因模式H的被破坏的最大概率为：(H)/(l-1)在单点杂交算子作用下的生成概率比大于 1 Pc(H)/(l-1)因此有基因模式H 在后代中出现的次数为：,1*0,编码长度l,基因模式H1,10,编码长度l,基因模式H2,基因模式定理,变异算子基因模式H的某个位置/字符发生变异的概率为Pm为，不发生变异的概率为1P
16、m；因而阶数为o(H)的基因模式不发生变异的概率为：,在遗传算法中，基因模式H在选择、杂交变异算子的共同作用下，能够在后代群体中出现的次数为：,旅行商问题的遗传算法方法1,编码符号编码直接采用所遍历城市的顺序排列来表示，其基因为n个记号，如城市名记为A、B、C、D、E、F、G、H、I。编码串L=(A,C,B,D,F,E,G,I,H)表示其旅行路线为：ACBDFEGIH,旅行商问题的遗传算法方法1,遗传操作循环交叉算子随机产生一个交叉位置；把父个体2对应的交叉位置上的值记为Za，把父个体1中出现Za的位置作为另一个交叉位置；不断重复，直到寻找到所有交叉位形成一个循环；交叉位置上的保持不变，其他位
17、置上的值按次序相互交换。,父个体1：L1=(A,B,C,D,E,F,G,H,I),父个体2：L2=(E,D,F,I,B,C,G,H,A),旅行商问题的遗传算法方法1,变异操作倒位变异：(A,B,C,D,E,F,G,H,I)(A,B,C,G,F,E,D,H,I)交换变异：(A,B,C,D,E,F,G,H,I)(A,B,C,G,E,F,D,H,I)插入变异：(A,B,C,D,E,F,G,H,I)(A,B,C,D,G,F,E,H,I),旅行商问题的遗传算法方法2,编码Grefenstette首先建立一个包含所有城市的列表F和空列表G；如果第一次访问的城市在F中的位置是g1，则把g1添到列表G中去，然
18、后从城市列表F中删去此城市，形成新的城市列表F；如果第二次访问的城市在F中的位置是g2，则把g2添到列表G的尾部，然后从城市列表F中删去此城市，又形成新的城市列表F；如此进行下去，直到F为空。序列G=(g1,g2,gn,)称为Grefenstette编码,F=(A,B,C,D,E,F,G,H,I),L1=(B,A,E,G,I,F,C,H,D),L2=(E,F,C,I,H,A,G,B,D),访问路线：,G1=(2,1,3,4,5,3,1,2,1),G2=(5,5,3,6,5,1,3,1,1),个体编码：,城市列表：,旅行商问题的遗传算法方法2,遗传操作单点交叉算子,L1=(B,A,E,G,I,F,C,H,D),L2=(E,F,C,I,H,A,G,B,D),访问路线,G1=(2,1,3,4,5,3,1,2,1),G2=(5,5,3,6,5,1,3,1,1),解码,交叉,遗传操作采用常规变异算子（基本位变异算子），如变异的位置是i，则变异的取值只能在1,2,n-i+1范围内。,个体编码串,
