遗传算法课件PPT

1第三章遗传算法2五.遗传算法的各种变形5.1其它编码方法5.2遗传运算中的问题5.3适值函数的标定(Scaling)5.4选择策略5.5停止准则六.应用遗传算法35.1其它编码方法①顺序编码：用1到N的自然数的不同顺序来编码，此种编码不允许重复，即且，又称自然数编码。该法适用范围很广：指派问题、旅行商问题和单机调度问题等等。合法性问题：是否符合采用的编码规则的问题五.GA的各种变形（1）jixxNxi,,2,14②实数编码：,R为实数集特征：方便运算简单，但反映不出基因的特征③整数编码类似于顺序编码，但编码允许重复适用于：新产品投入，时间优化，伙伴挑选例：3212345对顺序编码来说是不合法的，而对整数编码来说是合法的；010200不合法的01编码；五.GA的各种变形（2）RxxxxXin,,,,2155.2遗传运算中的问题在顺序编码遗传运算的过程中会遇见不合法的编码，应战的策略有二:拒绝或修复。例如：经双切点交叉后，后代编码不合法①21¦345¦6721¦125¦67②43¦125¦7643¦345¦76我们采用下面的修复策略使以上的编码合法。五.GA的各种变形（3）1P2P1C2C6①顺序编码的合法性修复：I.交叉修复策略，分为以下几种：a.部分映射交叉b.顺序交叉c.循环交叉五.GA的各种变形（4）7a.部分映射交叉(PMX)(PartiallyMappedCrossover)：用特别的修复程序解决简单的双切点交叉引起的非法性，步骤：⑴选切点X,Y；⑵交换中间部分；⑶确定映射关系；⑷将未换部分按映射关系恢复合法性。五.GA的各种变形（5）8PMX例题：五.GA的各种变形（6）映射关系：3-1，4-2，5-5则：43¦125¦6721¦345¦761C2C21¦345¦67¦125¦43¦125¦76¦345¦1P2PXY9b.顺序交叉(OX)OrderCrossover：可看做是带有不同修复程序的部分映射交叉的变形。OX步骤：⑴选切点X,Y；⑵交换中间部分；⑶从切点Y后第一个基因起列出原顺序，去掉已有基因；⑷从切点Y后第一个位置起，按顺序填入。五.GA的各种变形（7）10OX例题：五.GA的各种变形（8）列出基因：67213457643125则：34¦125¦6712¦345¦761C2C21¦345¦67¦125¦43¦125¦76¦345¦1P2PXY11OX的特点：较好的保留了相邻关系、先后关系,满足了TSP问题的需要,但不保留位值特征。五.GA的各种变形（9）12c.循环交叉(CX)CycleCrossover基本思想：子串位置上的值必须与父母的相同位置上的位值相等。CX步骤：⑴选的第一个元素作为的第一位，选的第一个元素作为的第一位；五.GA的各种变形（10）2P1P1C2C13⑵到中找的第一个元素赋给的相对位置…，重复此过程，直到上得到的第一个元素为止，称为一个循环；⑶对最前的基因按、基因轮替原则重复以上过程；⑷重复以上过程，直到所有位都完成。五.GA的各种变形（11）1P1P2P2P1C1P2P14CX例题：五.GA的各种变形（12）2453896172363986542713621P2P32，94，58，71629346346921C2C1P1P2P2P2953846713486592171C2C15CX的特点：与OX的特点不同的是，CX较好的保留了位值特征，适合指派问题；而OX较好的保留了相邻关系、先后关系满足了TSP问题的需要。五.GA的各种变形（13）16II.变异的修复策略a.换位变异(最常用)是随机地在染色体上选取两个位置，交换基因的位值。例：43125674512367b.移位变异：任选一位移到最前例：43125675431267五.GA的各种变形（14）17②实数编码的合法性修复I.交叉a.单切点交叉五.GA的各种变形（15）nkknkkxxyyyYyyxxxX,,,,,,,,,,,,1211211C2C1P2PnkknkkyyyyyYxxxxxX,,,,,,,,,,,,121121切点18b.双切点交叉(与单切点交叉类似)该方法最大的问题：如何在实际优化中保持可行性。五.GA的各种变形（16）1P2PnllkknllkkyyyyyyYxxxxxxX,,,,,,,,,,,,,,111111切点切点1C2CnllkknllkkyyxxyyYxxyyxxX,,,,,,,,,,,,,,11111119五.GA的各种变形（17）c.凸组合交叉：可以克服上面简单交叉操作导致的解的不可行性。约束是个凸集，可行性可以保持，但是分散性太差，又出现了向中间汇集的问题。01112YXZYXZ1x2x3x4x1x2x3x4x1P2PnkknkkyyyyyYxxxxxX,,,,,,,,,,,,12112120II.变异a.位值变异：任选一位加Δ（变异步长），例：五.GA的各种变形（18）aorNaaorUaU,0,,0nknkxxxxZxxxxX,,,,,,,,,212121b.向梯度方向变异缺点：只能用于目标函数可微的问题。例:对于最大化问题可采用如下操作：优点：考虑到了问题本身的性质，效率较高。但染色体种群也可能因此而趋于聚集，导致种群的多样性较差。五.GA的各种变形（19）aUxfXZ,0225.3适值函数的标定(Scaling)五.GA的各种变形（20）997999100210014321ffff0254444433422411ffffffffffff相对差别放大，选择压力变大，选优功能强化了标定相对差别小，选择压力小，选优功能弱化了23①标定的目的：使适值函数不会太大，有一定差别I.选择压力的概念：选择压力是种群好、坏个体被选中的概率之差，差大称为选择压力大。注意：上述概念中的“差大小”是相对于适值函数而言的。五.GA的各种变形（21）24II.局部搜索、广域搜索与选择压力的关系局部搜索与广域搜索是GA中的一对矛盾，只注重局部搜索很可能陷入局优，只注重广域搜索则会导致精确开发能力不强。因此，好的算法要将以上二者综合考虑。一般来说，算法开始时应注重广域搜索，通过使用较小的选择压力来实现；随着迭代的进行，逐步偏重于局部搜索，通过使用较大的选择压力来实现。五.GA的各种变形（22）25②适值的标定方法I.线性标定：函数表达式：,为目标函数，为适值函数五.GA的各种变形（23）baffff26a.对，=1，=+ξ，函数表达式：+ξ，b.对，=-1，=+ξ,函数表达式：+ξ，上述中的ξ是一个较小的数，目的是使种群中最差的个体仍然有繁殖的机会，增加种群的多样性。五.GA的各种变形（24）xfmaxminfxffxfminxfffmaxabminfabmaxf27II.动态线性标定(最常用)：线性标定中的参数随着迭代次数的增加而变化时就得到了动态线性标定优点：计算容易不占用时间函数表达式：，为迭代指标a.最常用最大化=1,函数表达式：五.GA的各种变形（25）kkbfafkkkfbminkakfffmin第k代的最小目标函数值28b.加入的意义（同线性标定中ξ的意义）加入使最坏个体仍有繁殖的可能，随的增大而减小c.的取值：，，，调节和，从而来调节五.GA的各种变形（26）kkkkkM0rkk1999.0,9.0rkMr29五.GA的各种变形（27）d.引入的目的：调节选择压力，即好坏个体选择概率的差，使广域搜索范围宽保持种群的多样性，而局域搜索细保持收敛性。如下图表示：开始：希望选择压力小后来：希望选择压力大kkkk30III.幂律标定：函数表达式：的取值，1时选择压力加大1时选择压力减小IV.对数标定：函数表达式：对数标定的作用：缩小目标函数值的差别五.GA的各种变形（28）fffaLnfb31V.指数标定：函数表达式：指数标定的作用：扩大差别VI.窗口技术：函数表达式：为前W代中的最小目标值，它考虑了各代的波动，这样具有记忆性五.GA的各种变形（29）caefbfwfaffwfwfminf32G.正规化技术：函数表达式：正规化技术的作用：将映射到(0,1)区间，抑制超级染色体正规化技术的实质：特殊的动态标定即其中：五.GA的各种变形（30）frffrfffminmaxminkkbfafrffakminmax1rffrfbkminmaxmin335.4选择策略传统的GA选择和遗传是一起进行的，即使后代不如父代，却无法纠正。下面介绍的选择策略都是先遗传后选择。这样，样本空间扩大了，可供选择的个体增多了。五.GA的各种变形（31）34I.截断选择：选择最好的前T个个体，让每一个有1/T的选择概率，平均得到NP/T个繁殖机会。例：NP=100,T=50即100名学生，成绩前50名的选出。每人的选择概率为1／50，有平均2个机会。缺点：这种方法将花费较多的时间在适应值的排序上。五.GA的各种变形（32）35II.顺序选择：a.步骤：⑴从好到坏排序所有个体⑵定义最好个体的选择概率为,则第个个体的选择概率为：五.GA的各种变形（33）11jqqjpqj36⑶由于有限时要归一化，则有下面的公式：，其中顺序选择的优点：选择概率可以离线计算，节省算法执行时间，且选择压力可控；缺点：把选择概率固定化了，选择压力不可调节。五.GA的各种变形（34）1111111qqqqNPjNPjNP11jjqqpNPqqq1137b.举例:且：采用旋轮法，随机产生当，选择个体五.GA的各种变形（35）ikiPPPP11.081.013.09.012.1.01.2321NoqqpNoqqpNoqpNo1121231231kkkppppppppppppppppp)1,0(Uki前i-1个个体的选择概率前i个个体的选择概率38III.正比选择：个体i的选择概率令：，用动态标定来调节选择压力，采用旋轮法来共同完成种群的选择。五.GA的各种变形（36）00PPNPiiiPPP1NPiiiiFFP1395.5停止准则①指定最大代数（常用）：该方法简单但不准确。②检查种群中适值的一致性：保持历史上最好的个体。计算公式：或第二种方法因很难实现，所以很少使用。五.GA的各种变形（37）ffmaxffi40背包问题个物品，对物品，价值为，重量为，背包容量是。如何选取物品装入背包，使背包中的价值最大。六.应用（1）niipiwW41模型:（二进制编码方法），装入物品，不装入物品六.应用（2）10ixii1,0..max11iiniiiniixWxwtsxp42例如，对于一个7个项目的背包问题，背包容量W=100，具体数据见下表，考察如下编码X=（1100110）这表示项目1、2、5和6被装入了背包，经过计算可知产生的解不可行。背包问题示例i1234567wi40503010104030pi4060101032060Pi/wi11.20.3310.30.5243①如何处理约束来保持可行性I.拒绝策略：可行解不易达到时，很难达到一个初始种群II.修复策略：将不可行解修复为可行的，但将失去多样性。六.应用（3）44III.惩罚策略：要求设计适当的惩罚函数，但设计不好会掩盖目标函数的优化。下面，我们将分别采用惩罚策略和解码法来处理上面的背包问题。六.应用（4）45a.罚函数法令适值函数，其中是目标函数令，其中注：与是的两个