第4章遗传算法.ppt

第第4 4章章 遗传算法遗传算法遗传算法基本思想n建立在自然选择原理和自然进化机制上的迭代式自适应概率性搜索方法；n生物进化理论：遗传、变异和适者生存；n遗传与进化的几个特点：Ø生物的所有遗传信息全部包含在其染色体中，染色体决定了生物的性状；Ø染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；Ø生物的繁殖过程是由其基因的复制过程来完成的；Ø通过同源染色体之间的交叉或染色体的变异会产生新的物种Ø对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多机会遗传到下一代遗传算法实例n个体编码：Ø分别采用5位二进制编码方法Ø0100000100(个体基因型)→X=[8,4](个体表现型)n构造适应度函数：Ø物种对生存环境的适应程度称为适应度，物种适应度高的将获得更多的繁殖机会，反之则少Ø通过目标函数的适当数学变换来构造适应度函数，f(x1,x2)=F(x1,x2)遗传算法实例n群体初始化Ø个体的集合称为群体，群体内个体的数量称为群体的大小，生物的进化以群体进行Ø初始群体中的4个个体为（随机产生）： 0110101101，1100011000，0100001000，1001110011遗传算法实例n后代群体繁殖（1）选择：采用轮赌法 若：四个随机数为0.1，0.5，0.6，0.8序号个体设计变量值适应度值选择概率累积概率 实际选取次数10110101101[13,13]3380.1440.144121100011000[24,24]11520.4920.636230100001000[8,8]1280.0550.691041001110011[19,19]7220.3091.0001累计值2340平均值585最大值1152遗传算法实例n后代群体繁殖（2）交叉：两个同源染色体在某一个相同位置处被切断，其前后两串分别交叉组合形成两个新的染色体。

序号父代交叉位置子代子代序号10110101101第2位之后01000110001’2110001100011101011012’21100011000第8位之后11000110113’4100111001110011100004’遗传算法实例n后代群体繁殖（3）变异：复制时可能以很小的概率产生某些差错的现象序号个体设计变量值适应度值选择概率累积概率1’1100011000[24,24]11520.2820.2822’1110101101[19,13]10100.2470.2473’1100011011[24,27]13050.3200.3204’1001110000[19,16]6170.1511.000累计值4084平均值1021最大值1305遗传算法实例n群体进化收敛性判别Ø计算前后两代群体的平均适应度变化率，如果连续几代的平均适应度变化率都很小，则可结束进化；n最优个体转化为最优解Ø在最后一代群体中选择最优个体，对最优个体进行转换，得到最优解和目标函数的最优值遗传算法的特点n以设计变量的编码作为运算对象；n直接以目标函数值作为搜索信息；n同时使用多个搜索点的搜索信息；n使用概率搜索技术。

编码方法n把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码；n编码决定了染色体的排列、解码方法；影响着遗传算子的运算方法及其效率；n目前还没有一套即严密又完整的指导理论及评价准则来帮助我们设计编码方案；n编码方法分三类：Ø二进制Ø浮点数Ø符号编码方法编码方法－二进制编码n编码符号集是由0和1所组成的二值符号集；n符号串的长度与问题所要求的精度有关；n若参数的取值范围是[xmin,xmax],用长度为l的二进制编码符号串来表示该参数，则能产生2l种不同的编码，精度为：000…000＝0 → xmin000…001＝1 → xmin+δ111…111＝ 2l-1 → xmaxblbl-1bl-2…b3b2b1 → x编码方法－二进制编码n优点：Ø编码、解码操作简单易行；Ø遗传操作便于实现；Ø符合最小字符集编码原则；Ø便于利用模式定理对算法进行理论分析n缺点：Ø存在汉明（Hamming）悬崖；Ø缺乏串长的微调功能；Ø对于一些连续函数的优化问题，二进制编码不便于反映所求问题的结构特征编码方法－格雷码n连续的两个整数的编码之间仅仅有一个码位是不同的。

