数据挖掘与技术 ch 遗传算法.pptx

《数据挖掘与技术 ch 遗传算法.pptx》由会员分享，可在线阅读，更多相关《数据挖掘与技术 ch 遗传算法.pptx（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生命的基本特征包括：生长、繁殖、新陈代谢和遗传与变异。达尔文用自然选择(natural selection)来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面：遗传变异生存斗争和适者生存第1页/共38页生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识遗传生物的普遍特征，“种瓜得瓜，种豆得豆”，亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代具有相同或相似的形状。生物有了这个特征，物种才能稳定存在。变异亲代和子代之间以及子代的不同个体之间总有些差异，这种现象称为变异。变异是随机发生的，变异的

2、选择和积累是生命多样性的根源。第2页/共38页生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生存斗争和适者生存自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断进行，其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代生存环境的选择作用，物种变异被定向着一个方向积累，演变成新的物种。第3页/共38页生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识遗传算法效法基于自然选择的生物进化，是一种摹仿生物进化过程的的随机方法。遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群由经过基因编码的一定数目的个体组成。按照适者生存和

3、优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码可以作为问题近似最优解。第4页/共38页生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识一定数目N个个体随机地初始化，并计算每个个体的适应度函数，初始代产生。按照适应度选择个体，父代要求基因重组（交叉）而产生子代。所有子代按一定概率变异。子代的适应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代。直到满足优化

4、准则为止。第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页/共38页初始化种群初始化种群编码为染色体编码为染色体种群种群计算各染色体的适应值计算各染色体的适应值遗传操作遗传操作(选择、交叉、变异选择、交叉、变异)种群种群

5、停机条件满足停机条件满足？种群种群种群种群N NY Y结结 束束图图 遗传算法的工作原理示意图遗传算法的工作原理示意图遗传算法基本原理遗传算法基本原理 第7页/共38页遗传算法的关键技术包括：遗传算法的关键技术包括：编码问题；编码问题；初始种群的产生；初始种群的产生；确定适应值函数；确定适应值函数；选择遗传操作算子；选择遗传操作算子；停机条件。停机条件。遗传算法基本原理遗传算法基本原理 第8页/共38页编码问题编码问题由于遗传算法不能直接处理解空间的解数据，因由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型此必须通过编码将它们表示成遗传空间的基因型串结构数据

6、。串结构数据。编码方法在很大程度上决定了如何进行群体的遗编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化的效率。由于不同的编传进化运算以及遗传进化的效率。由于不同的编码方法具有不同的特点，为了提高遗传算法的效码方法具有不同的特点，为了提高遗传算法的效率，应根据不同的情况采用不同的编码方式。率，应根据不同的情况采用不同的编码方式。主要的编码方法有二进制编码、浮点数编码、符主要的编码方法有二进制编码、浮点数编码、符号编码、多参数编码、可变长染色体编码等。号编码、多参数编码、可变长染色体编码等。遗传算法关键技术遗传算法关键技术 第9页/共38页编码问题编码问题在遗传算法中一般用二值（

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

8、技术 第10页/共38页具体的编码规则如下：具体的编码规则如下：若属性为范畴型，定义属性段的宽度等于属性取值个数。对若属性为范畴型，定义属性段的宽度等于属性取值个数。对于每个属性段，若第一位为于每个属性段，若第一位为*，表示该属性取值可以为，表示该属性取值可以为任意；否则，各位若取值为任意；否则，各位若取值为1 1，表示取该属性值，表示取该属性值，0 0表示不取表示不取该属性值。例如，某条件属性该属性值。例如，某条件属性C Ci i对应的编码二进制串为对应的编码二进制串为011001011001，表示该属性取第二个属性值或第三个属性值或第六，表示该属性取第二个属性值或第三个属性值或第六个属性值

9、，即个属性值，即若属性为数值型，定义属性段的宽度若属性为数值型，定义属性段的宽度 ，其，其中中n n为该属性的取值个数。对于每个属性段，若第一位为为该属性的取值个数。对于每个属性段，若第一位为*，表示该属性取值可以为任意，表示该属性取值可以为任意遗传算法关键技术遗传算法关键技术 第11页/共38页初始种群的产生初始种群的产生GAGA以初始种群作为初始点开始迭代。初始种群大以初始种群作为初始点开始迭代。初始种群大小表示群体中所含个体的数量。当个体数量取值小表示群体中所含个体的数量。当个体数量取值较小时，可提高遗传算法的运算速度，但较小时，可提高遗传算法的运算速度，但搜索空搜索空间分布范围有限，间

