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

9.3 遗传算法遗传算法( Algorithm,简称GA GA) 遗传算法(Genetic Algorithm,简称GA)是一种概率搜 索算法，它通过模拟自然界生物进化机制， 索算法 ， 它通过模拟自然界生物进化机制 ， 根据优胜劣 汰的生物进化原则， 汰的生物进化原则 ， 能够在较大的参数空间中较快地搜 索到问题的最优解。 索到问题的最优解 。 它尤其适用于处理传统搜索方法中 难以解决的复杂和非线性问题。 难以解决的复杂和非线性问题 。 不仅避免了局部优化算 法的缺陷， 而且可以利用固有知识缩小搜索空间， 法的缺陷 ， 而且可以利用固有知识缩小搜索空间 ， 避免 其它全局优化算法产生搜索的组合爆炸。 其它全局优化算法产生搜索的组合爆炸 。 遗传算法以其 简单通用、 鲁棒性强、适用于并行处理等特点， 简单通用 、 鲁棒性强 、 适用于并行处理等特点 ， 广泛应 用于组合优化、机器学习、规划设计、人工生命等领域。 用于组合优化 、 机器学习 、 规划设计 、 人工生命等领域 。

1.遗传算法的基本原理达尔文的“适者生存”理论、 达尔文的“适者生存”理论、继承的信息由基因携带 、多个 基因座、 基因组成了染色体 、基因座、等位基因 、基因型和表现型 染色体对应的是一系列符号序列，通常用0 染色体对应的是一系列符号序列，通常用0、1的位串表示 进行生物的遗传进化。在这一过程中包括三种演化操作： 进行生物的遗传进化。 在这一过程中包括三种演化操作： 在 父代基因群中的双亲选择操作、 父代基因群中的双亲选择操作、 两个父代双亲产生子代基因 的交叉操作和在子代基因群体中的变异操作。 的交叉操作和在子代基因群体中的变异操作。 两种数据转换：从表现型到基因型的转换，另一种是从基因 两种数据转换： 从表现型到基因型的转换， 型到表现型的转换 遗传算法实质上是一种繁衍、 遗传算法实质上是一种繁衍、检测和评价的迭代算法 最大优点是问题的最优解与初始条件无关， 最大优点是问题的最优解与初始条件无关， 而且搜索最优解 的能力极强

遗传算法可定义为一个8元组： 遗传算法可定义为一个 元组： 元组 GA = (C, E, P0, M, Φ, Γ, Ψ, T) 式中， C—个体的编码方法； 个体的编码方法； 式中， 个体的编码方法 E—个体适应值评价函数； 个体适应值评价函数； 个体适应值评价函数 P0—初始种群； 初始种群； 初始种群 M—群体大小； 群体大小； 群体大小 选择算子； Φ—选择算子； 选择算子 交叉算子； Γ—交叉算子； 交叉算子 变异算子； Ψ—变异算子； 变异算子 T—遗传算法终止条件。 遗传算法终止条件。 遗传算

法终止条件

初始化种群 编码为染色体 种群 P (t ) 计算各染色体的适应值 种群←种群 种群← 遗传操作(选择、交叉、变异) 遗传操作(选择、交叉、变异) 种群 P (t + 1) N 停机条件满足 ？ Y 结 束 图 遗传算法的工作原理示意图

遗传算法的关键技术包括： 遗传算法的关键技术包括： 编码问题； 编码问题； 初始种群的产生； 初始种群的产生； 确定适应值函数； 确定适应值函数； 选择遗传操作算子； 选择遗传操作算子； 停机条件。 停机条件。

编码问题 编码是应用遗传算法时要解决的首要问题，也是设 编码是应用遗传算法时要解决的首要问题， 计遗传算法时的一个关键步骤。 计遗传算法时的一个关键步骤。由于遗传算法不能 直接处理解空间的解数据， 直接处理解空间的解数据，因此必须通过编码将它 们表示成遗传空间的基因型串结构数据。 们表示成遗传空间的基因型串结构数据。编码方法 在很大程度上决定了如何进行群体的遗传进化运算 以及遗传进化的效率。由于不同的编码方法具有不 以及遗传进化的效率。 同的特点，为了提高遗传算法的效率， 同的特点，为了提高遗传算法的效率，应根据不同 的情况采用不同的编码方式。 的情况采用不同的编码方式。主要的编码方法有二 进制编码、浮点数编码、符号编码、多参数编码、 进制编码、浮点数编码、符号编码、多参数编码、 可变长染色体编码等。 可变长染色体编码等。

