数据挖掘与技术ch7遗传算法.ppt

第七章 遗传算法,生物进化理论和遗传学的基本知识,生命的基本特征包括：生长、繁殖、新陈代谢和遗传与变异。达尔文用自然选择(natural selection)来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面：遗传变异生存斗争和适者生存,生物进化理论和遗传学的基本知识,遗传生物的普遍特征，“种瓜得瓜，种豆得豆”，亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代具有相同或相似的形状。生物有了这个特征，物种才能稳定存在。变异亲代和子代之间以及子代的不同个体之间总有些差异，这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。,生物进化理论和遗传学的基本知识,生存斗争和适者生存自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断进行，其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代生存环境的选择作用，物种变异被定向着一个方向积累，演变成新的物种。,生物进化理论和遗传学的基本知识,遗传算法效法基于自然选择的生物进化，是一种摹仿生物进化过程的的随机方法。遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群由经过基因编码的一定数目的个体组成。按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码可以作为问题近似最优解。,生物进化理论和遗传学的基本知识,一定数目N个个体随机地初始化，并计算每个个体的适应度函数，初始代产生。按照适应度选择个体，父代要求基因重组（交叉）而产生子代。所有子代按一定概率变异。子代的适应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代。直到满足优化准则为止。,遗传算法可定义为一个8元组：GA=(C,E,P0,M,T)式中，C个体的编码方法；E个体适应值评价函数；P0初始种群；M群体大小；选择算子；交叉算子；变异算子；T遗传算法终止条件。,遗传算法基本原理,遗传算法基本原理,遗传算法的关键技术包括：编码问题；初始种群的产生；确定适应值函数；选择遗传操作算子；停机条件。,遗传算法基本原理,编码问题由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化的效率。由于不同的编码方法具有不同的特点，为了提高遗传算法的效率，应根据不同的情况采用不同的编码方式。主要的编码方法有二进制编码、浮点数编码、符号编码、多参数编码、可变长染色体编码等。,遗传算法关键技术,编码问题在遗传算法中一般用二值（0，1）向量表示染色体，故先要对规则进行编码。编码采用二进制，将由特征和类别组成的训练例子集编码成二进制字符串的遗传样本。一个样本Mi是一个二元组，其形式如下：Mi=xi，yi，其中：i为样本号；x为条件部分，即训练例子的各特征编码；y为结论部分，即训练例子的类别。,遗传算法关键技术,具体的编码规则如下：若属性为范畴型，定义属性段的宽度等于属性取值个数。对于每个属性段，若第一位为*，表示该属性取值可以为任意；否则，各位若取值为1，表示取该属性值，0表示不取该属性值。例如，某条件属性Ci对应的编码二进制串为011001，表示该属性取第二个属性值或第三个属性值或第六个属性值，即若属性为数值型，定义属性段的宽度，其中n为该属性的取值个数。对于每个属性段，若第一位为*，表示该属性取值可以为任意,遗传算法关键技术,初始种群的产生GA以初始种群作为初始点开始迭代。初始种群大小表示群体中所含个体的数量。当个体数量取值较小时，可提高遗传算法的运算速度，但搜索空间分布范围有限，降低了群体的多样性，有可能会引起遗传算法的早熟现象；当个体数量取值较大时，一方面计算复杂，会使遗传算法的运行效率降低，另一方面，部分高适应值的个体可能被淘汰，影响交叉。初始种群的一般取值范围是20100。,遗传算法关键技术,产生初始种群的方法通常有两种：（1）对问题的解无任何先验知识的情况，采用随机产生样本的方法；（2）对于具有某些先验知识的情况，可首先将这些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中随机地选取样本。这样选择初始种群可使遗传算法更快地达到最优解。,遗传算法关键技术,遗传算法关键技术,确定适应值函数遗传算法的设计要素之一是如何确定适应值函数，在遗传算法中，利用适应值来衡量个体的优劣，采用适者生存的原则决定哪些个体进行繁殖，哪些个体被淘汰。,遗传算法关键技术,选择遗传操作算子 遗传算子包括三个基本算子：选择算子(Selection Operator)、交叉算子(Crossover Operator)、变异算子(Mutation Operator)。,选择遗传操作算子,选择用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。选择的依据是计算适应度。适应度计算之后是实际的选择，按照适应度进行父代个体的选择，可以挑选以下的算法：轮盘赌选择随机遍历抽样局部选择等,遗传算法关键技术,轮盘赌选择 一组二进制基因码构成的个体组成的初始种群，个体的适用度评价值经计算由括号内的数值表示，适应度越大代表个体越好,遗传算法关键技术,轮盘赌选择轮盘赌选择方法类似于博彩游戏中的轮盘赌。个体适应度转化为选中概率，将轮盘分成10个扇区，因为要进行10次选择，所以产生10个0，1之间的随机数，相当于转动10次轮盘，获得10次转盘停止时指针位置，指针停止在某一扇区，该扇区代表的个体即被选中。,遗传算法关键技术,轮盘赌选择,遗传算法关键技术,轮盘赌选择0.070221、0.545929、0.7845671、8、9,7,遗传算法关键技术,轮盘赌选择,7,显然，适应度高的个体被选中的概率越大，而且可能被选中；而适应度低的个体则很有可能被淘汰。,遗传算法关键技术,交叉或基因重组杂交率就是用来确定 2个染色体进行局部的位（bit）的互换以产生2个新的子代的概率。实验表明这一数值通常取为0.7左右是理想的，尽管某些问题领域可能需要更高一些或较低一些的值。,遗传算法关键技术,交叉或基因重组每一次，从群体中选择 2个染色体，同时生成其值在0到1之间一个随机数，然后根据此数据的值来确定两个染色体是否要进行杂交。如果数值低于杂交率(0.7)就进行杂交，然后沿着染色体的长度随机选择一个位置，并把此位置后面所有的位进行互换。,遗传算法关键技术,交叉或基因重组例如，设给定的 2个染色体为:沿着它们的长度随机选择一个位置，比如说 10，然后互换第10位之后所有位。这样两个染色体就变成了（我已在开始互换的位置加了一个空格）：100010011 01000011 010100010 10010010,遗传算法关键技术,变异 变异率（突变率）就是在一个染色体中将位实行翻转（flip，即0 变1，1变 0）的几率。这对于二进制编码的基因来说通常都是很低的值，比如 0.001。因此，无论从群体中怎样选择染色体，首先是检查是否要杂交，然后再从头到尾检查子代染色体的各个位，并按所规定的几率对其中的某些位实行突变（翻转）。,遗传算法关键技术,停机条件遗传算法是一种反复迭代的搜索算法，它通过多次进化逐渐逼近最优解，因此需要确定停机条件。最常用的停机条件是规定遗传的代数，即迭代次数。,遗传算法关键技术,停机条件当遗传算法是用来产生新的规则时，停机条件不能简单地用遗传代数确定。一次学习过程的结束是当目前工作规则已收敛，停机条件应该定义为：子代种群的规则与其父代完全相同，并且各规则的适应值已连续M次保持不变。也就是说，当前工作种群已不再进化了。其中，M是根据不同的应用情况事先设置的一个参数。,遗传算法的步骤,代数计数器初始化：t0；产生初始种群；评价群体P(t)的适应值；根据当前群体的每个个体的适应值进行选择生成中间群体P1(t)；个体交叉(重组)操作：P2(t)crossoverP1(t)；个体变异操作：P3(t)mutationP2(t)；评价群体P3(t)的适应值；终止条件判断，若不满足终止条件，则：tt+1，转向第3步，继续进行遗传操作过程；若满足终止条件，则：输出当前最优个体，算法结束。,遗传算法的实例,问题：求解 在0，31 上的最大值。1）编码：用5位二进制表示x，有 x=0 即00000 x=31 即111112）初始种群 随机产生4个个体：13，24，8，19（分别用二进制表示）。3）适应值f 直接用目标函数作为适应值：a.非负；b.逐步增大。,4）选择率和期望值选择率：平均适应值：期望值：5）实选值 期望值取整数。如下表：,遗传算法的实例,表1：初始种群参数计算,表2：初始种群的遗传过程,表3：新种群参数计算,表4：新种群的遗传过程,遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再产生变化。为防止过早的收敛，研究者提出了一些方法增加基因的多样性。其中一种是所谓触发式超级突变，就是当染色体群体的质量下降（彼此的区别减少）时增加变异概率；另一种叫随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。,遗传算法的优缺点,选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解；而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。遗传算法很快就能找到良好的解，即使是在很复杂的解空间中。遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其他算法，互相补充，甚至根本不用遗传算法。,遗传算法的优缺点,遗传算法不能解决那些“大海捞针”的问题，所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题，遗传算法对这类问题无法找到收敛的路。对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交叉律和变异律。例如太大的变异律会导致丢失最优解，而过小的变异律会导致算法过早的收敛于局部最优点。对于这些参数的选择，现在还没有实用的上下限。适应度函数对于算法的速度和效果也很重要。,遗传算法的优缺点,