[管理学]数据挖掘与技术 ch7 遗传算法.pptVIP

第七章 遗传算法 生物进化理论和遗传学的基本知识 生命的基本特征包括：生长、繁殖、新陈代谢和遗传与变异。 达尔文用自然选择(natural selection)来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面： 遗传 变异 生存斗争和适者生存 生物进化理论和遗传学的基本知识 遗传 生物的普遍特征，“种瓜得瓜，种豆得豆”，亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代具有相同或相似的形状。生物有了这个特征，物种才能稳定存在。 变异 亲代和子代之间以及子代的不同个体之间总有些差异，这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。 生物进化理论和遗传学的基本知识 生存斗争和适者生存 自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断进行，其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代生存环境的选择作用，物种变异被定向着一个方向积累，演变成新的物种。 生物进化理论和遗传学的基本知识 遗传算法效法基于自然选择的生物进化，是一种摹仿生物进化过程的的随机方法。 遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群由经过基因编码的一定数目的个体组成。 按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。 在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。 这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码可以作为问题近似最优解。 生物进化理论和遗传学的基本知识 一定数目N个个体随机地初始化，并计算每个个体的适应度函数，初始代产生。 按照适应度选择个体，父代要求基因重组（交叉）而产生子代。所有子代按一定概率变异。 子代的适应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代。直到满足优化准则为止。 遗传算法关键技术 确定适应值函数 遗传算法的设计要素之一是如何确定适应值函数，在遗传算法中，利用适应值来衡量个体的优劣，采用适者生存的原则决定哪些个体进行繁殖，哪些个体被淘汰。 遗传算法关键技术 选择遗传操作算子 遗传算子包括三个基本算子：选择算子(Selection Operator)、交叉算子(Crossover Operator)、变异算子(Mutation Operator)。 选择遗传操作算子 选择 用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。 选择的依据是计算适应度。 适应度计算之后是实际的选择，按照适应度进行父代个体的选择，可以挑选以下的算法： 轮盘赌选择 随机遍历抽样 局部选择等 遗传算法关键技术 轮盘赌选择 一组二进制基因码构成的个体组成的初始种群，个体的适用度评价值经计算由括号内的数值表示，适应度越大代表个体越好 遗传算法关键技术 轮盘赌选择 轮盘赌选择方法类似于博彩游戏中的轮盘赌。个体适应度转化为选中概率，将轮盘分成10个扇区，因为要进行10次选择，所以产生10个[0，1]之间的随机数，相当于转动10次轮盘，获得10次转盘停止时指针位置，指针停止在某一扇区，该扇区代表的个体即被选中。 遗传算法关键技术 轮盘赌选择 遗传算法关键技术 轮盘赌选择 0.070221、0.545929、0.784567?1、8、 9 遗传算法关键技术 轮盘赌选择 遗传算法关键技术 交叉或基因重组 杂交率就是用来确定 2个染色体进行局部的位（bit）的互换以产生2个新的子代的概率。 实验表明这一数值通常取为0.7左右是理想的，尽管某些问题领域可能需要更高一些或较低一些的值。 遗传算法关键技术 交叉或基因重组 每一次，从群体中选择 2个染色体，同时生成其值在0到1之间一个随机数，然后根据此数据的值来确定两个染色体是否要进行杂交。 如果数值低于杂交率(0.7)就进行杂交，然后沿着染色体的长度随机选择一个位置，并把此位置后面所有的位进行互换。 遗传算法关键技术 交叉或基因重组 例如，设给定的 2个染色体为: 10001001110010010 01010001001000011 沿着它们的长度随机选择一个位置，比如说 10，然后互换第10位之后所有位。这样两个染色体就变成了（我已在开始互换的位置加了一个空格）： 100010011 010100010 遗传算法关键技术 变异 变异率（突变率）就是在一个染色体中将位实行翻转（flip，即0 变1，1变 0）的几率。这对于二进制编码的基因