数据挖掘原理与SPSS Clementine应用宝典第13章 遗传算法.ppt

数据挖掘原理与数据挖掘原理与SPSS Clementine应用宝典应用宝典第第13章章 遗传算法遗传算法第十三章第十三章 遗传算法算法本章内容本章内容 1.遗传遗传算法算法算法算法概概概概述述述述 2.基本基本基本基本遗传遗传算法算法算法算法 3.改改改改进遗传进遗传算法算法算法算法 4.基于基于基于基于遗传遗传算法的算法的算法的算法的数数数数据据据据挖挖挖挖掘掘掘掘 5.基因表基因表基因表基因表达达达达式式式式编编程程程程遗传算法概述遗传算法概述-模式定理模式定理模式定理模式定理模式定理是遗传算法的理论基础，它的定义如下：l模式定理(Schema theorem)：在遗传算子选择，交叉和变异的作用下，具有低阶，短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以指数级增长。遗传算法概述遗传算法概述-积木块假设积木块假设积木块假设积木块假设具有低阶，短定义距及高适应度的模式称作积木块(Building block)。l积木块假设(building block hypothesis)是指低阶，短距，高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶，长距，高平均适应度模式，可最终生成全局最优解。遗传算法概述遗传算法概述-隐并行性隐并行性隐并行性隐并行性具有高阶，长定义距的模式在交叉算子和变异算子作用下遭到破坏，尽管遗传算法实际上只对几个串个体进行运算，但遗传算法仍然隐含处理了大量的模式，命名这一性质为隐并行性。遗传算法概述遗传算法概述-基本操作基本操作基本操作基本操作遗 传 操 作 包 含 三 个 基 本 遗 传 算 子(Genetic operator)：l选择选择(Selection)从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(Reproduction operator)。l交叉交叉(Crossover)所谓交叉又是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。l变异变异(Mutation)变异算子的基本内容是对群体中个体串的某些基因座上的基因值作变动。遗传算法概述遗传算法概述-编码方式编码方式编码方式编码方式编码方式是个体表示问题，即对于给定的问题，选择或设计一个适当的基因表示式，表13-1比较了目前已有的遗传算法(GA)的编码策略的具体分析。基本遗传算法基本遗传算法-流程流程流程流程基本遗传算法(SGA)只使用选择操作、交叉操作以及变异操作三种基本遗传操作，SGA的遗传操作过程简单，容易理解，且是其它复杂遗传算法的基础，它在给各种遗传算法提供基本框架的同时，也具有一定的应用价值。改进遗传算法改进遗传算法改进遗传算法主要研究内容包括：l分层遗传算法；l自适应遗传算法；l小生境遗传算法；l并行遗传算法；l混合遗传算法。分层遗传算法分层遗传算法-基本思想基本思想基本思想基本思想分层遗传算法分层遗传算法-关键问题关键问题关键问题关键问题l各个子种群的确定各个子种群的确定 各个子种群确定方式同SGA方式相同。l遗传操作设计遗传操作设计 初步遗传操作得到的结果就是遗传异算法初始层，而每一个都是可以是被下一层遗传操作处理对象。分层遗传算法分层遗传算法-流程流程流程流程自适应遗传算法自适应遗传算法小生境遗传算法小生境遗传算法小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过杂交、变异产生新一代个体群，同时采用预选择(preselection)机制或排挤(crowding)机制或分享(Sharing)机制完成选择操作。并行遗传算法并行遗传算法-实现方案实现方案实现方案实现方案l全局型-主从式模型(master-slave model)l独立型-粗粒度模型(coarse-grained model)l分散型-细粒度模型(fine-grained model)并行遗传算法并行遗传算法-迁移策略迁移策略迁移策略迁移策略l一传多一传多 每个处理器对应有若干个相邻处理器，每个处理器产生新一代个体后，都将自己最好的一个个体传送给其所有相邻处理器，并且接受来自相邻处理器的最好的个体，将这些个体与自己的个体同时考虑，淘汰适应度差的个体。l一传一一传一 考虑到染色体的多样性，每个处理器都将自己最好的个体仅传给与之相邻的一个处理器，同时增加两个参数:(1)处理器之间通讯的频率;(2)每次传送给最好个体的数目。混合遗传算法混合遗传算法-基本框架基本框架基本框架基本框架混合遗传算法(Hybrid Genetic Algorithm)，是提高遗传算法运行效率和求解质量的一个有效手段，可在保持算法一定通用性的基础上提高算法的效率，基本框架如下所示：基于遗传算法的数据挖掘基于遗传算法的数据挖掘l基于遗传算法的关联规则挖掘 l基于遗传算法的聚类算法 l基于遗传算法的分类算法 l基于模糊遗传算法的建模 基于遗传算法的基于遗传算法的关联规则关联规则挖掘挖掘基于遗传算法的关联规则挖掘的过程如下：基于遗传算法的基于遗传算法的聚类算法聚类算法基于遗传算法的聚类算法描述如下：基于模糊遗传算法的建模基于模糊遗传算法的建模 基于模糊的遗传算法描述如下：基于遗传算法的基于遗传算法的分类算法分类算法基于遗传算法的分类算法描述如下：基因表达式编程基因表达式编程-算法描述算法描述算法描述算法描述基因表达式编程的基本算法描述如下：基因表达式编程基因表达式编程-遗传操作遗传操作遗传操作遗传操作基因表达式编程的主要遗传操作有：l选择操作选择操作(Selectionl变异操作变异操作(Mutation)l插串操作插串操作(Transposition)GEP中插串操作分为三种：（1）IS插串（Insertion Sequence Transposition,）；（2）RIS插串（root Insertion Sequence Transposition）；（3）基因插串（Gene Transposition）。l重组操作重组操作(Recombination)在GEP中有3种重组方式：（1）一点重组；（2）两点重组；（3）基因重组；