1730384游戏中的人工智能技术.ppt

选择 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction) 浙江大学CADCG 国家重点实验室 选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则 给出目标函数f，则f(bi)称为个体bi的适应度 为选中bi为下一代个体的次数 浙江大学CADCG 国家重点实验室 选择 性质： 适应度较高的个体，繁殖下一代的数目较多。 适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。 选择产生对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。 浙江大学CADCG 国家重点实验室 交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P，在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉 浙江大学CADCG 国家重点实验室 交叉 例如有个体 S1=100101 S2=010111 选择它们的左边3位进行交叉操作，则有 S1=010101 S2=100111 一般而言，交叉概率P的取值为0.25-0.75 浙江大学CADCG 国家重点实验室 变异 根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2 例如有个体S＝101011，对其的第1、4位置的基因进行变异，则有S=001111 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。 浙江大学CADCG 国家重点实验室 组合 选择＋杂交＝进化 选择使得适者生存 杂交将不同个体中优良的基因保存下来，创造新的具有各方面优势的品种 选择＋变异＝在优化中加入随机扰动 遗传算法是采用随机方法进行最优解有哪些信誉好的足球投注网站，选择体现了向最优解迫近，变异体现了全局最优解的复盖 坏的变异将最终被选择出去 浙江大学CADCG 国家重点实验室 组合 选择＋杂交＋突变＝遗传算法的力量 浙江大学CADCG 国家重点实验室 遗传算法 P:= 以随机方式产生串的集合 如果最优个体的适应度还未达到给定的阀值，或者最优个体的适应度和群体适应度仍然在上升 令fi=Fitness(pi), i=1…n 令P’= SelectionNewPopulation(p,f) 随机两两组合P’中的个体 对每一对个体，以概率C进行杂交 对P’中的每一个个体，以概率M进行编译 令P=P’ 浙江大学CADCG 国家重点实验室 结束条件 最优个体的适应度达到给定的阀值 最优个体的适应度和群体适应度不再上升 达到预先设定的最大循环数（繁衍代数） 群体中的所有个体具有相同的属性 浙江大学CADCG 国家重点实验室 遗传算法参数 群体大小n 交叉概率Pc 变异概率Pm 繁衍代数 其他：取决与具体的操作和结束条件 浙江大学CADCG 国家重点实验室 编码方式 除二进制编码外，问题的各种参数可以用实数向量构成子串 选择：与串类似 变异：将按照高斯概率分布的随机变量g加到某个参数上 浙江大学CADCG 国家重点实验室 遗传规划 遗传算法的一个分支，由Koza提出，与遗传算法用串的形式表示所不同的是，遗传规划的表示是计算机程序 它是一种自动编程技术 终结符集合：变量、常数 函数集合：程序中的函数 用分析树的形式表示中间产生的程序 浙江大学CADCG 国家重点实验室 初始化 先确定终结符集合和函数集合 随机产生初始群体 每一个个体（分析树）按照下列方式产生： 令T=空的分析树 令C=随机的终结符或者函数 将C加入T中 如果C位于预先设定的树的最大深度，则从终结符集合中任意选择C的儿子结点，并添加到T中 否则，对C的儿子重复上述过程 杂交 从待杂交的两棵树中任意选择一个结点，并交换以该结点为根结点的两棵子树 浙江大学CADCG 国家重点实验室 变异 选择某一个结点，将函数替换成另一个函数，将终结符替换成另一个终结符 选择某一个结点，删除以其为根的整棵子树，再以随机方式生成一棵子树 浙江大学CADCG 国家重点实验室 遗传规划算法 令P=随机初始群体 循环直到满足某