,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选PPT课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,精选PPT课件,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,精选PPT课件,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,精选PPT课件,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,精选PPT课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,精选PPT课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,精选PPT课件,*,人工智能,-,机器学习,遗传算法的评估,1,精选PPT课件,人工智能-机器学习1精选PPT课件,遗传算法（,Genetic Algorithms,）是一种模拟生物界自然选择和遗传的启发式随机搜索算法。,其基本步骤包括编码、初始群体的生成、适应度评估、选择、交叉操作和变异操作。,GA,是一种具有“生成,+,检测”的迭代过程的搜索算法。,一、遗传算法的简介,2,精选PPT课件,遗传算法（Genetic Algorithms）是一种模拟生,初始群体,评估每个个体,选择,交叉,结束,是否优解？,开始,解编码,评估函数,遗传操作,遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数为依据。,适应度函数评估是选择操作的依据。,一般需将目标函数以一定的方式映射成适应度函数。,新群体,变异,二、遗传算法的实现过程,3,精选PPT课件,初始群体评估每个个体选择交叉结束是否优解？开始解编码评估函数,三、,评估（,Evaluation,）,Evaluation,Evaluated,generation,generation,GA,基本上不用外部信息，仅用适应度函数来,评估每个个体。,评估时需要解码（,decoding,），即把基因型（,genotype,）解转换为表示型（,phenotype,）解，以便利用评估函数或适应函数。,4,精选PPT课件,三、评估（Evaluation）EvaluationEva,X(=39),解（个体）在问题空间和遗传空间的转换，即,phenotype,解和,genotype,解之间的转换,。,四、,Coding and decoding,5,精选PPT课件,X(=39)解（个体）在问题空间和遗传空间的转换，即phe,coding,假如用遗传算子来区别十进制数,6,、,7,、,8,、,9,。整数表示出一个自然且平局的有序空间。因为在十进制中，下一个数只下在前一数上加,1,，然而用二进制编码则有明显不同：,0110 0111 1100 1111,6 7 8 9,在,6,和,7,之间还有,8,和,9,之间只有一位发生变化，但在,7,和,8,之间四位全部不相同。,6,精选PPT课件,coding6精选PPT课件,coding,这种不统一表现问题，在葛莱编码（,gray coding,）有较好的表现。,Integer 0 1 2 3 4 5 6 7,binary 000 001 010 011 100 101 110 111,Gray 000 001 011 010 110 111 101 100,从上面可看到，相邻两个数之间只相差一位，用,Gray,代替标准的,binary,，这样可以使得相邻状态间的遗传算子的转换变得平滑。,7,精选PPT课件,coding7精选PPT课件,二值编码：,问题空间的相邻解在编码空间并不相邻不利于解的搜索,葛莱码：,问题空间的相邻解在编码空间相邻有利于解的搜索,coding,8,精选PPT课件,二值编码：葛莱码：coding8精选PPT课件,GA,算法分析,群体设定,编码设计后的任务是初始群体的设定，其关键问题是群体规模。其中,要考虑：,初始群体如何设定？多大规模？,进化过程中各代的群体规模如何维持？,初始群体的设定,GA,中初始群体中的个体是随机产生的，也可以根据先验知识设定初始群体,群体中个体的多样性,模式定理告诉我们，若群体规模为,M,，,GA,可操作的模式数为,M,并在此基础上不断形成和优化积木块，直到最优解。,显然，,M,越大，,GA,操作的模式越多，生成有意义的积木块的机会越高。换句话说，,群体规模越大，群体中个体的多样性越高，陷入局部解的危险就越小,9,精选PPT课件,GA算法分析群体设定 编码设计后的任务是初始群体,群体规模太大的弊病,计算效率,由于个体被选择的概率大多采用适应度比例选择法，当规模太大时，大多数个体会被淘汰，仅少量的高适应度个体生存下来，影响配对和交叉繁殖。,群体规模太小的弊病,会使,GA,的搜索空间有限，引起未成熟收敛,(premature convergence),结论：,规模设定是一个,tradeoff,问题,可以证明，在二进制编码的前提下，为满足隐并行性，群体的个数只要设定为 即可。这个数目很大，一般设定为几十,几百,进化过程中，群体规模未必保持在相同规模，但一般情况下都保持不变,GA,算法分析,群体设定,10,精选PPT课件,群体规模太大的弊病GA算法分析群体设定10精选PPT课件,五、搜索的并行性,爬山法：它保持多个候选解，删除没希望的，提高好的解决方法。上图，表明了多个候选解在搜索空间中朝最优点收敛。,11,精选PPT课件,五、搜索的并行性爬山法：它保持多个候选解，删除没希望的，提高,五、搜索的并行性,图中，水平轴代表在解空间中的可能点，垂直轴反应这些解的质量。曲线上的点是遗传算法中当前群体中的候选解成员。开始时，候选解分散在可能解空间中，经过,N,代进化后，它们趋向于聚集在质量较高的区域。,12,精选PPT课件,五、搜索的并行性图中，水平轴代表在解空间中的可能点，垂直轴反,六、隐含的并行性,一般地说，,GA,的计算能力主要来源于它的隐含并行性，即按照一些有效的原则，并行地把搜索尝试分配到搜索空间的许多领域的特性。,GA,的隐含并行性使,GA,使用相对少的串，就可以测试搜索空间里较大范围的区域。,GA,的这种隐含并行性，使其在复杂问题的优化求解等方面优于其它算法。,13,精选PPT课件,六、隐含的并行性一般地说，GA的计算能力主要来源于它的隐含并,GA,基本上不用外部信息，仅用适应度函数作为依据,GA,的适应度函数不受连续可微的约束，且定义域可为任意集合，唯一要求是,可计算出能加以比较的非负结果,。此特点使,GA,应用范围很广。,具有相同编码的解应有相同的适应度,需要译码后再进行适应度评估,七、,GA,算法评估,适应度函数设计,14,精选PPT课件,GA基本上不用外部信息，仅用适应度函数作为依据七、GA算法评,目标函数映射为适应度函数,许多应用中，目标函数可直接作为适应度函数，但是，有些情况下需,将目标函数作变换，以得到适应度函数。,最小化问题：,将费用函数等最小化函数,g(x),转化为适应度函数,其他情况,可以是一个合适的值，也可采用迄今为止进化过程中,g(x),的最大值或当前群体中,g(x),的最大值,最大化问题：,将利润函数等最大化函数,u(x),转化为适应度函数,其他情况,可以是合适的输入值，也可以是当前一代或前,K,代中,u(x),的最小值,15,精选PPT课件,目标函数映射为适应度函数其他情况 可以是一个,适应度函数标定,(scaling),在应用,GA,尤其用,GA,处理小规模群体时常常会出现一些,不利于优化的现象和结果：,进化初期的未成熟收敛现象：基于比例选择策略，一些异常个体竞争力太强而处于主宰地位,解决办法：降低异常个体的竞争力，即适应度,进化后期的随机漫游现象：群体的平均适应度已接近最佳个体的适应度，此时，个体间竞争力减弱,解决办法：提高个体间竞争力，即适应度,七、,GA,算法评估,适应度函数设计,16,精选PPT课件,适应度函数标定(scaling)七、GA算法评估适应度,线性标定：,设原适应度函数为,f,标定后为,f:f=af+b,其中，,a,b,设定要满足,：,和,为了控制原适应度最大的,个体可贡献子孙数。,通常取,为了保证在以后的选择处理中平均每个个体可贡献一个期待的子孙到下一代,七、,GA,算法评估,适应度函数设计,17,精选PPT课件,和为了控制原适应度最大的为了保证在以后的选择处理中平均每个个,A,正常线性定标,B,出,现负适应度地线性定标,一些坏个体适应度远小于群体平均适应,度和最大适应度，且,群体,平均适应度又,比较接近最大适应度时，为了拉开他,们，使低适应度经定标后变成负值,18,精选PPT课件,A 正常线性定标B 出现负适应度地线性定标一些坏,截断,(sigma truncation),消除负适应度：,是群体适应度的标准方差，每代要计算方差,1c3,幂定标,(power law scaling),较少使用，,K,与求解问题相关,七、,GA,算法评估,适应度函数设计,19,精选PPT课件,截断(sigma truncation)七、GA算法评,3.,适应度函数与,GA,迭代停止条件,当最优解的适应度值已知或准最优解的适应度下限可以确定时，可用作迭代停止条件,否则，若发现群体中个体的进化已趋于稳定，即发现一定比例的个体具有完全相同的适应度，则停止迭代,4.,适应度函数与问题的约束条件,GA,仅靠适应度来评估和引导搜索，不能明确表示约束条件。,对策：适应度函数考虑惩罚或代价,约束优化问题 非约束问题,此类问题还可在编码和遗传操作设计方面采取一定措施,七、,GA,算法评估,适应度函数设计,20,精选PPT课件,3.适应度函数与GA迭代停止条件七、GA算法评估适应度函,此课件下载可自行编辑修改，此课件供参考！,部分内容来源于网络，如有侵权请与我联系删除！感谢你的观看！,此课件下载可自行编辑修改，此课件供参考！,此课件下载可自行编辑修改，此课件供参考！,部分内容来源于网络，如有侵权请与我联系删除！感谢你的观看！,此课件下载可自行编辑修改，此课件供参考！,