10、分布范围有限，降低了群体的多样性，有可能降低了群体的多样性，有可能会引起遗传算法的早熟现象；当个体数量取值较会引起遗传算法的早熟现象；当个体数量取值较大时，一方面计算复杂，会使遗传算法的运行效大时，一方面计算复杂，会使遗传算法的运行效率降低，另一方面，部分高适应值的个体可能被率降低，另一方面，部分高适应值的个体可能被淘汰，影响交叉。初始种群的一般取值范围是淘汰，影响交叉。初始种群的一般取值范围是2010020100。遗传算法关键技术遗传算法关键技术 第12页/共38页产生初始种群的方法通常有两种：产生初始种群的方法通常有两种：（1 1）对问题的解无任何先验知识的情况，采用随机产生）对问题的解无

11、任何先验知识的情况，采用随机产生样本的方法；样本的方法；（2 2）对于具有某些先验知识的情况，可首先将这些先验）对于具有某些先验知识的情况，可首先将这些先验知识转变为必须满足的一组要求，然后在满足这些要知识转变为必须满足的一组要求，然后在满足这些要求的解中随机地选取样本。这样选择初始种群可使遗求的解中随机地选取样本。这样选择初始种群可使遗传算法更快地达到最优解。传算法更快地达到最优解。遗传算法关键技术遗传算法关键技术 第13页/共38页遗传算法关键技术遗传算法关键技术确定适应值函数遗遗传传算算法法的的设设计计要要素素之之一一是是如如何何确确定定适适应应值值函函数数，在在遗遗传传算算法法中中，利

12、利用用适适应应值值来来衡衡量量个个体体的的优优劣劣，采采用适者生存的原则决定哪些个体进行繁殖，哪些个体被淘汰。用适者生存的原则决定哪些个体进行繁殖，哪些个体被淘汰。第14页/共38页遗传算法关键技术遗传算法关键技术选择遗传操作算子选择遗传操作算子 遗传算子包括三个基本算子：选择算子遗传算子包括三个基本算子：选择算子(Selection Operator)(Selection Operator)、交叉算子、交叉算子(Crossover Operator)(Crossover Operator)、变异算、变异算子子(Mutation Operator)(Mutation Operator)。第15

13、页/共38页选择遗传操作算子选择遗传操作算子选择选择用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。选择的依据是计算适应度。选择的依据是计算适应度。适应度计算之后是实际的选择，按照适应度进行父代个体的选择，可以挑选以下的算法：适应度计算之后是实际的选择，按照适应度进行父代个体的选择，可以挑选以下的算法：轮盘赌选择轮盘赌选择随机遍历抽样随机遍历抽样局部选择等局部选择等第16页/共38页遗传算法关键技术遗传算法关键技术轮盘赌选择轮盘赌选择 一组二进制基因码构成的个体组成的初始种一组二进制基因码构成的个体组成的初始种群，个体的适用度

14、评价值经计算由括号内的数值表群，个体的适用度评价值经计算由括号内的数值表示，适应度越大代表个体越好示，适应度越大代表个体越好00011000000101111001000000010110011101001010101010 （8）（5）（2）（10）（7）11100101101001011011110000000110011101000001010011（12）（5）（19）（10）（14）第17页/共38页遗传算法关键技术遗传算法关键技术轮盘赌选择轮盘赌选择方法类似于博彩游戏中的轮盘赌。个体适应度转化为选中概率，将轮盘分成10个扇区，因为要进行10次选择，所以产生10个0，1之间的随机数，

15、相当于转动10次轮盘，获得10次转盘停止时指针位置，指针停止在某一扇区，该扇区代表的个体即被选中。第18页/共38页遗传算法关键技术遗传算法关键技术轮盘赌选择个体个体染色体染色体适应度适应度选择概率选择概率累计概率累计概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.05434

16、80.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.000000第19页/共38页遗传算法关键技术遗传算法关键技术轮盘赌选择0.070221、0.545929、0.7845671、8、971234568910个体选择概率累计概率10.0869570.08695720.0543481014130430.0217390.16304340.1086960.27173950.0760870.34782660.1304350.47826170.0543480.53260980

17、.2065220.73913090.1086960.847826100.1521741.000000第20页/共38页遗传算法关键技术遗传算法关键技术轮盘赌选择71234568910 显然，适应度高的个体被选中的概率越大，而且可能被选中；而适应度低的个体则很有可能被淘汰。第21页/共38页遗传算法关键技术遗传算法关键技术交叉或基因重组交叉或基因重组杂交率就是用来确定杂交率就是用来确定 2 2个染色体进行局部的位（个染色体进行局部的位（bitbit）的互换以产生）的互换以产生2 2个新的个新的子代的概率。子代的概率。实验表明这一数值通常取为实验表明这一数值通常取为0.70.7左右是理想的，尽管某

