遗传算法课件

第三章

遗传算法1精选可编辑ppt五.遗传算法的各种变形5.1其它编码方法5.2遗传运算中的问题5.3适值函数的标定(Scaling)5.4选择策略5.5停止准则六.应用

遗传算法2精选可编辑ppt5.1其它编码方法顺序编码：用1到N的自然数的不同顺序来编码，此种编码不允许重复，即且，又称自然数编码。该法适用范围很广：指派问题、旅行商问题和单机调度问题等等。合法性问题：是否符合采用的编码规则的问题五.GA的各种变形（1）3精选可编辑ppt实数编码：,R为实数集特征：方便运算简单，但反映不出基因的特征整数编码类似于顺序编码，但编码允许重复适用于：新产品投入，时间优化，伙伴挑选例：3212345对顺序编码来说是不合法的，而对整数编码来说是合法的；010200不合法的01编码；五.GA的各种变形（2）4精选可编辑ppt5.2遗传运算中的问题 在顺序编码遗传运算的过程中会遇见不合法的编码，应战的策略有二:拒绝或修复。例如：经双切点交叉后，后代编码不合法

21¦345¦6721¦125¦6743¦125¦7643¦345¦76我们采用下面的修复策略使以上的编码合法。五.GA的各种变形（3）5精选可编辑ppt顺序编码的合法性修复：交叉修复策略，分为以下几种：部分映射交叉顺序交叉循环交叉

五.GA的各种变形（4）

6精选可编辑ppt部分映射交叉(PMX)(PartiallyMappedCrossover)：用特别的修复程序解决简单的双切点交叉引起的非法性，步骤：⑴选切点X,Y；⑵交换中间部分；⑶确定映射关系；⑷将未换部分按映射关系恢复合法性。五.GA的各种变形（5）7精选可编辑pptPMX例题：五.GA的各种变形（6）映射关系：3-1，4-2，5-5则：43¦125¦6721¦345¦76

21¦345¦67¦125¦

43¦125¦76¦345¦

XY8精选可编辑ppt顺序交叉(OX

)OrderCrossover：可看做是带有不同修复程序的部分映射交叉的变形。OX步骤：⑴选切点X,Y；⑵交换中间部分；⑶从切点Y后第一个基因起列出原顺序，去掉已有基因；⑷从切点Y后第一个位置起，按顺序填入。五.GA的各种变形（7）9精选可编辑pptOX例题：五.GA的各种变形（8）列出基因：67213457643125则：34¦125¦6712¦345¦76

21¦345¦67¦125¦

43¦125¦76¦345¦

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

245389617236

398654271362

32，94，58，716

29346

34692

295384671

34865921714精选可编辑pptCX的特点：与OX的特点不同的是，CX较好的保留了位值特征，适合指派问题；而OX较好的保留了相邻关系、先后关系满足了TSP问题的需要。五.GA的各种变形（13）15精选可编辑ppt变异的修复策略换位变异(最常用)是随机地在染色体上选取两个位置，交换基因的位值。

例：

43125674512367

移位变异：任选一位移到最前

例：

43125675431267五.GA的各种变形（14）16精选可编辑ppt实数编码的合法性修复

交叉单切点交叉五.GA的各种变形（15）切点17精选可编辑ppt双切点交叉(与单切点交叉类似)

该方法最大的问题：如何在实际优化中保持可行性。五.GA的各种变形（16）切点切点18精选可编辑ppt五.GA的各种变形（17）凸组合交叉：可以克服上面简单交叉操作导致的解的不可行性。约束是个凸集，可行性可以保持，但是分散性太差，又出现了向中间汇集的问题。19精选可编辑ppt变异位值变异： 任选一位加Δ（变异步长），

例：五.GA的各种变形（18）20精选可编辑ppt向梯度方向变异缺点：只能用于目标函数可微的问题。 例:对于最大化问题可采用如下操作：优点：考虑到了问题本身的性质，效率较高。但染色体种群也可能因此而趋于聚集，导致种群的多样性较差。五.GA的各种变形（19）21精选可编辑ppt5.3适值函数的标定(Scaling)五.GA的各种变形（20）

相对差别放大，选择压力变大，选优功能强化了标定

相对差别小，选择压力小，选优功能弱化了22精选可编辑ppt标定的目的： 使适值函数不会太大，有一定差别选择压力的概念： 选择压力是种群好、坏个体被选中的概率之差，差大称为选择压力大。注意：上述概念中的“差大小”是相对于适值函数而言的。五.GA的各种变形（21）23精选可编辑ppt局部搜索、广域搜索与选择压力的关系局部搜索与广域搜索是GA中的一对矛盾，只注重局部搜索很可能陷入局优，只注重广域搜索则会导致精确开发能力不强。因此，好的算法要将以上二者综合考虑。一般来说，算法开始时应注重广域搜索，通过使用较小的选择压力来实现；随着迭代的进行，逐步偏重于局部搜索，通过使用较大的选择压力来实现。五.GA的各种变形（22）24精选可编辑ppt适值的标定方法线性标定：

函数表达式：

,

为目标函数，为适值函数五.GA的各种变形（23）25精选可编辑ppt对， =1，=

