,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 遗传算法,遗传算法基本思想,建立在自然选择原理和自然进化机制上的迭代式自适应概率性搜索方法；,生物进化理论：遗传、变异和适者生存；,遗传与进化的几个特点：,生物的所有遗传信息全部包含在其染色体中，染色体决定了生物的性状；,染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；,生物的繁殖过程是由其基因的复制过程来完成的；,通过同源染色体之间的交叉或染色体的变异会产生新的物种,对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多机会遗传到下一代。,遗传算法实例,个体编码：,分别采用,5,位二进制编码方法,0100000100(,个体基因型,),X,=8,4(,个体表现型,),构造适应度函数：,物种对生存环境的适应程度称为适应度，物种适应度高的将获得更多的繁殖机会，反之则少。,通过目标函数的适当数学变换来构造适应度函数，,f,(,x,1,x,2,)=,F,(,x,1,x,2,),遗传算法实例,群体初始化,个体的集合称为群体，群体内个体的数量称为群体的大小，生物的进化以群体进行。,初始群体中的,4,个个体为（随机产生）：,0110101101,，,1100011000,，,0100001000,，,1001110011,遗传算法实例,后代群体繁殖,（,1,）选择：采用轮赌法,若：四个随机数为,0.1,，,0.5,，,0.6,，,0.8,序号,个体,设计变量值,适应度值,选择概率,累积概率,实际选取次数,1,0110101101,13,13,338,0.144,0.144,1,2,1100011000,24,24,1152,0.492,0.636,2,3,0100001000,8,8,128,0.055,0.691,0,4,1001110011,19,19,722,0.309,1.000,1,累计值,2340,平均值,585,最大值,1152,遗传算法实例,后代群体繁殖,（,2,）交叉：两个同源染色体在某一个相同位置处被切断，其前后两串分别交叉组合形成两个新的染色体。,序号,父代,交叉位置,子代,子代序号,1,0110101101,第,2,位,之后,01,00011000,1,2,1100011000,11,10101101,2,2,1100011000,第,8,位,之后,11000110,11,3,4,1001110011,10011100,00,4,遗传算法实例,后代群体繁殖,（,3,）变异：复制时可能以很小的概率产生某些差错的现象。,序号,个体,设计变量值,适应度值,选择概率,累积概率,1,1,100011000,24,24,1152,0.282,0.282,2,1110101101,19,13,1010,0.247,0.247,3,1100011011,24,27,1305,0.320,0.320,4,1001110000,19,16,617,0.151,1.000,累计值,4084,平均值,1021,最大值,1305,遗传算法实例,群体进化收敛性判别,计算前后两代群体的平均适应度变化率，如果连续几代的平均适应度变化率都很小，则可结束进化；,最优个体转化为最优解,在最后一代群体中选择最优个体，对最优个体进行转换，得到最优解和目标函数的最优值。,遗传算法的特点,以设计变量的编码作为运算对象；,直接以目标函数值作为搜索信息；,同时使用多个搜索点的搜索信息；,使用概率搜索技术。,编码方法,把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码；,编码决定了染色体的排列、解码方法；影响着遗传算子的运算方法及其效率；,目前还没有一套即严密又完整的指导理论及评价准则来帮助我们设计编码方案；,编码方法分三类：,二进制,浮点数,符号编码方法,编码方法,二进制编码,编码符号集是由,0,和,1,所组成的二值符号集；,符号串的长度与问题所要求的精度有关；,若参数的取值范围是,x,min,x,max,用长度为,l,的二进制编码符号串来表示该参数，则能产生,2,l,种不同的编码，精度为：,000000,0 ,x,min,000001,1 ,x,min,+,111111,2,l,-1 ,x,max,b,l,b,l-,1,b,l-,2,b,3,b,2,b,1,x,编码方法,二进制编码,优点：,编码、解码操作简单易行；,遗传操作便于实现；,符合最小字符集编码原则；,便于利用模式定理对算法进行理论分析。,缺点：,存在汉明（,Hamming,）悬崖；,缺乏串长的微调功能；,对于一些连续函数的优化问题，二进制编码不便于反映所求问题的结构特征。,编码方法,格雷码,连续的两个整数的编码之间仅仅有一个码位是不同的。,由二进制码到格雷码的转换：,由格雷码到二进制码的转换：,二进制码,格雷码,x1,175,0010101111,0011111000,x2,177,0010110001,0011101001,表示异或运算,编码方法,其他方法,符号编码：是指个体染色体编码串中的基因值取自一个无数值含义而只有代码含义的符号集。,如：旅行商问题，,n,个城市记为：,C,1,、,C,2,、,、,C,n,，将各个城市的代号按其被访问的顺序连接在一起便可构成一个表示旅行路线的个体。如,C,1,C,2,C,n,就表示顺序访问城市,C,1,、,C,2,、,、,C,n,便于利用所求问题的专门知识；,便于与相关近似算法之间的混合使用；,遗传算子需要认真设计。,浮点数编码：个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于设计的变量个数；,多参数级编码：,多参数级连编码,多参数交叉编码,适应度函数,构造方法,遗传算法在进行优化搜索中基本不利用外部信息，仅以适应度函数为依据，,一般而言适应度函数,f,(,x,),是由目标函数,F,(,x,),变换而成的，对适应度函数值域的某种映射变换称为适应度的尺寸变换。,几种常见的适应度函数构造方法,直接法：,f,(,x,)=,F,(,x,),或,f,(,x,)=,F,(,x,),可能不满足轮赌法有概率非负的要求；,当待求解的函数其值在分布上相差很大时，平均适应度可能不利于体现种群的平均性能。,界限构造法：,f,(,x,)=,F,(,x,),C,min,或,f,(,x,)=,C,max,F,(,x,),对直接法的改进，但存在界限值估计困难、不可能精确的问题。,倒数构造法：,f,(,x,)=1/(1+,C,max,F,(,x,),或,f,(,x,)=1/(1+,F,(,x,),C,min,),适应度数值在,0,1,之间,适应度函数,尺度变换,原因：遗传进化初级产生超强适应度的个体，而控制选择过程，影响算法的全局优化性能。遗传进化后期，个体的差异度较小，继续优化的可能性降低，容易获得某个局部的最优解。在不同的运行阶段需要对个体的适应度进行适当的扩大或缩小。,线性变换：,f,=,f+,；,满足以下条件：,f,avg,=,f,avg,，,f,max,=,C,mult,f,avg,若某些个体的适应度远远小于平均值，变换后出现适应度为负的情况，可采用以下线性比例系数：,适应度函数,约束条件处理,目前还未找到一种能够处理各种约束条件的一般化方法，只能针对具体问题及约束选用不同方法。,搜索空间限定法,对搜索空间的大小加以限制，使搜索空间中表示一个个体的解与解空间中表示的一个可行解的点一一对应；,实现方法：用编码方式来保证；用程序来保证。,可行解变换法,在由个体基因型到个体表现型的变换中，寻找一种从个体基因型到个体表现型之间多对一的变换关系，使进化过程中所产生的个体总能通过这种变换而转化成解空间中满足约束条件的一个可行解。,罚函数法,对解空间中无对应可行解的个体，在计算其适应度时，用罚函数来降低该个体适应度，减少其被遗传到下一代群体中的机会。,f,=,f,（满足条件）；,f,=,f,s,（不满足条件）；,遗传操作,选择,个体选择概率的确定：,比例分配法,排序分配法,个体选择的方法：,轮赌法：首先计算累积概率，然后不断地产生,0,1,区间上的随机数来决定那个个体参加交配，直到需要选择的个体数目；,遍历抽样法：设定指针的间距为,1/n,，第一个指针的位置由,0,，,1/n,区间上的均匀随机数决定。,锦标赛选择法：每次随机地从种群中挑选一定数目的个体，然后最好的胜出作父个体，不断重复直到选出规定数量的个体位置；不需要计算选择概率和累积概率，但适应度最小的永远不会被选中。,遗传操作,交叉,/,基因重组,交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体，是产生新个体的主要方法。,交叉算子的设计和实现要求既不要太多地破坏个体编码串中表示优良性状的模式，又要能产生出一些较好的模式，另外，交叉算子的设计要和个体的编码设计统一考虑。,交叉算子的设计包括：,如何确定交叉点的位置,如何进行部分基因交换,遗传操作,交叉,/,基因重组,离散重组：对于浮点数编码，子个体每个变量的数值以等概率随机地从两个父个体中挑选的方法。,变量,1,变量,2,变量,3,变量,4,父个体,1,12,45,34,77,父个体,2,23,18,88,75,变量,1,变量,2,变量,3,变量,4,子个体,1,23,18,88,77,子个体,2,12,45,34,75,变量,1,变量,2,变量,3,变量,4,掩码,0,0,0,1,遗传操作,交叉,/,基因重组,中间重组：仅适用于浮点数编码。,子个体,1,父个体,1,1,（,父个体,2,父个体,1,）,子个体,2,父个体,2,2,（,父个体,1,父个体,2,）,是比例因子，对于每个个体的每个变量都有重新选择一个,值,变量,1,变量,2,变量,3,变量,4,子个体,1,13.1,31.5,98.8,77.2,子个体,2,19.7,36.9,55.6,75.8,变量,1,变量,2,变量,3,变量,4,父个体,1,12,45,34,77,父个体,2,23,18,88,75,变量,1,变量,2,变量,3,变量,4,1,0.1,0.5,1.2,0.1,2,0.3,0.7,0.6,0.4,遗传操作,交叉,/,基因重组,线性重组：中间重组的特例，,每个个体的所有变量都选择一个相同的,值,单点交叉：在相互配对的两个染色体编码串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。,父个体,子个体,1,01110011010,01110100101,2,10101100101,10101011010,双点,/,多点交叉：在相互配对的两个染色体编码串中随机设置两个,/,多个交叉点，然后在该点相互交换两个配对个体的部分染色体。,父个体,子个体,1,01110011010,01101100101,2,10101100101,10110011010,遗传操作,交叉,/,基因重组,均匀交叉：与离散重组交叉相同，只是离散重组交叉针对浮点数编码，而均匀交叉针对二进制编码。,父个体,掩码样本,子个体,1,01110011010,01100011010,11101111111,2,10101100101,00110000000,遗传操作,变异,在生物遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。,遗传算法中的变异操作即模仿生物遗传和进化中的这个变异环节，引入变异算子来产生出新的个体。,就产生新个体的能力方面来说：交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力，而变异运算只是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力。,变异算子的设计包括：,如何确定变异点的位置，,如何进行基因值的替换。,遗传操作,变异,基本位变异：最简单的变异算子，是指对个体编码串中以变异概率,P,m,随机指定的某一位基因值,/,符号作变异运算；,对于二进制编码：某一位变异运算即对该位