在遗传算法中一般用二值( , )向量表示染色体， 在遗传算法中一般用二值(0,1)向量表示染色体， 故先要对规则进行编码。编码采用二进制， 故先要对规则进行编码。编码采用二进制，将由特 征和类别组成的训练例子集编码成二进制字符串的 遗传样本。一个样本M 是一个二元组，其形式如下： 遗传样本。一个样本 i是一个二元组，其形式如下： Mi =[xi,yi],其中：i为样本号；x为条件部分，即训 为样本号； 为条件部分 为条件部分， ,其中： 为样本号 练例子的各特征编码； 为结论部分 为结论部分， 练例子的各特征编码；y为结论部分，即训练例子的 类别。 类别。

具体的编码规则如下： 具体的编码规则如下： 若属性为范畴型， 若属性为范畴型，定义属性段的宽度等于属性取值个 对于每个属性段，若第一位为‘ ’ 数。对于每个属性段，若第一位为‘*’,表示该属 性取值可以为任意；否则，各位若取值为1, 性取值可以为任意；否则，各位若取值为 ，表示取 该属性值， 表示不取该属性值 例如， 表示不取该属性值。 该属性值，0表示不取该属性值。例如，某条件属性 Ci对应的编码二进

制串为 对应的编码二进制串为011001,表示该属性取第二 ， 个属性值或第三个属性值或第六个属性值，即 个属性值或第三个属性值或第六个属性值， Ci ∈{Ci2, Ci3, Ci6} 若属性为数值型， 若属性为数值型，定义属性段的宽度 w = [log 2(n)] + 2, 其中n为该属性的取值个数 对于每个属性段， 为该属性的取值个数。 其中 为该属性的取值个数。对于每个属性段，若第 一位为‘ ’ 一位为‘*’,表示该属性取值可以为任意

初始种群的产生 GA以初始种群作为初始点开始迭代。初始种群 以初始种群作为初始点开始迭代。 作为初始点开始迭代 大小表示群体中所含个体的数量。 大小表示群体中所含个体的数量。当个体数量 取值较小时，可提高遗传算法的运算速度， 取值较小时，可提高遗传算法的运算速度，但 搜索空间分布范围有限，降低了群体的多样性， 搜索空间分布范围有限，降低了群体的多样性， 有可能会引起遗传算法的早熟现象； 有可能会引起遗传算法的早熟现象；当个体数 量取值较大时，一方面计算复杂，会使遗传算 量取值较大时，一方面计算复杂， 法的运行效率降低，另一方面， 法的运行效率降低，另一方面，部分高适应值 的个体可能被淘汰，影响交叉。 的个体可能被淘汰，影响交叉。初始种群的一 般取值范围是20~100 20~100。 般取值范围是20~100。

产生初始种群的方法通常有两种：(1)对问题 产生初始种群的方法通常有两种：(1 :( 的解无任何先验知识的情况， 的解无任何先验知识的情况，采用随机产生样 本的方法；( ;(2 对于具有某些先验知识的情况， 本的方法；(2)对于具有某些先验知识的情况， 可首先将这些先验知识转变为必须满足的一组 要求， 要求，然后在满足这些要求的解中随机地选取 样本。 样本。这样选择初始种群可使遗传算法更快地 达到最优解。 达到最优解。

确定适应值函数 遗传算法的设计要素之一是如何确定适应值 函数，在遗传算法中， 函数 ， 在遗传算法中 ， 利用适应值来衡量个 体的优劣， 体的优劣 ， 采用适者生存的原则决定哪些个 体进行繁殖，哪些个体被淘汰。 体进行繁殖，哪些个体被淘汰。

选择遗传操作算子遗传算子包括三个基本算子： 遗传算子包括三个基本算子：选择算子 Operator)、交叉算子(Crossover (Selection Operator)、交叉算子(Crosso …… 此处隐藏：4272字，全部文档内容请下载后查看。喜欢就下载吧 ……