+ξ， 函数表达式： +ξ，对， =-1，=

+ξ, 函数表达式： +ξ，

上述中的ξ是一个较小的数，目的是使种群中最差的个体仍然有繁殖的机会，增加种群的多样性。五.GA的各种变形（24）26精选可编辑ppt动态线性标定(最常用)：线性标定中的参数随着迭代次数的增加而变化时就得到了动态线性标定 优点：计算容易不占用时间函数表达式：，为迭代指标最常用最大化

=1,函数表达式：五.GA的各种变形（25）第k代的最小目标函数值27精选可编辑ppt加入的意义（同线性标定中ξ的意义） 加入使最坏个体仍有繁殖的可能，随的增大而减小的取值： ，，， 调节和，从而来调节五.GA的各种变形（26）28精选可编辑ppt五.GA的各种变形（27）引入的目的： 调节选择压力，即好坏个体选择概率的差，使广域搜索范围宽保持种群的多样性，而局域搜索细保持收敛性。如下图表示： 开始：希望选择压力小 后来：希望选择压力大k29精选可编辑ppt幂律标定： 函数表达式： 的取值，>1时选择压力加大

<1时选择压力减小对数标定： 函数表达式： 对数标定的作用：缩小目标函数值的差别五.GA的各种变形（28）30精选可编辑ppt指数标定： 函数表达式： 指数标定的作用：扩大差别窗口技术： 函数表达式： 为前W代中的最小目标值，它考虑了各代 的波动，这样具有记忆性五.GA的各种变形（29）31精选可编辑ppt正规化技术： 函数表达式： 正规化技术的作用： 将映射到(0,1)区间，抑制超级染色体 正规化技术的实质：特殊的动态标定 即 其中：五.GA的各种变形（30）32精选可编辑ppt5.4选择策略 传统的GA选择和遗传是一起进行的，即使后代不如父代，却无法纠正。下面介绍的选择策略都是先遗传后选择。这样，样本空间扩大了，可供选择的个体增多了。五.GA的各种变形（31）33精选可编辑ppt截断选择： 选择最好的前T个个体，让每一个有1/T的选择概率，平均得到NP/T个繁殖机会。例：NP=100,T=50 即100名学生，成绩前50名的选出。每人的选择概率为1／50，有平均2个机会。缺点：这种方法将花费较多的时间在适应值的排序上。五.GA的各种变形（32）34精选可编辑ppt顺序选择：步骤：⑴从好到坏排序所有个体⑵定义最好个体的选择概率为,则第个个体的选择概率为：五.GA的各种变形（33）35精选可编辑ppt⑶ 由于 有限时要归一化，则有下面的公式：，其中顺序选择的优点：选择概率可以离线计算，节省算法执行时间，且选择压力可控；缺点：把选择概率固定化了，选择压力不可调节。五.GA的各种变形（34）36精选可编辑ppt举例:

且：采用旋轮法，随机产生当，选择个体五.GA的各种变形（35）前i-1个个体的选择概率前i个个体的选择概率37精选可编辑ppt正比选择：个体i的选择概率 令： ，用动态标定来调节选择压力，采用旋轮法来共同完成种群的选择。

五.GA的各种变形（36）38精选可编辑ppt5.5停止准则指定最大代数（常用）：该方法简单但不准确。检查种群中适值的一致性：保持历史上最好的个体。计算公式： 或第二种方法因很难实现，所以很少使用。五.GA的各种变形（37）39精选可编辑ppt背包问题 个物品，对物品，价值为，重量为，背包容量是。如何选取物品装入背包，使背包中的价值最大。

六.应用（1）40精选可编辑ppt模型:

（二进制编码方法）

，装入物品 ，不装入物品

六.应用（2）41精选可编辑ppt例如，对于一个7个项目的背包问题，背包容量W=100，具体数据见下表，考察如下编码X=（1100110）这表示项目1、2、5和6被装入了背包，经过计算可知产生的解不可行。背包问题示例i1234567wi40503010104030pi4060101032060Pi/wi11.20.3310.30.5242精选可编辑ppt如何处理约束来保持可行性拒绝策略：可行解不易达到时，很难达到一个初始种群修复策略：将不可行解修复为可行的，但将失去多样性。六.应用（3）43精选可编辑ppt惩罚策略：要求设计适当的惩罚函数，但设计不好会掩盖目标函数的优化。 下面，我们将分别采用惩罚策略和解码法来处理上面的背包问题。 六.应用（4）44精选可编辑ppt罚函数法令适值函数 ，其中是目标函数令 ，其中

注： 与 是 的两个端点六.应用（5）罚函数45精选可编辑ppt函数式的意义：⑴ 的作用是使 ，保证⑵可行也惩罚，只有当 时不惩罚。⑶罚函数法的目的：把解拉向边界，尽量装满。六.应用（6）46精选可编辑ppt解码法——FirstFitHeuristic(优先适合启发式)解码法是一段修复程序(修复可行性的方法)⑴步骤：将选上物品按降序排列；选前个物品，使 ；⑵解码法的关键：如何在GA中解决可行性问题⑶编码方法：采用顺序编码 六.应用（7）47精选可编辑ppt例