第4章遗传算法.ppt

《第4章遗传算法.ppt》由会员分享，可在线阅读，更多相关《第4章遗传算法.ppt（35页珍藏版）》请在优知文库上搜索。

1、遗传算法基本思想n建立在自然选择原理和自然进化机制上的迭代式自适应概率性搜索方法；n生物进化理论：遗传、变异和适者生存；n遗传与进化的几个特点：生物的所有遗传信息全部包含在其染色体中，染色体决定了生物的性状；染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；生物的繁殖过程是由其基因的复制过程来完成的；通过同源染色体之间的交叉或染色体的变异会产生新的物种对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多机会遗传到下一代。遗传算法实例222121),(maxxxxxF31,30,2,1,0,21xx21,xxX n个体编码：分别采用分别采用5 5位二进制编码方法位二

2、进制编码方法0100000100(0100000100(个体基因型个体基因型)X X=8,4(=8,4(个体表现型个体表现型)n构造适应度函数：物种对生存环境的适应程度称为适应度，物种适应度物种对生存环境的适应程度称为适应度，物种适应度高的将获得更多的繁殖机会，反之则少。高的将获得更多的繁殖机会，反之则少。通过目标函数的适当数学变换来构造适应度函数，通过目标函数的适当数学变换来构造适应度函数，f(x1,x2)=)=F(x1,x2)遗传算法实例222121),(maxxxxxF31,30,2,1,0,21xx21,xxX n群体初始化个体的集合称为群体，群体内个体的数量称为群体的个体的集合称为群

3、体，群体内个体的数量称为群体的大小，生物的进化以群体进行。大小，生物的进化以群体进行。初始群体中的初始群体中的4 4个个体为（随机产生）：个个体为（随机产生）：01101011010110101101，11000110001100011000，01000010000100001000，10011100111001110011遗传算法实例222121),(maxxxxxF31,30,2,1,0,21xx21,xxX n后代群体繁殖（1 1）选择：采用轮赌法）选择：采用轮赌法 若：四个随机数为若：四个随机数为0.10.1，0.50.5，0.60.6，0.80.8序号个体设计变量值适应度值选择概率累

4、积概率 实际选取次数1011010110113,133380.1440.14412110001100024,2411520.4920.6362301000010008,81280.0550.69104100111001119,197220.3091.0001累计值2340平均值585最大值1152遗传算法实例222121),(maxxxxxF31,30,2,1,0,21xx21,xxX n后代群体繁殖（2 2）交叉：两个同源染色体在某一个相同位置处被切断，）交叉：两个同源染色体在某一个相同位置处被切断，其前后两串分别交叉组合形成两个新的染色体。其前后两串分别交叉组合形成两个新的染色体。序号父代

5、交叉位置子代子代序号10110101101第2位之后01000110001211000110001110101101221100011000第8位之后110001101134100111001110011100004遗传算法实例222121),(maxxxxxF31,30,2,1,0,21xx21,xxX n后代群体繁殖（3 3）变异：复制时可能以很小的概率产生某些差错的现）变异：复制时可能以很小的概率产生某些差错的现象。象。序号个体设计变量值适应度值选择概率累积概率1110001100024,2411520.2820.2822111010110119,1310100.2470.2473110

6、001101124,2713050.3200.3204100111000019,166170.1511.000累计值4084平均值1021最大值1305遗传算法实例222121),(maxxxxxF31,30,2,1,0,21xx21,xxX n群体进化收敛性判别计算前后两代群体的平均适应度变化率，如果连续几计算前后两代群体的平均适应度变化率，如果连续几代的平均适应度变化率都很小，则可结束进化；代的平均适应度变化率都很小，则可结束进化；n最优个体转化为最优解在最后一代群体中选择最优个体，对最优个体进行转在最后一代群体中选择最优个体，对最优个体进行转换，得到最优解和目标函数的最优值。换，得到最优

7、解和目标函数的最优值。遗传算法的特点n以设计变量的编码作为运算对象；n直接以目标函数值作为搜索信息；n同时使用多个搜索点的搜索信息；n使用概率搜索技术。编码方法n把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码；n编码决定了染色体的排列、解码方法；影响着遗传算子的运算方法及其效率；n目前还没有一套即严密又完整的指导理论及评价准则来帮助我们设计编码方案；n编码方法分三类：二进制浮点数符号编码方法编码方法二进制编码n编码符号集是由0和1所组成的二值符号集；n符号串的长度与问题所要求的精度有关；n若参数的取值范围是xmin,xmax,用长度为l的二进制编码符号串来表示该

8、参数，则能产生2l种不同的编码，精度为：12minmaxlxx0000000 xmin0000011 xmin+111111 2l-1 xmaxliiibxx11min2blbl-1bl-2b3b2b1 x编码方法二进制编码n优点：编码、解码操作简单易行；遗传操作便于实现；符合最小字符集编码原则；便于利用模式定理对算法进行理论分析。n缺点：存在汉明（Hamming）悬崖；缺乏串长的微调功能；对于一些连续函数的优化问题，二进制编码不便于反映所求问题的结构特征。编码方法格雷码n连续的两个整数的编码之间仅仅有一个码位是不同的。12321ggggggmmm12321bbbbbbmmm)1,2,1(1m

9、mibbgbgiiimm)1,2,1(1mmigbbgbiiimm由二进制码到格雷码的转换：由格雷码到二进制码的转换：)2(modmijjigb二进制码格雷码x117500101011110011111000 x217700101100010011101001表示异或运算编码方法其他方法n符号编码：是指个体染色体编码串中的基因值取自一个无数值含义而只有代码含义的符号集。n如：旅行商问题，n个城市记为：C1、C2、Cn，将各个城市的代号按其被访问的顺序连接在一起便可构成一个表示旅行路线的个体。如C1,C2,Cn就表示顺序访问城市C1、C2、Cn便于利用所求问题的专门知识；便于与相关近似算法之间的

10、混合使用；遗传算子需要认真设计。n浮点数编码：个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于设计的变量个数；n多参数级编码：多参数级连编码多参数交叉编码适应度函数构造方法n遗传算法在进行优化搜索中基本不利用外部信息，仅以适应度函数为依据，n一般而言适应度函数f(x)是由目标函数F(x)变换而成的，对适应度函数值域的某种映射变换称为适应度的尺寸变换。n几种常见的适应度函数构造方法n直接法：f(x)=F(x)或 f(x)=F(x)可能不满足轮赌法有概率非负的要求；当待求解的函数其值在分布上相差很大时，平均适应度可能不利于体现种群的平均性能。n界限构造法：f(x)=F(x)Cmi

11、n 或 f(x)=Cmax F(x)对直接法的改进，但存在界限值估计困难、不可能精确的问题。n倒数构造法：f(x)=1/(1+Cmax F(x)或 f(x)=1/(1+F(x)Cmin)适应度数值在01之间适应度函数尺度变换n原因：遗传进化初级产生超强适应度的个体，而控制选择过程，影响算法的全局优化性能。遗传进化后期，个体的差异度较小，继续优化的可能性降低，容易获得某个局部的最优解。在不同的运行阶段需要对个体的适应度进行适当的扩大或缩小。n线性变换：f=f+；满足以下条件：favg=favg，fmax=Cmult favg若某些个体的适应度远远小于平均值，变换后出现适应度为负的情况，可采用以下

12、线性比例系数：avgavgavgmultavgavgmultffffCffffCmaxmaxmax)()1(minmaxminminmaxfffffffavgavg适应度函数约束条件处理n目前还未找到一种能够处理各种约束条件的一般化方法，只能针对具体问题及约束选用不同方法。n搜索空间限定法对搜索空间的大小加以限制，使搜索空间中表示一个个体的解与解空间中表示的一个可行解的点一一对应；实现方法：用编码方式来保证；用程序来保证。n可行解变换法在由个体基因型到个体表现型的变换中，寻找一种从个体基因型到个体表现型之间多对一的变换关系，使进化过程中所产生的个体总能通过这种变换而转化成解空间中满足约束条件的

13、一个可行解。n罚函数法对解空间中无对应可行解的个体，在计算其适应度时，用罚函数来降低该个体适应度，减少其被遗传到下一代群体中的机会。f=f（满足条件）；f=f s（不满足条件）；遗传操作选择n个体选择概率的确定：比例分配法排序分配法n个体选择的方法：轮赌法：首先计算累积概率，然后不断地产生0,1区间上的随机数来决定那个个体参加交配，直到需要选择的个体数目；遍历抽样法：设定指针的间距为1/n，第一个指针的位置由0，1/n区间上的均匀随机数决定。锦标赛选择法：每次随机地从种群中挑选一定数目的个体，然后最好的胜出作父个体，不断重复直到选出规定数量的个体位置；不需要计算选择概率和累积概率，但适应度最小

14、的永远不会被选中。MiiMiiiiijMPffP111遗传操作交叉/基因重组n交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体，是产生新个体的主要方法。n交叉算子的设计和实现要求既不要太多地破坏个体编码串中表示优良性状的模式，又要能产生出一些较好的模式，另外，交叉算子的设计要和个体的编码设计统一考虑。n交叉算子的设计包括：如何确定交叉点的位置如何进行部分基因交换遗传操作交叉/基因重组n离散重组：对于浮点数编码，子个体每个变量的数值以等概率随机地从两个父个体中挑选的方法。变量1变量2变量3变量4父个体112453477父个体223188875变量1变量2变量3

15、变量4子个体123188877子个体212453475变量1变量2变量3变量4掩码0001遗传操作交叉/基因重组n中间重组：仅适用于浮点数编码。子个体1父个体11（父个体2父个体1）子个体2父个体22（父个体1父个体2）n是比例因子，对于每个个体的每个变量都有重新选择一个值变量1变量2变量3变量4子个体113.131.598.877.2子个体219.736.955.675.8变量1变量2变量3变量4父个体112453477父个体223188875变量1变量2变量3变量410.10.51.20.120.30.70.60.4遗传操作交叉/基因重组n线性重组：中间重组的特例，每个个体的所有变量都选择

16、一个相同的值n单点交叉：在相互配对的两个染色体编码串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。父个体子个体1 01110011010 011101001012 10101100101 10101011010n双点/多点交叉：在相互配对的两个染色体编码串中随机设置两个/多个交叉点，然后在该点相互交换两个配对个体的部分染色体。父个体子个体1 01110011010 011011001012 10101100101 10110011010遗传操作交叉/基因重组n均匀交叉：与离散重组交叉相同，只是离散重组交叉针对浮点数编码，而均匀交叉针对二进制编码。父个体掩码样本子个体101110011010011000110101110111111121010110010100110000000遗传操作变异n在生物遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。n遗传算法中的变异操作即模仿生物遗传和进化中的这个变异环节，引入变异算子来产生出新的个体。n就产生新个体的能力