遗传算法ppt专题知识专家讲座.pptx

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,当代设计方法之遗传优化算法,遗传算法ppt专题知识专家讲座,第1页,目录,1,、智能优化算法,2,、基本遗传算法,3,、遗传算法特点,4,、遗传算法数学基础,5,、,遗传算法收敛性分析,6,、,遗传算法应用举例,7,、,遗传算法小结,遗传算法ppt专题知识专家讲座,第2页,1,、智能优化算法,智能优化算法又称为当代启发式算法，是一个含有全局优化性能、通用性强、且适合于并行处理算法。这种算法普通含有严密理论依据，而不是单纯凭借教授经验，理论上能够在一定时间内找到最优解或近似最优解。,遗传算法ppt专题知识专家讲座,第3页,惯用智能优化算法,（,1,）遗传算法,（,Genetic Algorithm,，简称,GA,）,（,2,）模拟退火算法,（,Simulated Annealing,，简称,SA,）,（,3,）禁忌搜索算法,（,Tabu Search,，简称,TS,）,遗传算法ppt专题知识专家讲座,第4页,智能优化算法特点,它们共同特点：都是从任一组解出发，按照某种机制，以一定概率在整个求解空间中探索最优解。因为它们能够把搜索空间扩展到整个问题空间，因而含有全局优化性能。,遗传算法ppt专题知识专家讲座,第5页,遗传算法起源,遗传算法是由美国,Michigan,大学,J.Holland,教授于,1975,年在他专著,自然界和人工系统适应性,中首先提出，它是一类借鉴生物界自然选择和自然遗传机制随机化搜索算法,。,遗传算法ppt专题知识专家讲座,第6页,遗传算法搜索机制,遗传算法模拟自然选择和自然遗传过程中发生繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从候选解群中选取较优个体，利用遗传算子,(,选择、交叉和变异,),对这些个体进行组合，产生新一代候选解群，重复此过程，直到满足某种收敛指标为止。,遗传算法ppt专题知识专家讲座,第7页,2,、基本遗传算法,基本遗传算法（,Simple Genetic Algorithms,，简称,SGA,，又称简单遗传算法或标准遗传算法），是由,Goldberg,总结出一个最基本遗传算法，其遗传进化操作过程简单，轻易了解，是其它一些遗传算法雏形和基础。,遗传算法ppt专题知识专家讲座,第8页,基本遗传算法组成,（,1,）编码（产生初始种群）,（,2,）适应度函数,（,3,）遗传算子（选择、交叉、变异）,（,4,）运行参数,遗传算法ppt专题知识专家讲座,第9页,SGA,框图,产生初始群体,是否满足停顿准则,是,输出结果并结束,计算个体适应度值,百分比选择运算,单点交叉运算,基本位变异运算,否,产生新一代群体,执行,M/2,次,遗传算法ppt专题知识专家讲座,第10页,染色体及其编码,遗传算法以生物细胞中染色体,(,chromosome,),代表问题中个体对象。而一个染色体能够看作是由若干基因组成位串,所以需要将问题中个体对象编码为某种位串形式。这么,原个体对象也就相当于生命科学中所称生物体表现型,(,phenotype,),而其编码即,“,染色体,”,也就相当于生物体基因型,(,genotype,),。遗传算法中染色体普通用字符串表示,而基因也就是字符串中一个个字符。比如,假设数字,9,是某问题中个体对象,则我们就能够用它二进制数串,1001,作为它染色体编码。,遗传算法ppt专题知识专家讲座,第11页,基因型：,1000101110110101000111,表现型：,0.637197,编码,解码,个体（染色体）,基因,遗传算法ppt专题知识专家讲座,第12页,适应度与适应度函数,遗传算法对一个个体（解）好坏用适应度函数值来评价，适应度函数值越大，解质量越好。,适应度,(fitness),就是借鉴生物个体对环境适应程度,而对所求解问题中对象设计一个表征优劣测度。适应度函数,(fitness function),就是问题中全体对象与其适应度之间一个对应关系,即对象集合到适应度集合一个映射。,它普通是定义在论域空间上一个实数值函数。,适应度函数是遗传算法进化过程驱动力，也是进行自然选择唯一标准，它设计应结合求解问题本身要求而定。,说明,：“论域”是,数理逻辑,中概念。“在一个逻辑系统中，全部个体组成集合，称为个体域，亦称论域。”,遗传算法ppt专题知识专家讲座,第13页,种群,(,population,),SGA,采取随机方法生成若干个个体集合，该集合称为初始种群。初始种群中个体数量称为种群规模。,或种群就是模拟生物种群而由若干个染色体组成群体,它普通是整个论域空间一个很小子集。,遗传算法ppt专题知识专家讲座,第14页,遗传操作,遗传算法中有三种关于染色体运算（,遗传算子）,:,选择,-,复制、交叉和变异,这三种运算被称为遗传操作或遗传算子,(,genetic operator,),。,遗传算法ppt专题知识专家讲座,第15页,选择,-,复制算子和选择概率,选择,-,复制,(,selectionreproduction,),操作是模拟生物界优胜劣汰自然选择法则一个染色体运算,就是从种群中选择适应度较高染色体进行复制,以生成下一代种群。选择,-,复制通常做法是,对于一个规模为,N,种群,S,按每个染色体,x,i,S,选择概率,P,(,x,i,),所决定选中机会,分,N,次从,S,中随机选定,N,个染色体,并进行复制。这里选择概率,P,(,x,i,),计算公式为,Note:,复制即为个体被选中并遗传到下一代；,遗传算法ppt专题知识专家讲座,第16页,其中,f,为适应度函数,f,(,x,i,),为,x,i,适应度。能够看出,染色体,x,i,被选中概率就是其适应度,f,(,x,i,),所占种群中全体染色体适应度之和百分比。,显然,按照这种选择概率定义,适应度越高染色体被随机选定概率就越大,被选中次数也就越多,从而被复制次数也就越多。,相反,适应度越低染色体被选中次数也就越少,从而被复制次数也就越少。假如把复制看做染色体一次换代话,则这就意味着适应度越高染色体其后代也就越多,适应度越低染色体其后代也就越少,甚至被淘汰。这正吻合了优胜劣汰自然选择法则。,遗传算法ppt专题知识专家讲座,第17页,SGA,选择算子,遗传算法使用选择运算来实现对群体中个体进行优胜劣汰操作：,适应度高个体被遗传到下一代群体中概率大；适应度低个体，被遗传到下一代群体中概率小。,选择操作任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。,SGA,中选择算子采取,轮盘赌选择,方法。,遗传算法ppt专题知识专家讲座,第18页,轮盘赌选择又称,百分比选择算子,，它基本思想是：,各个个体被选中概率与其适应度函数值大小成,正比。,遗传算法ppt专题知识专家讲座,第19页,上述按概率选择方法可用一个称为赌轮原理来实现。即做一个单位圆,然后按各个染色体选择概率将圆面划分为对应扇形区域,(,如图,1,所表示,),。这么,每次选择时先转动轮盘,当轮盘静止时,上方指针所正对着扇区即为选中扇区,从而对应染色体即为所选定染色体。比如,假设种群,S,中有,4,个染色体,:,s,1,s,2,s,3,s,4,其选择概率依次为,:0.11,0.45,0.29,0.15,则它们在轮盘上所占份额如图,1,中各扇形区域所表示。,图,1,赌轮选择示例,遗传算法ppt专题知识专家讲座,第20页,在算法中赌轮选择法可用下面过程来模拟,:,在,0,1,区间内产生一个均匀分布伪随机数,r,。,若,r,q,1,则染色体,x,1,被选中。,若,q,k,-1,r,q,k,(2,k,N,),则染色体,x,k,被选中。,其中,q,i,称为染色体,x,i,(,i,=1,2,n,),积累概率,其计算公式为：,遗传算法ppt专题知识专家讲座,第21页,一个染色体,x,i,被选中次数,能够用下面期望值,e,(,x,i,),来确定：,其中,f,为种群,S,中全体染色体平均适应度值。,遗传算法ppt专题知识专家讲座,第22页,交叉,(crossover),算子,所谓交叉运算，是指对两个相互配正确染色体依据交叉概率,P,c,按某种方式相互交换,两个染色体一些位上基因,，从而形成两个新个体。,交叉运算是遗传算法区分于其它进化算法主要特征，它在遗传算法中起关键作用，是产生新个体主要方法,。,SGA,中交叉算子采取单点交叉算子。,遗传算法ppt专题知识专家讲座,第23页,比如,设染色体,s,1,=01001011,s,2,=10010101,交换其后,4,位基因,即：,则得新串,s,1,=01000101,s,2,=10011011,。,s,1,和,s,2,能够看做是原染色体,s,1,和,s,2,子代染色体。,交叉,(crossover),算子,单点交叉运算：,交叉前：,00000|,01110000000010000,11100|,00000111111000101,交叉后：,00000|,00000111111000101,11100|,01110000000010000,交叉点,遗传算法ppt专题知识专家讲座,第24页,变异,(mutation),算子,变异,(mutation),亦称,突变,就是改变染色体某个,(,些,),位上,(,基因座,),基因。,是依据变异概率,P,m,将个体编码串中一些基因值用其它基因值来替换，从而形成一个新个体。遗传算法中变异运算是产生新个体辅助方法，它决定了遗传算法局部搜索能力，同时保持种群多样性。交叉运算和变异运算相互配合，共同完成对搜索空间全局搜索和局部搜索。,SGA,中变异算子采取,基本位变异算子,。,遗传算法ppt专题知识专家讲座,第25页,基本位变异算子,基本位变异算子是指对个体编码串随机指定某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示个体，若需要进行变异操作某一基因座上原有基因值为,0,，则变异操作将其变为,1,；反之，若原有基因值为,1,，则变异操作将其变为,0,。,遗传算法ppt专题知识专家讲座,第26页,基本位变异算子执行过程,变异前：,00000111000,0,000010000,变异后：,00000111000,1,000010000,变异点,遗传算法ppt专题知识专家讲座,第27页,运行参数,（,1,）,M,：种群规模,(,20-100,),（,2,）,T,：遗传运算终止进化代数,(,100-500,),（,3,）,P,c,：交叉概率,(,0.4-0.9,),（,4,）,P,m,：变异概率,(,0.001-0.01,),参加交叉运算染色体个数占全体染色体总数百分比，记为,P,c,。因为生物繁殖时染色体交叉是按一定概率发生,所以参加交叉操作染色体也有一定百分比,而交叉率也就是交叉概率。,变异率,(mutation rate),是指,发生变异基因位数所占全体染色体基因总位数,百分比，记为,P,m,。因为在生物繁衍进化过程中,变异也是按一定概率发生,而且发生概率普通很小,所以变异率也就是变异概率。,遗传算法ppt专题知识专家讲座,第28页,SGA,框图,产生初始群体,是否满足停顿准则,是,输出结果并结束,计算个体适应度值,百分比选择运算,单点交叉运算,基本位变异运算,否,产生新一代群体,执行,M/2,次,遗传算法ppt专题知识专家讲座,第29页,基本遗传算法流程说明：,步,1,在论域空间,U,上定义一个适应度函数,f,(,x,),，给定种群规模,N,，交叉率,P,c,和变异率,P,m,，代数,T,；,步,2,随机产生,U,中,N,个染色体,s,1,s,2,s,N,，组成初始种群,S,=,s,1,s,2,s,N,，置代数计数器,t,=1,；,步,3,计算,S,中每个染色体适应度,f(s,i,),；,步,4,若终止条件满足，则取,S,中适应度最大染色体作为所求结果，算法结束。,步,5,按选择概率,P,(,x,i,),所决定选中机会，每次从,S,中随机选定,1,个染色体并将其复制，共做,N,次，然后将复制所得,N,个染色体组成群体,S,1,；,遗传算法ppt专题知识专家讲座,第30页,步,6,按交叉率,P,c,所决定参加交叉染色体数,c,，从,S,1,中随机确定,c,个染色体，配对进行交叉操作，并用产生新染色体代替原染色体，得群体,S,2,；,步,7,按变异率,P,m,所决定变异次数,m,，从,S,2,中随机确定,m,个染色体，分别进行变异操作，并用产生新染色体代替原染色体，得群体,S,3,；,步,8,将群体,S,3,作为新一代种群，即用,S,3,代替,S,，,t,=,t,+1,，转步,3,；,遗传算法ppt专题知识专家讲座,第31页,需要说明是,在应用遗传算法处理实际问题时,还需给出结构模式表示方案、适应度计算方法、终止条件等。表示方案通常是把问题搜索空间每一个可能点,编码为一个看做染色体字符串,字符通常采取二进制数,0,、,1,。适应度计算方法普通依据实际问题而定。,遗传算法ppt专题知识专家讲座,第32页,3,、遗传算法特点,（,1,）,GA,搜索群体中点是并行,而不是单点；,（,2,）,GA,使用概率变换规则,而不是确定变换规则,;,（,3,）适应度函数不受连续、可微等条件约束，适用范围很广。只需要影响搜索方向目标函数和相对应适应度函数,;,(4)GA,使用编码参数集,而不是本身参数集,;,遗传算法ppt专题知识专家讲座,第33页,4,、遗传算法数学基础,（,1,）模式定理,(,Pattern Theorem,),（,2,）积木块假设,(,Building Block Hypothesis,),遗传算法ppt专题知识专家讲座,第34页,模式,模式是指种群个体基因串中相同样板，它是一个用来描述基因串中一些位置上含有结构相同性,0,、,1,字符串集合方法。在二进制编码中，基于三值字符集,(0,1,*),字符串所产生能描述含有一些结构相同性,0,1,字符串集字符串称为,模式,.,符号*代表任意字符，即,0,或者,1,。,模式示例：,*0001,描述了含有,”0001”,特征全部字符串,即,(00001,10001);,遗传算法ppt专题知识专家讲座,第35页,两个定义,定义,1,：模式,H,中确定位置个数称为模式,H,阶，记作,O(H),。比如,O(10*1)=3,。,O(011*1*)=4;O(0*)=1,note:,一个模式阶数越高，其,样本数就越少,因而,确定性就越高,定义,2,：模式,H,中第一个确定位置和最终一个确定位置之间距离称为模式,H,定义距，记作,(H),。比如,(10*1)=4;(0*)=0,遗传算法ppt专题知识专家讲座,第36页,模式阶和定义距含义,模式阶用来反应不一样模式间确定性差异，一个模式阶数越高，其,样本数就越少,因而,确定性就越高。在遗传操作中，即使阶数相同模式，也会有不一样性质，而,模式定义距就反应了这种性质差异。,遗传算法ppt专题知识专家讲座,第37页,模式定理,模式定理,：在遗传算子选择、交叉和变异作用下，含有低阶、短定义距以及平均适应度高于种群平均适应度模式在子代中将以指数级增加。,(GA,必要条件,),模式定理确保了较优模式（,遗传算法较优解,）样本数目呈指数级增加，为解释遗传算法机理提供了数学基础。,遗传算法ppt专题知识专家讲座,第38页,模式定理,从模式定理可看出，有高平均适应度、短定义距、低阶基因模式，其样本在子代里取得最少以指数增加数目，这主要是因为选择使,最好模式有更多复制,，交叉算子不轻易破坏高频率出现、短定义距模式，而普通突变概率又相当小，因而它对这些主要模式几乎没有影响。,遗传算法ppt专题知识专家讲座,第39页,积木块假设,积木块假设：,阶数低,、,短定义距、适应度高模式（,这类模式称为积木块,），在遗传算子作用下相互结合，能生成阶数高、长度长、适应度高模式,可最终靠近全局最优解。,与积木块一样,一些好模式在遗传算子作用下相互拼搭、结合,产生适应度更高串,从而找到了更优可行解,这正是积木块假设所揭示内容,.,遗传算法ppt专题知识专家讲座,第40页,S1,AA,S2,S3,CC,S4,BB,S5,S6,S7,AA,S8,BB,初始,种群,S1,AA,S2,BB,S3,AA,CC,S4,BB,S5,S6,CC,S7,AA,BB,S8,第二代种群,积木块：,AA BB CC,遗传算法ppt专题知识专家讲座,第41页,S1,AA,S2,BB,S3,AA,BB,CC,S4,S5,S6,BB,S7,AA,CC,S8,第三代种群,遗传算法ppt专题知识专家讲座,第42页,模式定理确保了较优模式,(,遗传算法较优解,),样本数呈指数增加，从而满足了寻找最优解必要条件,即遗传算法存在着寻找到全局最优解可能性；,积木块假设则指出,GA,具备找到全局最优解能力,即积木块在遗传算子作用下，能生成阶数高、长度长、适应度高模式,最终生成全局最优解。,小 结,遗传算法ppt专题知识专家讲座,第43页,5.,遗传算法收敛性分析,遗传算法要实现全局收敛，首先要求,任意初始种群经有限步都能抵达全局最优解,；,其次算法必须由,保优操作来预防最优解遗失。,与算法收敛性相关原因主要包含种群规模、选择操作、交叉概率和变异概率。,遗传算法ppt专题知识专家讲座,第44页,种群规模对收敛性影响,通常，种群太小则不能提供足够采样点，以致算法性能很差；种群太大，尽管能够增加优化信息，阻止早熟收敛发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度迟缓。,遗传算法ppt专题知识专家讲座,第45页,选择操作对收敛性影响,选择操作使高适应度个体能够以更大概率生存，从而提升了遗传算法全局收敛性。假如在算法中采取最优保留策略，即将父代群体中最正确个体保留下来，不参加交叉和变异操作，使之直接进入下一代，,最终可使遗传算法以概率,1,收敛于全局最优解,。,1.,轮盘赌,2.,随机竞争选择,(,按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高选中，如此重复，直到选满为止,),3.,最优保留策略,(,当前种群中适应度最高个体不参加交叉和变异操作，而是用它来替换掉本代种群中经交叉、变异等操作后所产生适应度最低个体，确保算法终止时得到最终结果是历代出现过得最高适应度个体,),.,遗传算法ppt专题知识专家讲座,第46页,交叉概率对收敛性影响,交叉操作用于,个体对,，产生新个体，实质上是在解空间中,进行有效搜索,。交叉概率太大时，种群中个体更新很快，会造成高适应度值个体很快被破坏掉；概率太小时，交叉操作极少进行，从而会使搜索停滞不前，造成算法不收敛。,遗传算法ppt专题知识专家讲座,第47页,变异概率对收敛性影响,变异操作是对种群模式扰动，有利于增加种群多样性。不过，变异概率太小则极难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。,遗传算法ppt专题知识专家讲座,第48页,遗传算法ppt专题知识专家讲座,第49页,遗传算法本质,遗传算法本质上是对染色体模式所进行一系列运算，即经过选择算子将当前种群中优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。经过这些遗传操作，模式逐步向很好方向进化，最终得到问题最优解。,遗传算法ppt专题知识专家讲座,第50页,6.,遗传算法应用举例,例,1.,利用遗传算法求解区间,0,31,上二次函数,y,=,x,2,最大值；,【,分析,】,能够看出,只要能在区间,0,31,中找到函数值最大点,a,则函数,y,=,x,2,最大值也就能够求得。于是,原问题转化为在区间,0,31,中寻找能使,y,取最大值点,a,问题。显然,对于这个问题,任一点,x,0,31,都是可能解,而函数值,f,(,x,)=,x,2,也就是衡量,x,能否为最正确解一个测度。那么,用遗传算法眼光来看,区间,0,31,就是一个,(,解,),空间,x,就是其中个体对象,函数值,f,(,x,),恰好就能够作为,x,适应度。这么,只要能给出个体,x,适当染色体编码,该问题就能够用遗传算法来处理。,遗传算法ppt专题知识专家讲座,第51页,解：,(1),定义适应度函数,编码染色体。由上面分析,函数,f,(,x,)=,x,2,就可作为空间,U,上适应度函数。显然,y,=,x,2,是一个单调增函数,其取最大值点,x=31,是个整数。另首先,5,位二进制数也刚好能表示区间,0,31,中全部整数。所以,我们就仅取,0,31,中整数来作为参加进化个体,而且用,5,位二进制数作为个体,x,基因型编码,即染色体,。,(2),设定种群规模,产生初始种群。设定种群规模为,4,取染色体,s,1,=01101(13),s,2,=11000(24),s,3,=0100,0(8),s,4,=10011(19),组成初始种群,S,1,。,遗传算法ppt专题知识专家讲座,第52页,(3),计算各代种群中各染色体适应度,并进行遗传操作,直到适应度最高染色体,(,该问题中显然为,“,11111,”,=31,),出现为止。,计算,S,1,中各染色体适应度、选择概率、积累概率等并列于表,1,中。,遗传算法ppt专题知识专家讲座,第53页,表,1,第一代种群,S,1,中各染色体情况,r,1,=0.450126,r,2,=0.110347,r,3,=0.572496,r,4,=0.98503,设从区间,0,1,中产生,4,个随机数以下,:,遗传算法ppt专题知识专家讲座,第54页,选择,-,复制,设从区间,0,1,中产生,4,个随机数以下,:,r,1,=0.450126,r,2,=0.110347,r,3,=0.572496,r,4,=0.98503,按赌轮选择法，染色体,s,1,s,2,s,3,s,4,被选中次数依次为：,1,2,0,1,。于是，经复制得到新群体以下：,s,1,=11000,（,24,）,s,2,=01101,（,13,）,s,3,=11000,（,24,）,s,4,=10011,（,19,）,能够看出，,在第一轮选择中适应度最高染色体,s,2,被选中两次，因而被复制两次；而适应度最低染色体,s,3,一次也没有选中而遭淘汰。,遗传算法ppt专题知识专家讲座,第55页,交叉,设交叉率,p,c,=100%,，即,S,1,中全体染色体都参加交叉运算。设,s,1,与,s,2,配对，,s,3,与,s,4,配对。分别交换染色体,后两位基因，,得新染色体：,s,1,=11001,（,25,）,s,2,=01100,（,12,）,s,3,=11011,（,27,）,s,4,=10000,（,16,）,变异,设变异率,p,m,=0.001,。这么，群体,S,1,中共有,540.001=0.02,位基因能够变异。,0.02,位显然不足,1,位，所以本轮遗传操作不做变异。,现在，我们得到了第二代种群,S,2,：,s,1,=11001,（,25,）,s,2,=01100,（,12,）,s,3,=11011,（,27,）,s,4,=10000,（,16,）,Note,:s,1,=110,00,（,24,）,s,2,=011,01,（,13,）,s,3,=110,00,（,24,）,s,4,=100,11,（,19,）,遗传算法ppt专题知识专家讲座,第56页,假设这一轮选择,-,复制操作中，种群,S,2,中,4,个染色体都被选中（因为选择概率毕竟只是一个几率，所以,4,个染色体恰好都被选中情况是存在），我们得到群体,：,s,1,=11,001,（,25,）,s,2,=01,100,（,12,）,s,3,=11,011,（,27,）,s,4,=10,000,（,16,）,然后，做交叉运算，让,s,1,与,s,2,，,s,3,与,s,4,分别交换后三位基因，得,s,1,=11100,（,28,）,s,2,=01001,（,9,）,s,3,=11000,（,24,）,s,4,=10011,（,19,）,这一轮依然不会发生变异。于是，得第三代种群,S,3,：,s,1,=11100,（,28,）,s,2,=01001,（,9,）,s,3,=11000,（,24,）,s,4,=10011,（,19,）,表,2,第二代种群,S,2,中各染色体情况,遗传算法ppt专题知识专家讲座,第57页,表,3,第三代种群,S,4,中各染色体情况,遗传算法ppt专题知识专家讲座,第58页,设这一轮选择,-,复制结果为：,s,1,=111,00,（,28,）,s,2,=111,00,（,28,）,s,3,=110,00,（,24,）,s,4,=100,11,（,19,）,然后，做交叉运算，让,s,1,与,s,4,，,s,2,与,s,3,分别交换后两位基因，得,s,1,=11111,（,31,）,s,2,=11100,（,28,）,s,3,=11000,（,24,）,s,4,=10000,（,16,）,这一轮依然不会发生变异。于是，得第四代种群,S,4,：,s,1,=11111,（,31,）,s,2,=11100,（,28,）,s,3,=11000,（,24,）,s,4,=10000,（,16,）,遗传算法ppt专题知识专家讲座,第59页,显然，在这一代种群中已经出现了适应度最高染色体,s,1,=11111,。于是，遗传操作终止，将,染色体,“,11111,”,作为最终止果输出。,然后，将染色体,“,11111”,解码为表现型,，即得所求最优解：,31,。将,31,代入函数,y,=,x,2,中，即得原问题解，即函数,y,=,x,2,最大值为,961,。,遗传算法ppt专题知识专家讲座,第60页,遗传算法ppt专题知识专家讲座,第61页,遗传算法ppt专题知识专家讲座,第62页,7.,遗传算法小结,由上所述,我们看到,遗传算法模拟自然选择和有性繁殖、遗传变异自然原理,实现了优化搜索和问题求解。遗传算法主要特点是,:,遗传算法普通是直接在解空间搜索,;,遗传算法搜索随机地始于搜索空间一个点集,而不是固定地始于搜索空间初始节点或终止节点,所以遗传算法是一个随机搜索算法。,遗传算法ppt专题知识专家讲座,第63页,二维优化问题迭代过程,遗传算法ppt专题知识专家讲座,第64页,梯度方向与等值线关系,遗传算法ppt专题知识专家讲座,第65页,遗传算法总是在寻找优解,(,最优解或次优解,),所以遗传算法又是一个优化搜索算法。,遗传算法搜索过程是从空间一个点集,(,种群,),到另一个点集,(,种群,),搜索,而不是从空间一个点到另一个点地搜索。因而它实际是一个并行搜索,适合大规模并行计算,而且这种种群到种群搜索有能力跳出局部最优解。,遗传算法适应性强,除需知适应度函数外,几乎不需要其它先验知识。,遗传算法长于全局搜索,它不受搜索空间限制性假设约束,不要求连续性,能以很大概率从离散、多极值、,含有噪声高维问题中找到全局最优解。,遗传算法ppt专题知识专家讲座,第66页,