由二进制码到格雷码的转换：由格雷码到二进制码的转换：二进制码格雷码x117500101011110011111000x217700101100010011101001表示异或运算编码方法－其他方法n符号编码：是指个体染色体编码串中的基因值取自一个无数值含义而只有代码含义的符号集n如：旅行商问题，n个城市记为：C1、C2、…、Cn ，将各个城市的代号按其被访问的顺序连接在一起便可构成一个表示旅行路线的个体如{C1,C2,…,Cn}就表示顺序访问城市C1、C2、…、CnØ便于利用所求问题的专门知识；Ø便于与相关近似算法之间的混合使用；Ø遗传算子需要认真设计n浮点数编码：个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于设计的变量个数；n多参数级编码：Ø多参数级连编码Ø多参数交叉编码适应度函数－构造方法n遗传算法在进行优化搜索中基本不利用外部信息，仅以适应度函数为依据，n一般而言适应度函数f(x)是由目标函数F(x)变换而成的，对适应度函数值域的某种映射变换称为适应度的尺寸变换n几种常见的适应度函数构造方法n直接法： f (x) = F(x) 或 f (x) = −F(x)Ø可能不满足轮赌法有概率非负的要求；Ø当待求解的函数其值在分布上相差很大时，平均适应度可能不利于体现种群的平均性能。

n界限构造法： f (x) = F(x) − Cmin 或 f (x) =Cmax− F(x) Ø对直接法的改进，但存在界限值估计困难、不可能精确的问题n倒数构造法： f (x) =1/(1+Cmax− F(x)) 或 f (x) =1/(1+ F(x) − Cmin )Ø适应度数值在0～1之间适应度函数－尺度变换n原因：遗传进化初级产生超强适应度的个体，而控制选择过程，影响算法的全局优化性能遗传进化后期，个体的差异度较小，继续优化的可能性降低，容易获得某个局部的最优解在不同的运行阶段需要对个体的适应度进行适当的扩大或缩小n线性变换：f′= αf +β ；Ø满足以下条件：f′avg= favg， f′max= Cmult favgØ若某些个体的适应度远远小于平均值，变换后出现适应度为负的情况，可采用以下线性比例系数：适应度函数－约束条件处理n目前还未找到一种能够处理各种约束条件的一般化方法，只能针对具体问题及约束选用不同方法n搜索空间限定法Ø对搜索空间的大小加以限制，使搜索空间中表示一个个体的解与解空间中表示的一个可行解的点一一对应；Ø实现方法：用编码方式来保证；用程序来保证。

n可行解变换法Ø在由个体基因型到个体表现型的变换中，寻找一种从个体基因型到个体表现型之间多对一的变换关系，使进化过程中所产生的个体总能通过这种变换而转化成解空间中满足约束条件的一个可行解n罚函数法Ø对解空间中无对应可行解的个体，在计算其适应度时，用罚函数来降低该个体适应度，减少其被遗传到下一代群体中的机会Øf′= f（满足条件）； f′= f − s（不满足条件）；遗传操作－选择n个体选择概率的确定：Ø比例分配法Ø排序分配法n个体选择的方法：Ø轮赌法：首先计算累积概率，然后不断地产生[0,1]区间上的随机数来决定那个个体参加交配，直到需要选择的个体数目；Ø遍历抽样法：设定指针的间距为1/n，第一个指针的位置由[0，1/n]区间上的均匀随机数决定Ø锦标赛选择法：每次随机地从种群中挑选一定数目的个体，然后最好的胜出作父个体，不断重复直到选出规定数量的个体位置；不需要计算选择概率和累积概率，但适应度最小的永远不会被选中遗传操作－交叉/基因重组n交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体，是产生新个体的主要方法n交叉算子的设计和实现要求既不要太多地破坏个体编码串中表示优良性状的模式，又要能产生出一些较好的模式，另外，交叉算子的设计要和个体的编码设计统一考虑。

n交叉算子的设计包括：Ø如何确定交叉点的位置Ø如何进行部分基因交换遗传操作－交叉/基因重组n离散重组：对于浮点数编码，子个体每个变量的数值以等概率随机地从两个父个体中挑选的方法变量1变量2变量3变量4父个体112453477父个体223188875变量1变量2变量3变量4子个体123188877子个体212453475变量1变量2变量3变量4掩码0001遗传操作－交叉/基因重组n中间重组：仅适用于浮点数编码 子个体1＝父个体1＋α1（父个体2－父个体1） 子个体2＝父个体2＋α2（父个体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变量4α10.10.51.2－0.1α20.30.70.60.4遗传操作－交叉/基因重组n线性重组：中间重组的特例，每个个体的所有变量都选择一个相同的α值n单点交叉：在相互配对的两个染色体编码串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。

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

