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