数据挖掘与技术 ch 遗传算法PPT学习教案

1、会计学1数据挖掘与技术数据挖掘与技术 ch 遗传算法遗传算法第1页/共38页第2页/共38页第3页/共38页第4页/共38页第5页/共38页遗传算法可定义为一个遗传算法可定义为一个8 8元组：元组：GA = (GA = (C C, , E E, , P P0 0, , MM, , , , , , , , T T) ) 式中，式中， C C个体的编码方法；个体的编码方法； E E个体适应值评价函数；个体适应值评价函数； P P0 0初始种群；初始种群； MM群体大小；群体大小； 选择算子；选择算子； 交叉算子；交叉算子； 变异算子；变异算子； T T遗传算法终止条件。遗传算法终止条件。 第6页/

2、共38页初始化种群初始化种群编码为染色体编码为染色体种群种群计算各染色体的适应值计算各染色体的适应值遗传操作遗传操作( (选择、交叉、变异选择、交叉、变异) )种群种群停机条件满足停机条件满足？种群种群种群种群N NY Y结结 束束图图 遗传算法的工作原理示意图遗传算法的工作原理示意图) 1( tP)(tP第7页/共38页遗传算法的关键技术包括：遗传算法的关键技术包括： 编码问题；编码问题； 初始种群的产生；初始种群的产生； 确定适应值函数；确定适应值函数； 选择遗传操作算子；选择遗传操作算子； 停机条件。停机条件。 第8页/共38页编码问题编码问题由于遗传算法不能直接处理解空间的解数据，由于

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

4、符号编码、多参数编码、可变长染色体编码等。第9页/共38页编码问题编码问题在遗传算法中一般用二值（在遗传算法中一般用二值（0 0，1 1）向量表示染）向量表示染色体，故先要对规则进行编码。色体，故先要对规则进行编码。编码采用二进制，将由特征和类别组成的训练编码采用二进制，将由特征和类别组成的训练例子集编码成二进制字符串的遗传样本。一个例子集编码成二进制字符串的遗传样本。一个样本样本MMi i是一个二元组，其形式如下：是一个二元组，其形式如下： MMi i = =x xi i，y yi i ，其中：，其中：i i为样本号；为样本号；x x为条件部分，即训为条件部分，即训练例子的各特征编码；练例子

5、的各特征编码；y y为结论部分，即训练为结论部分，即训练例子的类别。例子的类别。第10页/共38页具体的编码规则如下：具体的编码规则如下： 若属性为范畴型，定义属性段的宽度等于属性取值个数。若属性为范畴型，定义属性段的宽度等于属性取值个数。对于每个属性段，若第一位为对于每个属性段，若第一位为* *，表示该属性取值可以，表示该属性取值可以为任意；否则，各位若取值为为任意；否则，各位若取值为1 1，表示取该属性值，表示取该属性值，0 0表示表示不取该属性值。例如，某条件属性不取该属性值。例如，某条件属性C Ci i对应的编码二进制串对应的编码二进制串为为011001011001，表示该属性取第二个

6、属性值或第三个属性值或，表示该属性取第二个属性值或第三个属性值或第六个属性值，即第六个属性值，即 若属性为数值型，定义属性段的宽度若属性为数值型，定义属性段的宽度 ，其，其中中n n为该属性的取值个数。对于每个属性段，若第一位为为该属性的取值个数。对于每个属性段，若第一位为* *，表示该属性取值可以为任意，表示该属性取值可以为任意,632iiiiCCCC 2)(2lognw第11页/共38页 初始种群的产生初始种群的产生GAGA以初始种群作为初始点开始迭代。初始种群以初始种群作为初始点开始迭代。初始种群大小表示群体中所含个体的数量。当个体数量取大小表示群体中所含个体的数量。当个体数量取值较小时

7、，可提高遗传算法的运算速度，但值较小时，可提高遗传算法的运算速度，但搜索搜索空间分布范围有限，空间分布范围有限，降低了群体的多样性，有可降低了群体的多样性，有可能会引起遗传算法的早熟现象；当个体数量取值能会引起遗传算法的早熟现象；当个体数量取值较大时，一方面计算复杂，会使遗传算法的运行较大时，一方面计算复杂，会使遗传算法的运行效率降低，另一方面，部分高适应值的个体可能效率降低，另一方面，部分高适应值的个体可能被淘汰，影响交叉。初始种群的一般取值范围是被淘汰，影响交叉。初始种群的一般取值范围是2010020100。第12页/共38页产生初始种群的方法通常有两种：产生初始种群的方法通常有两种：（1

8、 1）对问题的解无任何先验知识的情况，采用随机产生）对问题的解无任何先验知识的情况，采用随机产生样本的方法；样本的方法；（2 2）对于具有某些先验知识的情况，可首先将这些先验）对于具有某些先验知识的情况，可首先将这些先验知识转变为必须满足的一组要求，然后在满足这些要知识转变为必须满足的一组要求，然后在满足这些要求的解中随机地选取样本。这样选择初始种群可使遗求的解中随机地选取样本。这样选择初始种群可使遗传算法更快地达到最优解。传算法更快地达到最优解。 第13页/共38页第14页/共38页第15页/共38页第16页/共38页0001100000010111100100000001011001110

9、1001010101010 （8） （5）（2）（10）（7）11100101101001011011110000000110011101000001010011（12）（5）（19）（10）（14）第17页/共38页第18页/共38页个体个体染色体染色体适应度适应度选择概率选择概率累计概率累计概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.347826611100101

10、10120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.000000第19页/共38页71234568910个体选择概率累计概率10.0869570.08695720.0543481014130430.0217390.16304340.1086960.27173950.0760870.34782660.1304350.47826170.0543480.53260980.2065220.7391

11、3090.1086960.847826100.1521741.000000第20页/共38页71234568910 显然，适应度高的个体被选中的概率越大，而且可能被选中；而适应度低的个体则很有可能被淘汰。第21页/共38页第22页/共38页第23页/共38页第24页/共38页第25页/共38页第26页/共38页第27页/共38页第28页/共38页x2)x(f第29页/共38页iiiiffPiinffffi第30页/共38页编号编号初始种群位串初始种群位串参数值参数值x值值目标适应值目标适应值选择率选择率期望值期望值实选值实选值1234011011100001000100111324819169

12、576643610.140.490.060.310.581.970.221.231201总和总和平均值平均值最大值最大值11702935761.000.250.494.001.001.974.01.02.0第31页/共38页选择后的交配池选择后的交配池交叉对象交叉对象交叉位置交叉位置新的种群新的种群x值值f(x)=x201101110001100010011214344220110011001110111000012252716144625729256总和总和平均值平均值最大值最大值1754439729第32页/共38页编号编号初始种群位串初始种群位串参数值参数值x值值目标适应值目标适应值选择率选择率期望值期望值实选值实选值123401100110011101110000122527161446257292560.080.360.420.150.331.421.660.580121总和总和平均值平均值最大值最大000.250.424.001.001.664