知识发现数据挖掘第十二章

知识发现数据挖掘第十二章内容摘要：

变异：发生变异的概率很小 （ 7）新群体的产生： 保留上一代最优个体，一般为 10%左右，至少 1个 用新个体取代旧个体，随机取代或择优取代。 11000， 11011， 11001， 10011 （ 8）重复上述操作： 说明： GA的终止条件一般人为设置； GA只能求次优解或满意解。 分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解 ——择优取代有问题。 若随机的将个体 01101选入新群体中，有可能找到最优解。 mP遗传算法举例 2020/11/4 史忠植 高级人工智能 44 遗传算法的理论基础 模式的定义 遗传算法的理论基础是遗传算法的二进制表达式及模式的含义。 模式是能对染色体之间的相似性进行解释的模板。 [定义 1] 设 GA的个体 ,记集合 则称 为一个模式，其中＊是通配符。 即模式 (schema)是含有通配符 (*)的一类字符串的通式表达。 每个“ *” 可以取 “ 1” 或者 “ 0”。 lBp lS ,* }1,0{Ss2020/11/4 史忠植 高级人工智能 45 模式举例  模式 *10101110 与以下两个字符串匹配： 010101110 110101110  而模式 *1010＊ 110 与以下四个字符串匹配： 010100110 010101110 110100110 110101110 2020/11/4 史忠植 高级人工智能 46 模式的定义  [定义 2] 一个 模式 s的阶 是出现在模式中的“ 0”和“ 1”的数目，记为 o(s)。 如：模式“ 0****” 的阶为 1，模式 “ 10*1*” 的阶为 3。  [定义 3] 一个 模式 s的长度 是出现在模式中第一个确定位置和最后一个确定位置之间的距离，记为。 如：模式“ 01***” 的长度为 1，模式 “ 0***1” 的长度为 3。 )(s2020/11/4 史忠植 高级人工智能 47 模式定理  假定在给定的时间步 t,一个特定的模式 s在群体 P(t)中包含由 m个代表串，记为 m=m(s,t)。 首先，我们暂不考虑交叉和变异操作。 每个串根据适应值的大小获得不同的复制概率。 串 i的复制概率为：  njijfifp1)()( （ 1) 2020/11/4 史忠植 高级人工智能 48 模式定理  则在群体 P(t+1)中，模式 s的代表串的数量的期望值为：   njjfsfntsmtsmE1)()(),()1,(• 其中， 表示模式 s在 t时刻的所有代表串的适应值的均值，称为模式 s的适应值。 )(sf（ 2） 2020/11/4 史忠植 高级人工智能 49 模式定理  若记 P(t)中所有个体的适应值的平均值为： njffnj 1)(（ 3） • 则 (2)式可以表示为：  fsftsmtsmE )(),()1,( 2020/11/4 史忠植 高级人工智能 50 模式定理  (3)式表明，模式 s的代表串的数目随时间增长的幅度正比于模式 s的适应值与群体平均适应值的比值。 即：适应值高于群体平均值的模式在下一代的代表串数目将会增加，而适应值低于群体平均值的模式在下一代的代表串数目将会减少。  假设模式的适应值为 ,其中 c是一个常数，则 (3)式可写为： fc)1( 2020/11/4 史忠植 高级人工智能 51 模式定理 （ 4） • 上式表明，在平均适应值之上（之下）的模式，将会按指数增长（衰减）的方式被复制。  1)1()0,()1(),()1(),()1,(tcsmctsmffctsmtsmE2020/11/4 史忠植 高级人工智能 52 模式定理 • 复制的结果并没有生成新的模式。 因而，为了探索搜索空间中的未搜索部分，需要利用交叉和变异操作。 • 下面先探索交叉对模式的影响。 模式 s1=“*1****0”和 s2=“***10**” 交叉会改变模式的一部分，模式的长度越长，被破坏的概率越大。 2020/11/4 史忠植 高级人工智能 53 模式定理 • 假定模式 s在交叉后不被破坏的概率为 ps，则： • 若交叉概率为 pc,则 s不被破坏的概率为 1)(1 lsps1)(1 lsppcs2020/11/4 史忠植 高级人工智能 54 模式定理 （ 5） • 所以，再考虑交叉时， (3)式可表示为 • 最后，考虑变异算子对模式的影响。 变异算子以概率 pm随机地改变个体某一位的值。 只有当 o(s)个确定位的值不被破坏时，模式 s才不被破坏。   1)(1)(),()1,(lspfsftsmtsmEc2020/11/4 史忠植 高级人工智能 55 模式定理 • 模式 s在变异后不被破坏的概率： • Pm1,可近似地表示为   )(1 soms pp )(1 sopp ms 2020/11/4 史忠植 高级人工智能 56 模式定理 （ 6） • 因此，考虑交叉和变异时， (3)式可表示为  mcmcmcpsolspfsftsmpsolsppsolspfsftsmtsmE)(1)(1)(),()(1)()(1)(1)(),()1,(2020/11/4 史忠植 高级人工智能 57 模式定理  由 (6)我们得到一个重要的定理。  [定理 1] 模式定理 (Schema Theorem) 适应值在群体适应值之上的、长度较短的、低阶的模式在 GA的迭代中将按指数增长方式被复制。 2020/11/4 史忠植 高级人工智能 58 积木块假设  Holland和 Goldberg在模式定理的基础上提出了“积木块假设” (Building Block Hypothesis):  低阶、长度较短、高于平均适应度的模式 (积木块 )在遗传算子的作用下，相互结合，能生成高阶、长度较长、适应度较高的模式，并得到全局最优解。 2020/11/4 史忠植 高级人工智能 59 遗传算法的收敛性分析  算法的收敛性可以定义如下： 定义： 若算法在 t时刻的种群 xt满足 则称算法收敛到 x0。  关于遗传算法的收敛性， Michalewicz证明了基于压缩原理的收敛性定理。 而 Rudolph证明了基于 Markov链的收敛性定理。 Xxxx tt  00l i m2020/11/4 史忠植 高级人工智能 60 遗传算法的改进 遗传算法的局限性： 遗传算法得到了广泛应用，但也暴露了一些问题，如：遗传算法在解决某些问题时速度较慢；遗传算法对编码方案的依赖性较强，算法的鲁棒性不够好等。 这些问题主要归结为： （ 1）上位 (epistasis)效应 上位效应包括两个方面：多基因性和基因多效性。 2020/11/4 史忠植 高级人工智能 61 遗传算法的改进 （ 2）编码方案 最初使用最多的是二进制位串，但此类编码并不适合一些实际问题。 现在人们已经探索了许多其它方案，如浮点表示、树形表示等等。 （ 3）积木块假设 积木块假设是否成立，是否一定存在短的、低阶的、高适应值的积木块。 若构成问题最优解的所有低阶模式的适应值都较低，这是 GA很难收敛到最优解，此类问题称为“欺骗问题”。 2020/11/4 史忠植 高级人工智能 62 遗传算法的改进 （ 4）早熟收敛 即 GA收敛到一个局部最优解。 Schraudolph和 Belew提出“动态参数编码”方案来解决早熟收敛问题。 关于遗传算法的一些改进措施，有兴趣的同学可查找相关资料。 2020/11/4 史忠植 高级人工智能 63 遗传机器学习－分类器系统  机器学习是人工智能的一个重要研究领域，也是人工智能的一个重要的应用领域。  遗传机器学习 (Geics Based Machine Learning, GBML)时将遗传算法与机器学习系统相结合的产物。 2020/11/4 史忠植 高级人工智能 64 遗传机器学习系统的一般框架 任务子系统 学习子系统 任务检测器 … 1dmd… 1eme任务效应器 执行效应器 执行检测器 2020/11/4 史忠植 高级人工智能 65 匹兹堡方法和密西根方法  遗传机器学习有两种重要的实现方法：  一种是由匹兹堡 (Pittsburgh)大学的 De Jong和他的学生 Smith提出的。 该方法用整个规则集合表示一个个体， GAs维护一个包含一定数目的候选规则集的种群。 这种方法称为匹兹堡方法。 2020/11/4 史忠植 高级人工智能 66 匹兹堡方法和密西根方法  另一种方法是由密西根。