大学计算机怎样研究算法遗传算法研究示例课件

,战德臣 教授,51,/51,大学计算机-计算思维导论,2013-2014,Research Center on,I,ntelligent,C,omputing for,E,nterprises &,S,ervices,H,arbin,I,nstitute of,T,echnology,战德臣,哈尔滨工业大学 教授,.,博士生导师,教育部大学计算机课程教学指导委员会委员,大学计算机-计算思维导论2013-2014Research,第,9,讲 怎样研究算法：遗传算法示例,2013-2014,Research Center on,I,ntelligent,C,omputing for,E,nterprises &,S,ervices,H,arbin,I,nstitute of,T,echnology,战德臣,哈尔滨工业大学 教授,.,博士生导师,教育部大学计算机课程教学指导委员会委员,第9讲 怎样研究算法：遗传算法示例2013-2014Rese,第,9,讲 怎样研究算法：遗传算法示例,什么是可求解与难求解问题,?,难解性问题的基本求解思路是什么,?,如何类比自然界生物求解问题的思想，设计计算类问题的求解算法,?,难解性问题,算法,计算,第9讲 怎样研究算法：遗传算法示例什么是可求解与难求解问题?,怎样研究算法：遗传算法示例,1.,可求解与难求解问题,可求解与难求解问题,-,计算复杂性,-P,类问题、,NP,类问题和,NPC,类问题,-NPC,类问题的求解思路,怎样研究算法：遗传算法示例可求解与难求解问题,现实世界中的问题分类,1.,可求解与难求解问题,1.1,什么是可求解与难求解问题,?,计算机在有限时间内能够求解的,(,可求解问题,),计算机在有限时间内不能求解的,(,难求解问题,),计算机完全不能求解的,(,不可计算问题,),计算复杂性是指问题的一种特性，即利用计算机求解问题的难易性或难易程度，其衡量标准：,计算所需的步数或指令条数,(,即时间复杂度,),计算所需的存储空间大小,(,即空间复杂度,),-,通常表达为关于问题规模,n,的一个函数,O(f(n),问题的计算复杂性,现实世界中的问题分类1.可求解与难求解问题计算机在有限时间内,1.,可求解与难求解问题,1.2,什么是有限时间内不能求解,?,问题规模,n,计算量,10,10,！,20,20,！,100,100,！,1000,1000,！,10000,10000,！,20,！,= 1.21610,17,20,3,=,8000,O(n,3,),O(3,n,),0.2,秒,4,10,28,秒,=1015,年,注：每秒百万次，,n=60,，,1015,年相当于,10,亿台计算机计算一百万年,O(n,3,),与,O(3,n,),的差别，,O(n!),与,O(n,3,),的差别,O(b,n,), O(n!),O(1), O(log n), O(n), O(n log n), O(n,b,),1.可求解与难求解问题问题规模n计算量1010！2020！1,1.,可求解与难求解问题,1.3,怎样以复杂性来划分问题,?,P,类问题，,NP,类问题，,NPC,类问题,P,类问题,： 多项式问题,(Polynomial Problem),，指计算机可以在有限时间内求解的问题，即：,P,类问题是可以找出一个呈现,O(n,a,),复杂性算法的问题，其中,a,为常数。,NP,类问题,：非确定性多项式问题,(Non-deterministic Polynomial),。有些问题，其答案是无法直接计算得到的，只能通过间接的猜算或试算来得到结果，这就是非确定性问题,(Non-deterministic),。虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题，即：在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题，就是,NP,类问题。,NPC,问题,：完全非确定性多项式问题,(NP-Complete),。如果,NP,问题的所有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非确定性多项式问题，即,NP-Complete,问题。,问：加密算法应该设计成一个什么问题呢？,1.可求解与难求解问题P类问题，NP类问题，NPC类问题P类,1.,可求解与难求解问题,1.4 NPC,类问题如何求解,?,NPC,类问题求解,穷举法,或称,遍历法,：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果,-,精确解,可能是,O(n!),或,O(a,n,),近似解求解算法,-,近似解,应该是,O(n,a,), = |,近似解,精确解,|,满意解：,充分小时的近似解,TSP,问题的遍历算法,TSP,问题的贪心算法,仿生学算法,进化算法，遗传算法，蚁群算法，蜂群算法, ,1.可求解与难求解问题NPC类问题求解穷举法或称遍历法：对解,怎样研究算法：遗传算法示例,2.,遗传算法的缘起,-,生物学中的遗传与进化,遗传算法的缘起,-生物学中的遗传与进化,怎样研究算法：遗传算法示例遗传算法的缘起,2.,遗传算法的缘起,-,生物学中的遗传与进化,2.1,生物体中是怎样遗传的,?,生物学中的遗传和进化,关于生物遗传进化的基本观点,(i),生物的所有,遗传信息,都包含在其,染色体,中，染色体决定了生物的性状；,(ii),染色体是由,基因,及其,有规律的排列,所构成的，遗传和进化过程发生在染色体上；,(iii),生物的繁殖过程是由其基因的复制过程来完成的；,(iv),通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。,(v),对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。,遗传与进化,优胜劣汰,2. 遗传算法的缘起-生物学中的遗传与进化生物学中的遗传和,2.,遗传算法的缘起,-,生物学中的遗传与进化,2.2,生物体遗传与进化的过程是怎样的,?,生物学中的遗传和进化,2. 遗传算法的缘起-生物学中的遗传与进化生物学中的遗传和,2.,遗传算法的缘起,-,生物学中的遗传与进化,2.3,什么是染色体和基因，它们与遗传有什么关系,?,生物学中的遗传和进化,基本概念,种群,(,Population),vs.,个体,(Individual),vs.,染色体,(,chromosome,),染色体,(chromosome) vs.,基因,(gene),基因型,(Genotype) vs.,表现型,(Phenotype),个体的适应度,(Fitness),选择,(Selection),复制,(Reproduction,),交配,/,杂交,(Crossover),突变,(Mutation),2. 遗传算法的缘起-生物学中的遗传与进化生物学中的遗传和,怎样研究算法：遗传算法示例,3.,计算学科的遗传算法,计算学科的遗传算法,怎样研究算法：遗传算法示例计算学科的遗传算法,3.,计算学科的遗传算法,3.1,怎样用遗传算法求解问题,?,一个简单的遗传算法应用示例,求多项式函数的最小值：,Min F(X) = X,2,-19X +20,其中,X=1,64,之间的整数。,注：此题不难求出精确解，其精确解为,X=9,或者,X=10,。,如何用遗传算法进行求解,?,3. 计算学科的遗传算法一个简单的遗传算法应用示例求多项式函,3.,计算学科的遗传算法,3.2,生物学中的概念如何与计算学科中的概念映射,?,生物学中的概念与计算学科中的概念映射,生物学中的概念,计算学科中的概念,解释,种群,解集,/,种群,若干可能解的集合,个体,解,/,个体,一个可能解的表现型，本例中即是十进制的,X,染色体,编码解,/,染色体,一个可能解的基因型，本例即是,X,的二进制编码。,X = b,6,b,5,b,4,b,3,b,2,b,1,，,其中,b,i,=0,或,1,。,基因,基因,解编码中的若干位的,b,i,适应度,适应度,一个可能解接近最优解的一个度量，本例直接用,F(X),作为其适应度的度量，其值越小越接近最优解,选择,选择,指从种群,(,解集,),中依据适应度按某种条件选择某些个个体,(,可能解,),复制,复制,将一个解从一个解集复制到另一个解集,交配,/,杂交,交叉,即交配,/,杂交，是新可能解的一种形成方法，即是对两个可能解的编码通过交换某些编码位而形成两个新的可能解的遗传操作,突变,变异,也是新可能解的一种形成方法，它是通过随机地改变一个可能解的编码的某些片段,(,或基因,),而使一个可能解变为一新的可能解的遗传操作,3. 计算学科的遗传算法生物学中的概念与计算学科中的概念映射,3.,计算学科的遗传算法,3.3,怎样模拟遗传算法进行求解,?,遗传算法求解过程的模拟,3. 计算学科的遗传算法遗传算法求解过程的模拟,3.,计算学科的遗传算法,3.4,如何设计遗传算法,?,遗传算法基本框架及其设计要点,begin,/*,遗传算法 *,/,t, 0,；,/*,进化的种群代数 *,/,生成初始种群,P,(,t,),；,计算初始种群,P,(,t,),中每个个体的适应值；,while,（不满足终止条件）,do,/*,利用下述操作生成新个体，并选择更优个体组成新种群 *,/,(1),通过复制、交叉或变异操作重组种群,P,(,t,),中,的个体，产生新个体，形成候选种群,C,(,t,),；,/*,注意此处,C(t),并未包含,P(t),中的个体,*/,(2),计算,C,(,t,),中每个个体的适应值；,(3),根据适应值从,C,(,t,),和,P(t),中选择更优的个体,组成新种群,P,(,t,+1),；,(4),t,t,+1,；,end while,选择,P(t),中最优个体为所求的解；,end begin,3. 计算学科的遗传算法遗传算法基本框架及其设计要点begi,怎样研究算法：遗传算法示例,4.,遗传算法为什么可以求解,NPC,问题,遗传算法,为什么可以求解,NPC,问题,怎样研究算法：遗传算法示例遗传算法,4.,遗传算法为什么可以求解,NPC,问题,4.1,遗传算法的本质是什么,?,遗传算法的基本思想,(a),穷举，遍历,搜索所有,可找到精确解,穷举法,或称,遍历法,：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果,-,精确解,可能是,O(n!),或,O(a,n,),NPC,问题理论上可通过枚举,-,验证的遍历算法来实现,4. 遗传算法为什么可以求解NPC问题遗传算法的基本思想(a,4.,遗传算法为什么可以求解,NPC,问题,4.1,怎样用遗传算法求解问题,?,遗传算法的基本思想,(b),完全随机搜索,随机点之间完全没有联系,随机搜索法,：在解空间中随机选择一些可能解进行验证，求出所选择可能解,(,子解空间,),中的最优解,-,近似解,基于概率论：随机选择,子解空间越大，求得满意解的可能性越大，但耗时也会加长,求出的近似解并,不能保证是满意解,不求精确解，而求近似解,-,满意解，可采取随机搜索方法,4. 遗传算法为什么可以求解NPC问题遗传算法的基本思想(b,(c),导向性随机搜索,随机点之间形成一路径,4.,遗传算法为什么可以求解,NPC,问题,4.1,怎样用遗传算法求解问题,?,遗传算法的基本思想,导向性随机搜索法,：对随机点的选取进行导向,(,导向到接近最优解的方向或路径,),基于概率论：随机选择,随机选择的可能解与前一可能解相比，更偏向于满意解,万一初始解就很差怎么办,?,为提高近似解的质量，可采取导向性随机搜索方法,(c)导向性随机搜索4. 遗传算法为什么可以求解NPC问题遗,4.,遗传算法为什么可以求解,NPC,问题,4.1,怎样用遗传算法求解问题,?,遗传算法的基本思想,(d),导向性群,(,体,),随机搜索,多随机点同步进行导向性搜索,导向性群,(,体,),随机搜索法,：通时对多个随机点的选取进行导向,(,导向到接近最优解的方向或路径,),，多条搜索路径,基于概率论：随机选择,多条路径下的最优，总比一条路径的最优要更优一些。,遗传算法就是这样一种导向性群随机搜索算法。,同一时刻多条路径上的解集合即为一个种群。多次选择，即多代进化。,为进一步提高近似解的质量，可采取导向性群,(,体,),随机搜索方法,4. 遗传算法为什么可以求解NPC问题遗传算法的基本思想(d,4.,遗传算法为什么可以求解,NPC,问题,4.2,什么情况下可用遗传算法求解问题,?,遗传算法的适用条件,对于,NP,问题，当没有其他更好的算法可以使用时，可以考虑选择遗传算法。,遗传算法的适用条件：,(1),已知“解空间”，即可能解的表现型和基因型,(2),关于可能解的“适应度”函数的计算方法,(,适应度用于判断一个可能解接近精确解的程度或方向,),。,遗传算法提供了一种求解复杂系统问题的通用框架。,4. 遗传算法为什么可以求解NPC问题遗传算法的适用条件对于,怎样研究算法：遗传算法示例,5.,怎样用遗传算法求解应用问题,怎样用遗传算法求解,具体的应用问题,(I),-,问题理解与分析建模,-,面向应用的遗传算法设计要点,-,可能解编码方案的多样性,-,交叉,/,变异规则的多样性与随机性,-,遗传算法设计的其他方面,-,仍需要思考的,怎样研究算法：遗传算法示例怎样用遗传算法求解,5.,怎样用遗传算法求解应用问题,5.1,你能举出一些需要求解的现实问题吗,?,现实世界的几个具体问题分析,例,1,：“会议室”租用问题,例,2,：“航班机组成员”选择问题,例,3,：“软件测试用例”选择问题,其实它们是同一个问题：一维的集覆盖问题,约束矩阵,a,ij,5. 怎样用遗传算法求解应用问题现实世界的几个具体问题分析例,5.,怎样用遗传算法求解应用问题,5.2,例,4,和例,1,2,3,有何不同,?,例,4 “,课程表”优化问题,有,8,门课程需要安排教室，记为,L,i,，,i=1,8,；,有,6,个教室可被使用，记为,R,j,，,j=1,6,；,要求每门课只能安排在一个教室，而每个教室最多只能安排两门课。,教室与课程班之间的约束矩阵,A,如下表给出，其中,a,ij,=1,表示该课程班可以安排在该教室，,a,ij,=0,则不可安排。,费用为教室容纳人数,/,课程班人数，即,C,ij,=K,j,/L,i,。,约束矩阵,5. 怎样用遗传算法求解应用问题例4 “课程表”优化问题约束,5.,怎样用遗传算法求解应用问题,5.2,例,4,和例,1,2,3,有何不同,?,例,1,，例,2,，例,3,例,4,一维集覆盖问题,二维集覆盖问题,使每一行都被选出的列覆盖，被哪一列或几列覆盖不重要，要满足约束矩阵,使每一行都确定安排在某一列上，使被选中的行,-,列覆盖所有的行，要满足约束矩阵,可能解是一维向量,可能解是二维矩阵,5. 怎样用遗传算法求解应用问题例1，例2，例3例4一维集覆,怎样研究算法：遗传算法示例,5.,怎样用遗传算法求解应用问题,怎样用遗传算法求解,具体的应用问题,(II),-,问题理解与分析建模,-,面向应用的遗传算法设计要点,-,可能解编码方案的多样性,-,交叉,/,变异规则的多样性与随机性,-,遗传算法设计的其他方面,-,仍需要思考的,怎样研究算法：遗传算法示例怎样用遗传算法求解,5.,怎样用遗传算法求解应用问题,5.3,遗传算法的设计要点是什么,?,NPC,求解,:,产生一个或一批可能解,判断可能解是否是问题的解,可能解的形式是怎样的,?,怎样产生待判定的可能解,?,产生多少个待判定可能解,?,怎样判定一个解是否是所求的解,?,解的表现型和基因型,交叉、变异,随机,(,概率,),解集的规模,进化的代数,随机,(,概率,),适应度,选择,(,标准,),满意解,遗传算法设计要点,5. 怎样用遗传算法求解应用问题NPC求解: 可能解的形式是,5.,怎样用遗传算法求解应用问题,5.3,遗传算法的设计要点是什么,?,一组关于解的概念需要区分,假设一个问题的解的形式为,x,，由,x,的取值空间或定义域给定的任何一个,x,值被称为,可能解,而一个问题通常有很多个关于可能解的约束，即不是任何一个,x,值都满足约束，我们可将满足问题约束的那些,x,值称为,可行解,而由一个算法在任何一组可行解中求出的最优解被称为是,近似解,而符合用户期望的近似解被称为是,满意解,所有可行解中的最优解是问题的,最优解,。,“可能解集合”,“可行解集合”,“近似解集合”,“满意解集合”,“最优解集合”,5. 怎样用遗传算法求解应用问题一组关于解的概念需要区分假设,实际问题分析,:,解的形式,解的约束,解空间,问题解的编码与解码规则设计,:,个体,(,解,),的表现型与基因型的变换函数,初始种群的规模与生成规则设计,种群个体的适应度函数设计,遗传规则的设计：交叉、变异,终止条件及最终解产生,繁衍种群的策略设计,解的满意度评估,算法效率的评估以及算法的改进,优质个体的选择,(,汰选,),方法设计,5.,怎样用遗传算法求解应用问题,5.3,遗传算法的设计要点是什么,?,遗传算法设计要点,实际问题分析: 解的形式, 解的约束,解空间问题解的编码与解,5.,怎样用遗传算法求解应用问题,5.4,为什么要考虑解的形式与解的编码,?,x,11,x,12, x,1n,x,21,x,22, x,2n, ,x,m1,x,m2, x,mn,可能解的一般形式,课程,教室,X,ij,=1,课程,i,被安排在教室,j; =0,课程未被安排在教室,j,0 0 0 0 1 0,0 1 0 0 0 0,1 0 0 0 0 0,0 0 0 1 0 0,0 1 0 0 0 0,1 0 0 0 0 0,0 0 0 1 0 0,0 0 0 0 1 0,可行解,1,1 0 0 0 0 0,0 0 1 0 0 0,0 0 0 0 1 0,0 0 0 1 0 0,0 1 0 0 0 0,1 0 0 0 0 0,0 0 0 1 0 0,0 1 0 0 0 0,可行解,2,例,4,问题的,解的形式,(,表现型,),与编码,(,基因型,),5. 怎样用遗传算法求解应用问题x11 x12 ,5.,怎样用遗传算法求解应用问题,5.4,为什么要考虑解的形式与解的编码,?,行优先编码,:,课程分段编码,一门课程相关的划为一段，有多少课程就有多少段,列优先编码,:,教室分段编码,一个教室相关的划为一段，有多少教室就有多少段,针对具体问题，可以有不同的编码方案,不同的编码方案，交叉、变异的规则也可能不同,例,4,问题的,解的形式,(,表现型,),与编码,(,基因型,),5. 怎样用遗传算法求解应用问题行优先编码: 课程分段编码,怎样研究算法：遗传算法示例,5.,怎样用遗传算法求解应用问题,怎样用遗传算法求解,具体的应用问题,(III),-,问题理解与分析建模,-,面向应用的遗传算法设计要点,-,可能解编码方案的多样性,-,交叉,/,变异规则的多样性与随机性,-,遗传算法设计的其他方面,-,仍需要思考的,怎样研究算法：遗传算法示例怎样用遗传算法求解,5.,怎样用遗传算法求解应用问题,5.5,为什么要设计交叉规则,?,怎样交叉,?,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉点,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,遗传算法的交叉规则设计,产生新的待判定的可能解,交叉,两段交叉,是否只有这一种交叉方案呢,?,两段交叉，一个染色体被分成两段，两个染色体的同位置段进行交叉重组,5. 怎样用遗传算法求解应用问题01010110101001,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,1-2,段交叉点,2-3,段交叉点,距离,1-2,段交叉点,2-3,段交叉点,距离,等距离多段交叉,5.,怎样用遗传算法求解应用问题,5.5,为什么要设计交叉规则,?,怎样交叉,?,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,产生新的待判定的可能解,交叉,等距离多段交叉,多段交叉，一个染色体被分成多段，两个染色体的同位置段进行交叉重组,遗传算法的交叉规则设计,010101101010010101101010交叉0101,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,1-2,段交叉点,2-3,段交叉点,距离,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,1-2,段交叉点,2-3,段交叉点,距离,不等距离多段交叉,5.,怎样用遗传算法求解应用问题,5.5,为什么要设计交叉规则,?,怎样交叉,?,产生新的待判定的可能解,交叉,不等距离多段交叉,多段交叉，一个染色体被分成多段，两个染色体的同位置段进行交叉重组,遗传算法的交叉规则设计,010101101010010101101010交叉0101,5.,怎样用遗传算法求解应用问题,5.5,为什么要设计交叉规则,?,怎样交叉,?,结合具体问题的解的编码方式,交叉,:,点交叉、行交叉、列交叉、块交叉,行交叉,是指对两个染色体同位置的两个课程段基因进行交叉重组,列交叉,是指对不同段的相同位置的两个染色体的基因进行交换,块交叉,则是对两个染色体的任何位置的两个块基因进行交换,点交叉,则是对两个染色体按某一概率交换其位基因,5. 怎样用遗传算法求解应用问题结合具体问题的解的编码方式,交叉操作本质上是一种组合,，其组合所形成的可能解空间依然是庞大的，难以确定性的遍历每个组合。,基于概率的随机处理方法,也是遗传算法的核心处理机制,交叉概率,：,在一个群体中，,个体,被选择出进行,交,叉,的概率,交叉点的选择,：,可,通过随机方式产生,子空间中的待判定解的选择,：可,通过随机方式产生,5.,怎样用遗传算法求解应用问题,5.6,你体会到为什么要交叉以及怎样交叉重组的多样性了吗,?,交叉与随机,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,交叉点总计,12,个,取几个,?,种群,交叉操作本质上是一种组合，其组合所形成的可能解空间依然是庞大,(1),种群中个体的配对分组问题，即哪两个个体进行配对交叉,；,(2),两段交叉中交叉点位置的选择,；,(3),多段交叉中的交叉点距离的变化与不变，即两个或多个交叉点间等距离和不等距离的多段选择问题,；,(4),结合问题解编码的交叉与随机策略,；,5.,怎样用遗传算法求解应用问题,5.6,你体会到为什么要交叉以及怎样交叉重组的多样性了吗,?,交叉与随机,交叉组合产生新可能解的方式是变化多样的,0,1,0,1,0,1,1,0,1,0,1,0,0,0,1,0,0,0,1,1,1,0,0,1,0,1,0,1,0,1,1,0,1,0,1,0,种群,(,解集,),0,1,0,1,0,1,1,0,1,0,1,0,0,0,1,0,0,0,1,1,1,0,0,1,0,0,1,0,0,0,1,1,1,0,0,1,繁衍,:,交叉,交叉,交叉,(1)种群中个体的配对分组问题，即哪两个个体进行配对交叉；5,交叉操作,I,：点交叉,设,P,1,和,P,2,表示两个,n,位的父代染色体，,f(P,1,),和,f(P,2,),分别表示两个父代的适应值，,C,表示子代染色体。点交叉操作如下：,step1: i=1,step2:,如果,P,1,i=,P,2,i,，则,C,i=,P,1,i=,P,2,i,step3:,如果,P,1,i,P,2,i,，则,step3.1:,以概率,p=,f(P,1,),/(,f(P,1,),+,f(P,2,),让,C,i:=P,1,i,step3.2:,以概率,1-p,让,C,i:=,P,2,i,step4:,如果,i =n,，停止；否则,i=i+1,，返回,step2,5.,怎样用遗传算法求解应用问题,5.7,怎样将随机和交叉结合在一起呢,?,交叉与随机,交叉策略,按前述的各种策略进行，每一种策略都是一子解空间,。,随机,可依据问题选择不同的概率模型，进行处理。,概率模型的不同、交叉策略选择的不同构成了丰富多彩的遗传算法,交叉操作I：点交叉5. 怎样用遗传算法求解应用问题交叉与随机,5.,怎样用遗传算法求解应用问题,5.7,怎样将随机和交叉结合在一起呢,?,交叉与随机,交叉操作,II,：行交叉,设,P,1,和,P,2,表示两个,k*h,位的父代染色体，其中,k,为每一段的位数，,h,为染色体的分段数目，,f(P,1,),和,f(P,2,),分别表示两个父代的适应度值，,C,表示子代染色体。,step1:,产生一个,0,至,h-1,的随机数,x,；,step2:,如果,P,1,x*k+i=,P,2,x*k+i for all i=1,k,，则不产生后代；,step3:,如果,P,1,x*k+i,P,2,x*k+i for any i=1,k,，则以概率,p=,f(P,1,),/ (,f(P,1,),+,f(P,2,),让,P,1,x*k+i,与,P,2,x*k+i for i=1,k,交换；,/,注：,两个染色体的,x,段如相同,则不交换,否则以概率,p,进行交换。,5. 怎样用遗传算法求解应用问题交叉与随机交叉操作II：行交,5.,怎样用遗传算法求解应用问题,5.7,怎样将随机和交叉结合在一起呢,?,交叉与随机,交叉操作,III,：列交叉,设,P,1,和,P,2,表示两个,k*h,位的父代染色体，其中,k,为每一段的位数，,h,为染色体的分段数目，,f(P,1,),和,f(P,2,),分别表示两个父代的适应,度,值，,C,表示子代染色体。,step1:,产生一个,0,至,k-1,的随机数,x,；,step2:,如果,P,1,i*k+x=,P,2,i*k+x for all i=1,h,，则不产生后代；,step3:,如果,P,1,i*k+x,P,2,i*k+x for any i=1,h,，则以概率,f(P,1,),/(,f(P,1,),+,f(P,2,),让,P,1,i*k+x,与,P,2,i*k+x,交换,for all i=1,h,；,/,注：,两个染色体的各段的,x,位如都相同，则不交换，否则以概率,p,进行交换,。,5. 怎样用遗传算法求解应用问题交叉与随机交叉操作III：列,交叉策略比较：,“点交叉”将覆盖,更大的,可能,解空间,，产生更多种新可能解，增加获得最优解的机会；,“行交叉”、“列交叉”大大地,压缩,了可能解的,解空间,，产生的可能解都是可行解,(编码方案将约束条件考虑进去了,),；,策略的选择需要折中,：选择搜索更加广泛的解空间呢，还是选择压缩搜索空间呢？需要折中。,5.,怎样用遗传算法求解应用问题,5.8,不同的交叉随机策略有什么特点,?,交叉与随机,不同的交叉策略对算法的求解质量和收敛速度等方面是有影响的，没有一种设计能够面面俱到，因此如何在算法不同方面性能之间权衡，也是遗传算法设计过程的关键所在，体现了一定程度的技术性和艺术性。,交叉策略比较：5. 怎样用遗传算法求解应用问题交叉与随机不同,怎样研究算法：遗传算法示例,5.,怎样用遗传算法求解应用问题,怎样用遗传算法求解,具体的应用问题,(IV),-,问题理解与分析建模,-,面向应用的遗传算法设计要点,-,可能解编码方案的多样性,-,交叉,/,变异规则的多样性与随机性,-,遗传算法设计的其他方面,-,仍需要思考的,怎样研究算法：遗传算法示例怎样用遗传算法求解,引入,变异操作,的目的,：,一是使遗传算法具有,局部的随机搜索能力,。,二是使遗传算法,可维持群体多样性,。,变异操作,是对群体中的某些个体染色体的某些基因进行突变处理,变异概率,(PM, probability of mutation),，控制算法中变异操作的使用频率。,变异操作的,基本步骤,：,a),对种群中所有个体以事先设定的变异概率判断是否进行变异；,b),对进行变异的个体随机选择变异位置进行变异。,遗传算法设计的其他问题,5.,怎样用遗传算法求解应用问题,5.9,你能自己分析一下遗传算法的其他问题吗,?,引入变异操作的目的：变异操作是对群体中的某些个体染色体的某些,遗传算法设计的其他问题,5.,怎样用遗传算法求解应用问题,5.9,你能自己分析一下遗传算法的其他问题吗,?,适应度函数的选择,主要考察其是否能度量一个可能解接近最优解的程度和方向。,初始种群,中的个体通常,是,随机产生的。,初始种群的规模与个体解，可依据问题解空间的分布特性来选择。,终止条件,通常有以下几种：,(1),进化次数限制,-,进化到指定的代数即可终止算法；,(2),计算耗费的资源限制,（如计算时间、计算占用的内存等）,-,当达到一定的资源占用量时可终止算法，如当产生超过一定数量的不重复可行解后即可终止；,(3),某一个个体已经满足最优值的条件,，即最优值已经找到；,(4),适应度已经达到饱和,，继续进化不会产生适应度更好的个体；,(5),人为干预,；,(6),以上两种或更多种的组合,。,遗传算法设计的其他问题5. 怎样用遗传算法求解应用问题适应度,5.,怎样用遗传算法求解应用问题,5.10,你思考过下列问题吗,?,思考,1,：遗传算法的收敛速度和解的质量有什么关系呢？,解的质量,，可以使用“近似率”来衡量，所谓近似率是指算法求得的解与问题最优解的近似程度。,收敛速度,，,是指对于具有迭代特征的近似算法，在迭代多少次后能够使得结果稳定,(,通俗来讲,，,即结果不再随进一步迭代而发生变化或发生极小的可以被忽略的变化,),，它从一定程度反映了算法求解的“快慢”,“在执行相同次数的迭代后，近似率高的算法更好”,“在达到期望的满意解的前提下，迭代次数越少越好”,算法的比较,：当不同算法均应用多次后，求得满意解次数越多的算法越好！,5. 怎样用遗传算法求解应用问题思考1：遗传算法的收敛速度和,思考,3,：染色体编码中什么是“遗传基因”，怎样发现种群的遗传基因，怎样使遗传基因被遗传被继承？,一般，染色体基因就是一个二进制位,。,一个种群的优质个体的编码中：,“值相同位”越多的是否就是遗传基因呢,？,“,0,、,1,组合相同的片段”越多是否就是遗传基因呢,？,例如,00,10,1011, 00,10,1001, 10,10,0101, 01,10,0100,自左而右第,3-4,位“,10,”有,4,个相同，它是否是遗传基因呢？,发现了遗传基因后，在交叉变异重组时又怎样使其不受破坏呢？,思考,2,：遗传算法各项参数对算法收敛速度和解的质量有什么影响？各次迭代的种群规模大小，尤其是初始种群规模大小对算法的性能有什么影响呢？,不同的交叉变异规则反映了算法对可能解空间的覆盖范围，覆盖范围越大则获得最优解的概率也越大。,此外，如变异率、交叉率等，对算法的性能又有什么影响呢？,5.,怎样用遗传算法求解应用问题,5.10,你思考过下列问题吗,?,思考3：染色体编码中什么是“遗传基因”，怎样发现种群的遗传基,社会,/,自然现象,(,遗传与进化,),计算学科的,(,遗传,),算法,(,遗传,),算法的本质,(,遗传,),算法的应用,本讲小结,社会/自然现象(遗传与进化)计算学科的(遗传)算法(遗传)算,本讲小结,社会,/,自然现象,(,遗传与进化,),计算学科的,(,遗传,),算法,(,遗传,),算法的本质,(,遗传,),算法的应用,计算与计算系统,(,浅层次,),社会,/,自然,/,生活,计算与计算系统,(,深层次,),由遗传算法的学习，学会算法的研究，更重要的是养成科学研究良好的习惯,本质,应用,宽度学习,深度学习,本讲小结社会/自然现象(遗传与进化)计算学科的(遗传)算法(,2013-2014,Questions & Discussion?,第,9,讲 怎样研究算法：遗传算法示例,2013-2014Questions & Discussio,