遗传算法课件

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

2、新产品投入，时间优化，伙伴挑选 例：3212345 对顺序编码来说是不合法的，而 对整数编码来说是合法的；010200不合法的01 编码；,五.GA的各种变形（2）,4,学习交流PPT,5.2 遗传运算中的问题 在顺序编码遗传运算的过程中会遇见不合法 的编码，应战的策略有二:拒绝或修复。 例如：经双切点交叉后，后代编码不合法 21 345 67 21 125 67 43 125 76 43 345 76 我们采用下面的修复策略使以上的编码合法。,五.GA的各种变形（3）,5,学习交流PPT,顺序编码的合法性修复： 交叉修复策略，分为以下几种： 部分映射交叉 顺序交叉 循环交叉,五.GA的各种变

3、形（4）,6,学习交流PPT,部分映射交叉(PMX) ( Partially Mapped Crossover)：用特别的修复程序解决简单的双切点交叉引起的非法性，步骤： 选切点X,Y； 交换中间部分； 确定映射关系； 将未换部分按映射关系恢复合法性。,五.GA的各种变形（5）,7,学习交流PPT,PMX例题：,五.GA的各种变形（6）,8,学习交流PPT,顺序交叉( OX )Order Crossover：可看做是带有不同修复程序的部分映射交叉的变形。 OX步骤： 选切点X,Y； 交换中间部分； 从切点Y后第一个基因起列出原顺序，去掉已有基因； 从切点Y后第一个位置起，按顺序填入。,五.GA

4、的各种变形（7）,9,学习交流PPT,OX例题：,五.GA的各种变形（8）,10,学习交流PPT,OX的特点： 较好的保留了相邻关系、先后关系,满足了TSP 问题的需要,但不保留位值特征。,五.GA的各种变形（9）,11,学习交流PPT,循环交叉(CX) Cycle Crossover 基本思想：子串位置上的值必须与父母的相同 位置上的位值相等。 CX步骤： 选 的第一个元素作为 的第一位， 选 的第一个元素作为 的第一位；,五.GA的各种变形（10）,12,学习交流PPT, 到 中找 的第一个元素赋给 的相对位置，重复此过程，直到 上得到 的第一个元素为止，称为一个循环； 对最前的基因按 、

5、 基因轮替原则重复以上过程； 重复以上过程，直到所有位都完成。,五.GA的各种变形（11）,13,学习交流PPT,CX 例题：,五.GA的各种变形（12）,14,学习交流PPT,CX的特点： 与OX的特点不同的是， CX较好的保留了位值 特征，适合指派问题；而OX较好的保留了相邻 关系、先后关系满足了TSP问题的需要。,五.GA的各种变形（13）,15,学习交流PPT,变异的修复策略 换位变异(最常用)是随机地在染色体上选取两个位置，交换基因的位值。 例： 4 3 1 2 5 6 7 4 5 1 2 3 6 7 移位变异：任选一位移到最前 例： 4 3 1 2 5 6 7 5 4 3 1 2

6、6 7,五.GA的各种变形（14）,16,学习交流PPT,实数编码的合法性修复 交叉 单切点交叉,五.GA的各种变形（15）,切点,17,学习交流PPT,双切点交叉(与单切点交叉类似) 该方法最大的问题：如何在实际优化中保持可行性。,五.GA的各种变形（16）,18,学习交流PPT,五.GA的各种变形（17）,凸组合交叉：可以克服上面简单交叉操作导致的解的不可行性。 约束是个凸集，可行性可以保持，但是分散 性太差，又出现了向中间汇集的问题。,19,学习交流PPT,变异 位值变异： 任选一位加（变异步长）， 例：,五.GA的各种变形（18）,20,学习交流PPT,向梯度方向变异 缺点：只能用于目

7、标函数可微的问题。 例:对于最大化问题可采用如下操作： 优点：考虑到了问题本身的性质，效率较高。但染色体种群也可能因此而趋于聚集，导致种群的多样性较差。,五.GA的各种变形（19）,21,学习交流PPT,5.3 适值函数的标定(Scaling),五.GA的各种变形（20）,22,学习交流PPT,标定的目的： 使适值函数不会太大，有一定差别 选择压力的概念： 选择压力是种群好、坏个体被选中的概率 之差，差大称为选择压力大。 注意：上述概念中的“差大小”是相对于适值函数而言的。,五.GA的各种变形（21）,23,学习交流PPT,局部搜索、广域搜索与选择压力的关系 局部搜索与广域搜索是GA中的一对矛

8、盾，只注重局部搜索很可能陷入局优，只注重广域搜索则会导致精确开发能力不强。因此，好的算法要将以上二者综合考虑。一般来说，算法开始时应注重广域搜索，通过使用较小的选择压力来实现；随着迭代的进行，逐步偏重于局部搜索，通过使用较大的选择压力来实现。,五.GA的各种变形（22）,24,学习交流PPT,适值的标定方法 线性标定： 函数表达式： , 为目标函数， 为适值函数,五.GA的各种变形（23）,25,学习交流PPT,对 ， =1， = + ， 函数表达式 ：+， 对 ， =-1， = + , 函数表达式： +， 上述中的是一个较小的数，目的是使种群中最差的个体仍然有繁殖的机会，增加种群的多样性。,

