遗传算法课件ppt

《遗传算法课件ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章遗传算法1五.遗传算法的各种变形5.1其它编码方法5.2遗传运算中的问题5.3适值函数的标定(Scaling)5.4选择策略5.5停止准则六.应用遗传算法25.1其它编码方法顺序编码：用1到N的自然数的不同顺序来编码，此种编码不允许重复，即且，又称自然数编码。该法适用范围很广：指派问题、旅行商问题和单机调度问题等等。合法性问题：是否符合采用的编码规则的问题五.GA的各种变形（1）3实数编码：,R为实数集特征：方便运算简单，但反映不出基因的特征整数编码类似于顺序编码，但编码允许重复适用于：新产品投入，时间优化，伙伴挑选例：3212345对顺序编码来说是不合法的，而对整数编码来说

2、是合法的；010200不合法的01编码；五.GA的各种变形（2）45.2遗传运算中的问题在顺序编码遗传运算的过程中会遇见不合法的编码，应战的策略有二:拒绝或修复。例如：经双切点交叉后，后代编码不合法21¦345¦6721¦125¦6743¦125¦7643¦345¦76我们采用下面的修复策略使以上的编码合法。五.GA的各种变形（3）5顺序编码的合法性修复：交叉修复策略，分为以下几种：部分映射交叉顺序交叉循环交叉五.GA的各种变形（4）6部分映射交叉(PMX)(PartiallyMappedCrossover)：用特别的修复程序解决简单的双切点交叉引起的非法性，步骤：⑴选切点X,Y；⑵

3、交换中间部分；⑶确定映射关系；⑷将未换部分按映射关系恢复合法性。五.GA的各种变形（5）7PMX例题：五.GA的各种变形（6）映射关系：3-1，4-2，5-5则：43¦125¦6721¦345¦7621¦345¦67¦125¦43¦125¦76¦345¦XY8顺序交叉(OX)OrderCrossover：可看做是带有不同修复程序的部分映射交叉的变形。OX步骤：⑴选切点X,Y；⑵交换中间部分；⑶从切点Y后第一个基因起列出原顺序，去掉已有基因；⑷从切点Y后第一个位置起，按顺序填入。五.GA的各种变形（7）9OX例题：五.GA的各种变形（8）列出基因：67213457643125则：34¦

4、125¦6712¦345¦7621¦345¦67¦125¦43¦125¦76¦345¦XY10OX的特点：较好的保留了相邻关系、先后关系,满足了TSP问题的需要,但不保留位值特征。五.GA的各种变形（9）11循环交叉(CX)CycleCrossover基本思想：子串位置上的值必须与父母的相同位置上的位值相等。CX步骤：⑴选的第一个元素作为的第一位，选的第一个元素作为的第一位；五.GA的各种变形（10）12⑵到中找的第一个元素赋给的相对位置…，重复此过程，直到上得到的第一个元素为止，称为一个循环；⑶对最前的基因按、基因轮替原则重复以上过程；⑷重复以上过程，直到所有位都完成。五.GA的各

5、种变形（11）13CX例题：五.GA的各种变形（12）24538961723639865427136232，94，58，716293463469229538467134865921714CX的特点：与OX的特点不同的是，CX较好的保留了位值特征，适合指派问题；而OX较好的保留了相邻关系、先后关系满足了TSP问题的需要。五.GA的各种变形（13）15变异的修复策略换位变异(最常用)是随机地在染色体上选取两个位置，交换基因的位值。例：43125674512367移位变异：任选一位移到最前例：43125675431267五.GA的各种变形（14）16实数编码的合法性修复交叉单切点交叉五.G

6、A的各种变形（15）切点17双切点交叉(与单切点交叉类似)该方法最大的问题：如何在实际优化中保持可行性。五.GA的各种变形（16）切点切点18五.GA的各种变形（17）凸组合交叉：可以克服上面简单交叉操作导致的解的不可行性。约束是个凸集，可行性可以保持，但是分散性太差，又出现了向中间汇集的问题。19变异位值变异：任选一位加Δ（变异步长），例：五.GA的各种变形（18）20向梯度方向变异缺点：只能用于目标函数可微的问题。例:对于最大化问题可采用如下操作：优点：考虑到了问题本身的性质，效率较高。但染色体种群也可能因此而趋于聚集，导致种群的多样性较差。五.GA的各种变形（19）215.3适

7、值函数的标定(Scaling)五.GA的各种变形（20）相对差别放大，选择压力变大，选优功能强化了标定相对差别小，选择压力小，选优功能弱化了22标定的目的：使适值函数不会太大，有一定差别选择压力的概念：选择压力是种群好、坏个体被选中的概率之差，差大称为选择压力大。注意：上述概念中的“差大小”是相对于适值函数而言的。五.GA的各种变形（21）23局部搜索、广域搜索与选择压力的关系局部搜索与广域搜索是GA中的一对矛盾，只注重局部搜索很可能陷入局优，只注重广域搜