18、些问题左右是理想的，尽管某些问题领域可能需要更高一些或较低一些的值。领域可能需要更高一些或较低一些的值。第22页/共38页遗传算法关键技术遗传算法关键技术交叉或基因重组交叉或基因重组每一次，从群体中选择每一次，从群体中选择 2个染色体，同时生成其值在个染色体，同时生成其值在0到到1之间一个随机数，之间一个随机数，然后根据此数据的值来确定两个染色体是否要进行杂交。然后根据此数据的值来确定两个染色体是否要进行杂交。如果数值低于杂交率如果数值低于杂交率(0.7)就进行杂交，然后沿着染色体的长度随机选择一就进行杂交，然后沿着染色体的长度随机选择一个位置，并把此位置后面所有的位进行互换。个位置，并把此位

19、置后面所有的位进行互换。第23页/共38页遗传算法关键技术遗传算法关键技术交叉或基因重组交叉或基因重组例如，设给定的例如，设给定的 2 2个染色体为个染色体为:沿着它们的长度随机选择一个位置，比如说沿着它们的长度随机选择一个位置，比如说 1010，然后互换第，然后互换第1010位之后位之后所有位。这样两个染色体就变成了（我已在开始互换的位置加了一个空格）：所有位。这样两个染色体就变成了（我已在开始互换的位置加了一个空格）：100010011 100010011 01000011 01000011 010100010 010100010 1001001010010010 第24页/共38页遗传算

20、法关键技术遗传算法关键技术变异变异 变异率（突变率）就是在一个染色体中将位实行翻转（变异率（突变率）就是在一个染色体中将位实行翻转（flipflip，即，即0 0 变变1 1，1 1变变 0 0）的几率。这对于二进制编码的基因来说通常都是很低的值，比如）的几率。这对于二进制编码的基因来说通常都是很低的值，比如 0.001 0.001。因此，无论从群体中怎样选择染色体，首先是检查是否要杂交，然后再从头因此，无论从群体中怎样选择染色体，首先是检查是否要杂交，然后再从头到尾检查子代染色体的各个位，并按所规定的几率对其中的某些位实行突变到尾检查子代染色体的各个位，并按所规定的几率对其中的某些位实行突变

21、（翻转）。（翻转）。第25页/共38页遗传算法关键技术遗传算法关键技术停机条件停机条件遗传算法是一种反复迭代的搜索算法，它通过多次进化逐渐逼近最优解，因遗传算法是一种反复迭代的搜索算法，它通过多次进化逐渐逼近最优解，因此需要确定停机条件。此需要确定停机条件。最常用的停机条件是规定遗传的代数，即迭代次数。最常用的停机条件是规定遗传的代数，即迭代次数。第26页/共38页遗传算法关键技术遗传算法关键技术停机条件当遗传算法是用来产生新的规则时，停机条件不能简单地用遗传代数确定。一次学习过程的结束是当当遗传算法是用来产生新的规则时，停机条件不能简单地用遗传代数确定。一次学习过程的结束是当目前工作规则已收

22、敛，停机条件应该定义为：子代种群的规则与其父代完全相同，并且各规则的适应目前工作规则已收敛，停机条件应该定义为：子代种群的规则与其父代完全相同，并且各规则的适应值已连续值已连续MM次保持不变。也就是说，当前工作种群已不再进化了。其中，次保持不变。也就是说，当前工作种群已不再进化了。其中，MM是根据不同的应用情况事先是根据不同的应用情况事先设置的一个参数。设置的一个参数。第27页/共38页遗传算法的步骤遗传算法的步骤代数计数器初始化：代数计数器初始化：t0t0；产生初始种群；产生初始种群；评价群体评价群体P(t)P(t)的适应值；的适应值；根据当前群体的每个个体的适应值进行选择生成中间群体根据当

23、前群体的每个个体的适应值进行选择生成中间群体P1(t)P1(t)；个体交叉个体交叉(重组重组)操作：操作：P2(t)crossoverP1(t)P2(t)crossoverP1(t)；个体变异操作：个体变异操作：P3(t)mutationP2(t)P3(t)mutationP2(t)；评价群体评价群体P3(t)P3(t)的适应值；的适应值；终止条件判断，若不满足终止条件，则：终止条件判断，若不满足终止条件，则：tt+1tt+1，转向第转向第3 3步，继续进行遗传操作过程；步，继续进行遗传操作过程；若满足终止条件，则：输出当前最优个体，算法结束。若满足终止条件，则：输出当前最优个体，算法结束。第