9、五.GA的各种变形（24）,26,学习交流PPT,动态线性标定(最常用)：线性标定中的参数随着迭代次数的增加而变化时就得到了动态线性标定 优点：计算容易不占用时间 函数表达式： ， 为迭代指标 最常用最大化 =1 , 函数表达式：,五.GA的各种变形（25）,第k代的最小目标函数值,27,学习交流PPT,加入的意义（同线性标定中 的意义） 加入使最坏个体仍有繁殖的可能， 随 的增大而减小 的取值： ， ， ， 调节 和 ，从而来调节,五.GA的各种变形（26）,28,学习交流PPT,五.GA的各种变形（27）,引入 的目的： 调节选择压力，即好坏个体选择概率的 差，使广域搜索范围宽保持种群的多

10、样性，而 局域搜索细保持收敛性。如下图表示： 开始：希望选择压力小 后来：希望选择压力大,29,学习交流PPT,幂律标定： 函数表达式： 的取值， 1时选择压力加大 1时选择压力减小 对数标定： 函数表达式： 对数标定的作用：缩小目标函数值的差别,五.GA的各种变形（28）,30,学习交流PPT,指数标定： 函数表达式： 指数标定的作用：扩大差别 窗口技术： 函数表达式： 为前W代中的最小目标值，它考虑了各代的波动，这样 具有记忆性,五.GA的各种变形（29）,31,学习交流PPT,正规化技术： 函数表达式： 正规化技术的作用： 将 映射到(0,1)区间，抑制超级染色体 正规化技术的实质：特殊

11、的动态标定 即 其中：,五.GA的各种变形（30）,32,学习交流PPT,5.4 选择策略 传统的GA选择和遗传是一起进行的，即使 后代不如父代，却无法纠正。下面介绍的选择 策略都是先遗传后选择。这样，样本空间扩大 了，可供选择的个体增多了。,五.GA的各种变形（31）,33,学习交流PPT,截断选择： 选择最好的前T个个体，让每一个有1/T的选择概率，平均得到NP/T个繁殖机会。 例：NP=100,T=50 即100名学生，成绩前50名的选出。每人的选择概率为150，有平均2个机会。 缺点：这种方法将花费较多的时间在适应值的 排序上。,五.GA的各种变形（32）,34,学习交流PPT,顺序选

12、择： 步骤： 从好到坏排序所有个体 定义最好个体的选择概率为 ,则第 个个体的选择概率为：,五.GA的各种变形（33）,35,学习交流PPT,由于 有限时要归一化，则有下面的公式： ，其中 顺序选择的优点：选择概率可以离线计算，节省算法执行时间，且选择压力可控； 缺点：把选择概率固定化了，选择压力不可调节。,五.GA的各种变形（34）,36,学习交流PPT,举例: 且： 采用旋轮法，随机产生 当 ，选择个体,五.GA的各种变形（35）,前i-1个个体的选择概率,前i个个体的选择概率,37,学习交流PPT,正比选择：个体i的选择概率 令： ， 用动态标定来调节选择压力，采用旋轮法来共 同完成种群

13、的选择。,五.GA的各种变形（36）,38,学习交流PPT,5.5 停止准则 指定最大代数（常用）：该方法简单但不准确。 检查种群中适值的一致性：保持历史上最好的个体。计算公式： 或 第二种方法因很难实现，所以很少使用。,五.GA的各种变形（37）,39,学习交流PPT,背包问题 个物品，对物品 ，价值为 ，重量为 ， 背包容量是 。如何选取物品装入背包，使背 包中的价值最大。,六.应用（1）,40,学习交流PPT,模型: （二进制编码方法） ，装入物品 ，不装入物品,六.应用（2）,41,学习交流PPT,例如，对于一个7个项目的背包问题，背包容量W=100，具体数据见下表，考察如下编码X=（

14、1 1 0 0 1 1 0） 这表示项目1、2、5和6被装入了背包，经过计算可知产生的解不可行。 背包问题示例,42,学习交流PPT,如何处理约束来保持可行性 拒绝策略： 可行解不易达到时，很难达到一个初始种群 修复策略： 将不可行解修复为可行的，但将失去多样性。,六.应用（3）,43,学习交流PPT,惩罚策略： 要求设计适当的惩罚函数，但设计不好会掩盖目标函数的优化。 下面，我们将分别采用惩罚策略和解码法来处理上面的背包问题。,六.应用（4）,44,学习交流PPT,罚函数法 令适值函数 ，其中 是目标函数 令 ，其中 注： 与 是 的两个端点,六.应用（5）,45,学习交流PPT,函数式的意

15、义： 的作用是使，保证 可行也惩罚，只有当 时不惩罚。 罚函数法的目的：把解拉向边界，尽量装满。,六.应用（6）,46,学习交流PPT,解码法First Fit Heuristic(优先适合启 发式)解码法是一段修复程序(修复可行性的方法) 步骤： 将选上物品按 降序排列； 选前 个物品，使； 解码法的关键：如何在GA中解决可行性问题 编码方法：采用顺序编码,六.应用（7）,47,学习交流PPT,例： =7 用顺序( 3 2 5 1 4 6 7 )表示选择物品的顺序 用优先适合启发式保留前K位，使解可行 即： =3， ( 3 2 5 ) 问题：编码长度是可变的，如何做交叉和变异,六.应用（8）,30,50,10,40,100,48,学习交流PPT,变长顺序编码的遗传算法插入式交叉算法 在 上选一个随机的断点； 在 上随机选一个基因片断插入 的断点处； 去掉 上的重复基因； 按优先适合启发式得到可行解 见下页例题,六.应用（9）,49,学习交流PPT,例题：,六.应用（10）