ch9_现代数据挖掘技术--遗传算法

《ch9_现代数据挖掘技术--遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、遗传算法（GeneticAlgorithm，简称GA）是一种概率搜索算法，它通过模拟自然界生物进化机制，根据优胜劣汰的生物进化原则，能够在较大的参数空间中较快地搜索到问题的最优解。它尤其适用于处理传统搜索方法中难以解决的复杂和非线性问题。不仅避免了局部优化算法的缺陷，而且可以利用固有知识缩小搜索空间，避免其它全局优化算法产生搜索的组合爆炸。遗传算法以其简单通用、鲁棒性强、适用于并行处理等特点，广泛应用于组合优化、机器学习、规划设计、人工生命等领域。9.3遗传算法1.遗传算法的基本原理达尔文的“适者生存”理论、继承的信息由基因携带、多个基因组成了染色体、基因座

2、、等位基因、基因型和表现型染色体对应的是一系列符号序列，通常用0、1的位串表示进行生物的遗传进化。在这一过程中包括三种演化操作：在父代基因群中的双亲选择操作、两个父代双亲产生子代基因的交叉操作和在子代基因群体中的变异操作。两种数据转换：从表现型到基因型的转换，另一种是从基因型到表现型的转换遗传算法实质上是一种繁衍、检测和评价的迭代算法最大优点是问题的最优解与初始条件无关，而且搜索最优解的能力极强遗传算法可定义为一个8元组：GA=(C,E,P0,M,,,,T)式中，C—个体的编码方法；E—个体适应值评价函数；P0—初始种群；M—群体大小；—选择算子；

3、—交叉算子；—变异算子；T—遗传算法终止条件。初始化种群编码为染色体种群计算各染色体的适应值遗传操作(选择、交叉、变异)种群停机条件满足？种群←种群NY结束图遗传算法的工作原理示意图遗传算法的关键技术包括：编码问题；初始种群的产生；确定适应值函数；选择遗传操作算子；停机条件。编码问题编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化的效率。由于不同的编码方法具有不同的特点，为了

4、提高遗传算法的效率，应根据不同的情况采用不同的编码方式。主要的编码方法有二进制编码、浮点数编码、符号编码、多参数编码、可变长染色体编码等。在遗传算法中一般用二值（0，1）向量表示染色体，故先要对规则进行编码。编码采用二进制，将由特征和类别组成的训练例子集编码成二进制字符串的遗传样本。一个样本Mi是一个二元组，其形式如下：Mi=[xi，yi]，其中：i为样本号；x为条件部分，即训练例子的各特征编码；y为结论部分，即训练例子的类别。具体的编码规则如下：若属性为范畴型，定义属性段的宽度等于属性取值个数。对于每个属性段，若第一位为‘*’，表示该属性取值可以为任意；否

5、则，各位若取值为1，表示取该属性值，0表示不取该属性值。例如，某条件属性Ci对应的编码二进制串为011001，表示该属性取第二个属性值或第三个属性值或第六个属性值，即若属性为数值型，定义属性段的宽度，其中n为该属性的取值个数。对于每个属性段，若第一位为‘*’，表示该属性取值可以为任意初始种群的产生GA以初始种群作为初始点开始迭代。初始种群大小表示群体中所含个体的数量。当个体数量取值较小时，可提高遗传算法的运算速度，但搜索空间分布范围有限，降低了群体的多样性，有可能会引起遗传算法的早熟现象；当个体数量取值较大时，一方面计算复杂，会使遗传算法的运行效率降低，另一

6、方面，部分高适应值的个体可能被淘汰，影响交叉。初始种群的一般取值范围是20~100。产生初始种群的方法通常有两种：（1）对问题的解无任何先验知识的情况，采用随机产生样本的方法；（2）对于具有某些先验知识的情况，可首先将这些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中随机地选取样本。这样选择初始种群可使遗传算法更快地达到最优解。确定适应值函数遗传算法的设计要素之一是如何确定适应值函数，在遗传算法中，利用适应值来衡量个体的优劣，采用适者生存的原则决定哪些个体进行繁殖，哪些个体被淘汰。选择遗传操作算子选择算子又称复制(reproduction)算子、

7、繁殖算子。选择是从群体中选择生命力强的染色体产生新种群的过程。选择的依据是每个染色体的适应值大小，适应值越大，被选中的概率就越大。最常见的选择方法有比例选择法，即轮盘法。遗传算子包括三个基本算子：选择算子(SelectionOperator)、交叉算子(CrossoverOperator)、变异算子(MutationOperator)。交叉算子又称重组、配对算子。交叉分两步，首先按照一定的方法，随机地从交配池中取出要交配的一对染色体，然后进行交叉，产生一对新的位串。交叉的方法是，先根据位串长度L，随机产生一个交叉位置，即[1，L-1]上的一个整数，然后进行交

8、叉。例如：A1=1100

9、10，A2=1010

10、01