24、28页/共38页遗传算法的实例遗传算法的实例 问题：求解问题：求解 在在0 0，31 31 上的最大值。上的最大值。1 1）编码：用）编码：用5 5位二进制表示位二进制表示x x，有，有 x=0 x=0 即即00000 x=31 00000 x=31 即即11111111112 2）初始种群）初始种群 随机产生随机产生4 4个个体：个个体：1313，2424，8 8，1919（分别用（分别用二进制表示）。二进制表示）。3 3）适应值）适应值f f 直接用目标函数作为适应值：直接用目标函数作为适应值：a.a.非负；非负；b.b.逐步增大。逐步增大。第29页/共38页4 4）选择率和期望值）选择率

25、和期望值选择率：选择率：平均适应值：平均适应值：期望值：期望值：5 5）实选值）实选值 期望值取整数。如下表：期望值取整数。如下表：遗传算法的实例遗传算法的实例第30页/共38页表1：初始种群参数计算编号编号初始种群位串初始种群位串参数值参数值x值值目标适应值目标适应值选择率选择率期望值期望值实选值实选值1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总和总和平均值平均值最大值最大值11702935761.000.250.494.001.001.974.01.02.0第31页/共38页表

26、2：初始种群的遗传过程选择后的交配池选择后的交配池交叉对象交叉对象交叉位置交叉位置新的种群新的种群x值值f(x)=x201101110001100010011214344220110011001110111000012252716144625729256总和总和平均值平均值最大值最大值1754439729第32页/共38页表3：新种群参数计算编号编号初始种群位串初始种群位串参数值参数值x值值目标适应值目标适应值选择率选择率期望值期望值实选值实选值123401100110011101110000122527161446257292560.080.360.420.150.331.421.660.5

27、80121总和总和平均值平均值最大值最大值17544397291.000.250.424.001.001.664.01.02.0第33页/共38页表4：新种群的遗传过程选择后的交配池选择后的交配池交叉对象交叉对象交叉位置交叉位置新的种群新的种群x值值f(x)=x211011110011101110000214311331101111001110001001127 252419729 625576361总和总和平均值平均值最大值最大值2291572729第34页/共38页遗传算法在适应度函数选择不当的情况下有可能收敛于局遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优

28、。部最优，而不能达到全局最优。对于动态数据，用遗传算法求最优解比较困难，因为染色对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再产体种群很可能过早地收敛，而对以后变化了的数据不再产生变化。生变化。为防止过早的收敛，研究者提出了一些方法增加基因的多为防止过早的收敛，研究者提出了一些方法增加基因的多样性。其中一种是所谓样性。其中一种是所谓触发式超级突变触发式超级突变，就是当染色体群，就是当染色体群体的质量下降（彼此的区别减少）时增加变异概率；另一体的质量下降（彼此的区别减少）时增加变异概率；另一种叫种叫随机外来染色体随机外来染色体，是偶尔加入一些全

29、新的随机生成的，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。染色体个体，从而增加染色体多样性。遗传算法的优缺点遗传算法的优缺点第35页/共38页选择过程很重要，但交叉和变异的重要性存在争议。一种选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解；而另一种观点则认为交叉过程的作用只不某些可能的解；而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变

30、异率，而这么大群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。的变异很可能影响进化过程。遗传算法很快就能找到良好的解，即使是在很复杂的解空遗传算法很快就能找到良好的解，即使是在很复杂的解空间中。间中。遗传算法并不一定总是最好的优化策略，优化问题要具体遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试情况具体分析。所以在使用遗传算法的同时，也可以尝试其他算法，互相补充，甚至根本不用遗传算法。其他算法，互相补充，甚至根本不用遗传算法。遗传算法的优缺点遗传算法的优缺点第36页/共38页遗传算法不能解决那些遗传算法不能解决那

31、些“大海捞针大海捞针”的问题，所谓的问题，所谓“大海大海捞针捞针”问题就是没有一个确切的适应度函数表征个体好坏问题就是没有一个确切的适应度函数表征个体好坏的问题，遗传算法对这类问题无法找到收敛的路。的问题，遗传算法对这类问题无法找到收敛的路。对于任何一个具体的优化问题，调节遗传算法的参数可能对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交会有利于更好的更快的收敛，这些参数包括个体数目、交叉律和变异律。例如太大的变异律会导致丢失最优解，而叉律和变异律。例如太大的变异律会导致丢失最优解，而过小的变异律会导致算法过早的收敛于局部最优点。对于过小的变异律会导致算法过早的收敛于局部最优点。对于这些参数的选择，现在还没有实用的上下限。这些参数的选择，现在还没有实用的上下限。适应度函数对于算法的速度和效果也很重要。适应度函数对于算法的速度和效果也很重要。遗传算法的优缺点遗传算法的优缺点第37页/共38页感谢您的观看！第38页/共38页