n变异算子的设计包括：①如何确定变异点的位置，②如何进行基因值的替换遗传操作－变异n基本位变异：最简单的变异算子，是指对个体编码串中以变异概率Pm随机指定的某一位基因值/符号作变异运算；n对于二进制编码：某一位变异运算即对该位变量翻转；n对于浮点算编码：X′= X +Δ运行参数选择及自适应n基本遗传算法参数选择：编码方式采用固定长度的二进制编码选择算子采用按适应度比例的轮赌法选择，交叉算子采用单点交叉算子，变异算子采用基本位变异算子Ø编码串长度LØ种群大小：种群中个体是数量；Ø交叉概率Pc（0.4～0.99）：个体参与交叉的概率（剩下的参与复制）；若Pc不变，则种群中参与交叉的个体数量＝ M× Pc；Ø变异概率Pm（0.0001～0.1）：通常讨论的是基因/字符的变异概率（相对于个体变异概率），基因/字符的突变概率是指个体中某个基因/字符发生变异的概率；Ø中止代数/最大进化代数Tn最优保存策略：最优保存策略：当前群体中适应度最高的个体不参与交叉和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体n自适应遗传算法： Pc和Pm等可以进行自适应调整。

基因模式定理n如果基因模式长度较短、基因模式阶次较低、基因模式的适应度值大于群体的平均适应度值，那么随着群体的进化，该基因模式在群体中出现的次数将按指数规律增长Ø基因模式：在某些位置上具有确定特征的个体编码串的一个子集如：H=11**1，描述了长度为5，且在位置1、2、5取值为1的所有字符串的集合{11001, 11011, 11111}Ø基因模式阶次：在基因模式H中具有确定基因值的位置数目，记为o(H)；Ø基因模式长度：在基因模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离，记为δ(H) H=11**1的长度是4， H=00***的长度是1基因模式定理n设当前群体A(t)中能与基因模式H匹配的个体数为m(H,t)，下一代群体A(t+1)中能与基因模式H匹配的个体数为m(H,t+1) ，当前群体的平均适应度为η=(∑f )/n，包含基因模式的个体平均适应度为f(H)，①①选择算子算子Ø完成选择操作后群体中的个体包含基因模式H的个体数为： m(H,t+1) = n·m(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)2·m(H,t-1)基因模式定理②②交叉算子交叉算子Ø基因模式H的被破坏的最大概率为： δ(H) / (l-1)Ø在单点杂交算子作用下的生成概率比大于 1 － Pc·δ(H)/(l-1)Ø因此有基因模式H 在后代中出现的次数为： …1****0 …编码长度l基因模式H1…10 …编码长度l基因模式H2基因模式定理③③变异算子异算子Ø基因模式H的某个位置/字符发生变异的概率为Pm为，不发生变异的概率为1−Pm；因而阶数为o(H)的基因模式不发生变异的概率为： Ø在遗传算法中，基因模式H在选择、杂交＆变异算子的共同作用下，能够在后代群体中出现的次数为： 旅行商问题的遗传算法－方法1n编码－符号编码Ø直接采用所遍历城市的顺序排列来表示，其基因为n个记号，Ø如城市名记为A、B、C、D、E、F、G、H、I。

Ø编码串L=(A,C,B,D,F,E,G,I,H)表示其旅行路线为：A→C→B→D→F→E→G→I→H 旅行商问题的遗传算法－方法1n遗传操作－循环交叉算子Ø随机产生一个交叉位置；Ø把父个体2对应的交叉位置上的值记为Za，Ø把父个体1中出现Za的位置作为另一个交叉位置；Ø不断重复，直到寻找到所有交叉位形成一个循环；Ø交叉位置上的保持不变，其他位置上的值按次序相互交换父个体1：L1=(A,B,C,D,E,F,G,H,I)父个体2：L2=(E,D,F,I,B,C,G,H,A) 子个体1：L1=(A,B,F,D,E,C,G,H,I)′ 子个体2：L2=(E,D,C,I,B,F,G,H,A)′旅行商问题的遗传算法－方法1n变异操作Ø倒位变异： (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)旅行商问题的遗传算法－方法2n编码－GrefenstetteØ首先建立一个包含所有城市的列表F和空列表G；Ø如果第一次访问的城市在F中的位置是g1，则把g1添到列表G中去，然后从城市列表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)个体编码：城市列表：旅行商问题的遗传算法－方法2n遗传操作－单点交叉算子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)′G1=(2,1,3,4,5,1,3,3,1)G2=(5,5,3,6,5,3,1,2,1)′L1=(B,A,E,G,I,C,H,D,F)′L2=(E,F,C,I,H,D,A,G,B)′解码交叉n遗传操作Ø采用常规变异算子（基本位变异算子），如变异的位置是i，则变异的取值只能在[1, 2, …, n-i+1]范围内个体编码串。