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

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

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

3、算法终止条件。,遗传算法的关键技术包括： 编码问题； 初始种群的产生； 确定适应值函数； 选择遗传操作算子； 停机条件。,编码问题,编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化的效率。由于不同的编码方法具有不同的特点，为了提高遗传算法的效率，应根据不同的情况采用不同的编码方式。主要的编码方法有二进制编码、浮点数编码、符号编码、多参数编码、可变长染色体编码等。,在遗传算法中一般用二值（0，1）向量表示染色体，故

4、先要对规则进行编码。编码采用二进制，将由特征和类别组成的训练例子集编码成二进制字符串的遗传样本。一个样本Mi是一个二元组，其形式如下： Mi =xi，yi，其中：i为样本号；x为条件部分，即训练例子的各特征编码；y为结论部分，即训练例子的类别。,具体的编码规则如下： 若属性为范畴型，定义属性段的宽度等于属性取值个数。对于每个属性段，若第一位为*，表示该属性取值可以为任意；否则，各位若取值为1，表示取该属性值，0表示不取该属性值。例如，某条件属性Ci对应的编码二进制串为011001，表示该属性取第二个属性值或第三个属性值或第六个属性值，即 若属性为数值型，定义属性段的宽度 ，其中n为该属性的取值

5、个数。对于每个属性段，若第一位为*，表示该属性取值可以为任意,初始种群的产生,GA以初始种群作为初始点开始迭代。初始种群大小表示群体中所含个体的数量。当个体数量取值较小时，可提高遗传算法的运算速度，但搜索空间分布范围有限，降低了群体的多样性，有可能会引起遗传算法的早熟现象；当个体数量取值较大时，一方面计算复杂，会使遗传算法的运行效率降低，另一方面，部分高适应值的个体可能被淘汰，影响交叉。初始种群的一般取值范围是20100。,产生初始种群的方法通常有两种：（1）对问题的解无任何先验知识的情况，采用随机产生样本的方法；（2）对于具有某些先验知识的情况，可首先将这些先验知识转变为必须满足的一组要求，

6、然后在满足这些要求的解中随机地选取样本。这样选择初始种群可使遗传算法更快地达到最优解。,确定适应值函数,遗传算法的设计要素之一是如何确定适应值函数，在遗传算法中，利用适应值来衡量个体的优劣，采用适者生存的原则决定哪些个体进行繁殖，哪些个体被淘汰。,选择遗传操作算子,选择算子又称复制(reproduction)算子、繁殖算子。选择是从群体中选择生命力强的染色体产生新种群的过程。选择的依据是每个染色体的适应值大小，适应值越大，被选中的概率就越大。最常见的选择方法有比例选择法，即轮盘法。,遗传算子包括三个基本算子：选择算子(Selection Operator)、交叉算子(Crossover Ope

7、rator)、变异算子(Mutation Operator)。,交叉算子又称重组、配对算子。交叉分两步，首先按照一定的方法，随机地从交配池中取出要交配的一对染色体，然后进行交叉，产生一对新的位串。交叉的方法是，先根据位串长度L，随机产生一个交叉位置，即1，L-1上的一个整数，然后进行交叉。例如：A1=1100|10，A2=1010|01，“|”表示交叉位置，则交叉后得： 遗传算法是有效性主要来自选择和交叉操作，尤其是交叉，在遗传算法中起着核心作用。,选择和交叉算子基本上完成了遗传算法的大部分搜索功能，而变异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率，随机改变字符串某个位置上的值

8、。在二进制编码中，就是将0变成1，将1变成0。变异与选择、交叉算子结合在一起，就能避免由选择和交叉算子引起的某些信息的永久性丢失，从而保证了遗传算法的有效性。变异发生的概率极低，一般取值在0.0010.01之间。 在变异操作中，变异率Pm对遗传算法的性能有较大的影响，为了提高遗传算法的性能，在算法是运行过程中，动态改变变异率Pm，即根据个体的适应值决定个体的变异率Pm。对于适应值高的个体，取较小的变异率；而对于适应值低的个体，取较大的变异率。,遗传算法是一种反复迭代的搜索算法，它通过多次进化逐渐逼近最优解，因此需要确定停机条件。 最常用的停机条件是规定遗传的代数，即迭代次数。 当遗传算法是用来

9、产生新的规则时，停机条件不能简单地用遗传代数确定。一次学习过程的结束是当目前工作规则已收敛，停机条件应该定义为：子代种群的规则与其父代完全相同，并且各规则的适应值已连续M次保持不变。也就是说，当前工作种群已不再进化了。其中，M是根据不同的应用情况事先设置的一个参数。,停机条件,2.遗传算法的步骤：,代数计数器初始化：t0； 产生初始种群； 评价群体P(t)的适应值； 根据当前群体的每个个体的适应值进行选择生成中间群体P1(t)； 个体交叉(重组)操作：P2(t) crossoverP1(t) ； 个体变异操作：P3(t) mutationP2(t) ； 评价群体P3(t)的适应值； 终止条件判

10、断，若不满足终止条件，则：tt+1， 转向第3步，继续进行遗传操作过程； 若满足终止条件，则：输出当前最优个体，算法结束。,问题：求解 在0，31 上的最大值。 1）编码：用5位二进制表示x，有 x=0 即00000 x=31 即11111 2）初始种群 随机产生4个个体：13，24，8，19（分别用二进制表示）。 3）适应值f 直接用目标函数作为适应值： a.非负； b.逐步增大。,3.遗传算法的实例,4）选择率和期望值 选择率： 平均适应值： 期望值： 5）实选值 期望值取整数。如下表：,表1：初始种群参数计算,表2：初始种群的遗传过程,表3：新种群参数计算,表4：新种群的遗传过程,遗传算

11、法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。 对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再产生变化。 为防止过早的收敛，研究者提出了一些方法增加基因的多样性。其中一种是所谓触发式超级突变，就是当染色体群体的质量下降（彼此的区别减少）时增加变异概率；另一种叫随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。,4.遗传算法的优缺点,选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解；而另一种观点则认为交叉过程的作用只不过是在种

12、群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。 遗传算法很快就能找到良好的解，即使是在很复杂的解空间中。 遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其他算法，互相补充，甚至根本不用遗传算法。,遗传算法的优缺点,遗传算法不能解决那些“大海捞针”的问题，所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题，遗传算法对这类问题无法找到收敛的路。 对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交叉律和变异律。例如太大的变异律会导致丢失最优解，而过小的变异律会导致算法过早的收敛于局部最优点。对于这些参数的选择，现在还没有实用的上下限。 适应度函数对于算法的速度和效果也很重要。,遗传算法的优缺点,遗传算法适用的问题,遗传算法擅长解决的问题是全局最优化问题，例如，解决时间表安排问题就是它的一个特长，很多安排时间表的软件都使用遗传算法，遗传算法还经常被用于解决实际工程问题。 遗传算法能够跳出局部最优而找到全局最优点。而且遗传算法允许使用非常复杂的适应度函数（或者叫做目标函数），并对变量