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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,遗传算法,Genetic Algorithm,遗传算法GA专题知识专家讲座,第1页,主要内容,一、遗传算法概述,二、遗传算法基本操作,三、遗传算法原理,四、遗传算法应用,遗传算法GA专题知识专家讲座,第2页,1,、遗传算法起源,遗传算法,(,Genetic Algorithm,GA),是由美国,J.Holland,教授于,1975,年在他专著,自然界和人工系统适应性,中首先提出，它,是,一类借鉴生物界自然选择和自然遗传机制随机化搜索算法,。,GA,起源于达尔文,进化论,、魏茨曼,物种选择,学说和孟德尔,群体遗传,学说。其基本思想是模拟自然界遗传机制和生物进化论而形成一个,随机化,搜索全局最优解,算法。,一、遗传算法概述,遗传算法GA专题知识专家讲座,第3页,2,、生物进化理论和遗传学基本知识,一、遗传算法概述,(1),达尔文自然选择说,遗传（,heredity,）：,子代和父代含有相同或相同性状，确保物种稳定性。,变异（,variation,）：,子代与父代,子代不一样个体之间总有差异，是生命多样性根源。,生存斗争和适者生存：,含有适应性变异个体被保留，不具适应性变异个体被淘汰。,遗传算法GA专题知识专家讲座,第4页,一、遗传算法概述,2,、生物进化理论和遗传学基本知识,(2),遗传学基本概念和术语,基因,(gene),：,染色体一个片段,染色体,(Chromosome),：,问题中个体某种字符串形式编码表示,种群,(Population),：,个体集合,该集合内个体数称为种群大小,基因型,(genetype),：,基因组合模型，染色体内部表现,表现型,(phenotype),：,染色体决定性状外部表现,1 1 1,1,1 1 1,1 1 1,0,1 1 1,个体 染色体,9 -1001,遗传算法GA专题知识专家讲座,第5页,一、遗传算法概述,2,、生物进化理论和遗传学基本知识,(2),遗传学基本概念和术语,进化,(evolution),：,个体逐步适应生存环境，不停改良品质过程,适应度,(fitness),：,反应个体性能一个数量值,编码,(coding),：,从表现型到基因型映射,解码,(decoding),：,从基因型到表现性映射,适应度函数,(fitness function):,问题中全体个体与其适应度之间一个对应关系,普通是一个实值函数。该函数就是遗传算法中指导搜索评价函数。,遗传算法GA专题知识专家讲座,第6页,1,选择,-,复制,(selection-reproduction),二、遗传算法基本操作,选择,-,复制指就是以一定概率从种群中选择若干个体并进行复制操作。,轮盘赌选择（,roulette wheel selection,）,随机遍历抽样（,stochastic universal selection,）,局部选择（,local selection,）,截断选择（,truncation selection,）,锦标赛选择（,tournament selection,）,选择概率,P(x,i,),计算公式为,:,惯用选择,-,复制方法：,按百分比适应,度分配方法,遗传算法GA专题知识专家讲座,第7页,1,选择,-,复制,(selection-reproduction),二、遗传算法基本操作,例：轮盘赌选择,解,(1),计算选择概率和累计概率,个体,染色体,适应度,选择概率,累计概率,1,0001100000,8,0.086957,0.086957,2,0101111001,5,0.054348,0.141304,3,0000000101,2,0.021739,0.163043,4,1001110100,10,0.108696,0.271739,5,1010101010,7,0.076087,0.347826,6,1110010110,12,0.130435,0.478261,7,1001011011,5,0.054348,0.532609,8,1100000001,19,0.206522,0.739130,9,1001110100,10,0.108696,0.847826,10,0001010011,14,0.152174,1.000000,遗传算法GA专题知识专家讲座,第8页,1,选择,-,复制,(selection-reproduction),二、遗传算法基本操作,个体,染色体,适应度,选择概率,累计概率,1,0001100000,8,0.086957,0.086957,2,0101111001,5,0.054348,0.141304,3,0000000101,2,0.021739,0.163043,4,1001110100,10,0.108696,0.271739,5,1010101010,7,0.076087,0.347826,6,1110010110,12,0.130435,0.478261,7,1001011011,5,0.054348,0.532609,8,1100000001,19,0.206522,0.739130,9,1001110100,10,0.108696,0.847826,10,0001010011,14,0.152174,1.000000,复制操作能从旧种群中选择出优异者，但不能创造新染色体！,(2),在,0-1,之间产生一个随机数,0.407893 6,0.070221 1,0.545929 8,0.784567 9,0.446930 6,0.291198 5,0.716340 8,0.271901 5,0.371435 6,0.854641 10,淘汰,遗传算法GA专题知识专家讲座,第9页,2,交叉,(crossover),基因重组,二、遗传算法基本操作,交叉就是交换两个染色体一些位上基因。,s,1,=01000101,s,2,=10011011,能够看做是原染色体,s,1,和,s,2,子代染色体,例：设染色体,s,1,=01001011,s,2,=10010101,交换其后,4,位基因,即,单点交叉,遗传算法GA专题知识专家讲座,第10页,2,交叉,(crossover),基因重组,二、遗传算法基本操作,其它惯用交叉方法：,多点交叉（,multiple-point crossover,）,均匀交叉（,uniform crossover,）,部分匹配交叉（,Partially Matched Crossover,）,次序交叉（,Ordered Crossover,）,循环交叉（,Cycle Crossover,）,交叉模拟了生物进化过程中繁殖现象，经过两个染色体交换组合，来产生新优良品种！,遗传算法GA专题知识专家讲座,第11页,3,变异,(mutation),变异就是改变染色体某个,(,些,),位上基因。,比如，设染色体,s,=11001101,，将其第三位上,0,变为,1,即,s,=11,0,01101,11,1,01101=,s,。,s,也能够看做是原染色体,s,子代染色体,变异运算用来模拟生物在自然遗传环境中因为各种偶然原因引发基因突变。,若只有选择和交叉、而没有变异，则无法在初始基因组合以外空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解质量,!,二、遗传算法基本操作,遗传算法GA专题知识专家讲座,第12页,三、遗传算法原理,标准遗传算法流程框图,遗传算子,适者生存,种群繁殖,关键,遗传算法GA专题知识专家讲座,第13页,三、遗传算法原理,算法中一些控制参数：,种群规模,N,：,最大迭代次数,T,：,交叉率,(crossover rate),：,参加交叉运算染色体个数占全体染色体总数百分比，记为,P,c,取值范围普通为,0.4,0.99,。,变异率,(mutation rate),：,发生变异,基因位数所占全体染色体基因总位数,百分比，记为,P,m,取值范围普通为,0.0001,0.1,。,遗传算法GA专题知识专家讲座,第14页,三、遗传算法原理,标准遗传算法,(Standard genetic algorithm,SGA),Step1,在搜索空间,U,上定义一个适应度函数,f,(x),，给定种群规模,N,，交叉率,P,c,和变异率,P,m,，迭代次数,T,；,Step2,随机产生,U,上,N,个个体,s,1,s,2,s,N,，组成初始种群,S,=,s,1,s,2,s,N,，置迭代计数器,t,=1,；,Step3,计算,S,中每个个体适应度,f,(x),；,Step4,若终止条件满足，则取,S,中适应度最大个体作为所求结果，算法结束。不然，转,Step5,；,遗传算法GA专题知识专家讲座,第15页,Step5,按选择概率,P(x,i,),所决定选中机会，每次从,S,中随机选定,1,个个体并将其复制，共做,N,次，然后将复制所得,N,个染色体组成群体,S,1,；,Step6,按交叉率,P,c,所决定参加交叉染色体数,c,，从,S,1,中随机确定,c,个染色体，配对进行交叉操作，并用产生新染色体代替原染色体，得群体,S,2,；,Step7,按变异率,P,m,所决定变异次数,m,，从,S,2,中随机确定,m,个染色体，分别进行变异操作，并用产生新染色体代替原染色体，得群体,S,3,；,Step8,将群体,S,3,作为新一代种群，即用,S,3,代替,S,，,t=t+1,，转,Step3,。,三、遗传算法原理,标准遗传算法,(Standard genetic algorithm,SGA),遗传算法GA专题知识专家讲座,第16页,四、遗传算法应用,1,、遗传算法应用领域,（,1,）组合优化 （,2,）函数优化,（,3,）自动控制 （,4,）生产调度,（,5,）图像处理 （,6,）机器学习,（,7,）人工生命 （,8,）数据挖掘,遗传算法GA专题知识专家讲座,第17页,2,、遗传算法应用举例,四、遗传算法应用,例：,求以下一元函数最大值,：,x-1,2,，求解结果准确到,6,位小数。,遗传算法GA专题知识专家讲座,第18页,四、遗传算法应用,用微分法求解：,即：,解有没有穷多个,(i=1,2,及,i=-1,-2,),是一个靠近于,0,实数递减序列,当,i,为奇数时,x,i,对应局部极大值点，,i,为偶数时,x,i,对应局部极小值,x,19,即为区间,-1,2,内最大值点,此时，函数最大值,f(x,19,）比,f(1.85)=3.85,稍大,遗传算法GA专题知识专家讲座,第19页,四、遗传算法应用,用遗传算法求解：,分析：,因为区间长度为,3,，求解结果准确到,6,位小数，所以可将自变量定义区间划分为,310,6,等份。又因为,2,21,310,6,2,22,，所以本例二进制编码长度最少需要,22,位，编码过程实质上是将区间,-1,，,2,内对应实数值转化为一个二进制串（,b,21,b,20,b,0,）。,求解过程：,(1),编码,表现型：,x,基因型：二进制编码，串长,22,位,遗传算法GA专题知识专家讲座,第20页,四、遗传算法应用,(2),生成初始种群,用遗传算法求解：,方式：随机生成长度为,22,二进制制串,数量：种群大小,(,规模,),，如,30,，,50,，,1111010011100001011000,1100110011101010101110,1010100011110010000100,1011110010011100111001,0001100101001100000011,0000011010010000000000,遗传算法GA专题知识专家讲座,第21页,四、遗传算法应用,(3),计算适应度,用遗传算法求解：,不一样问题有不一样适应度计算方法，本例直接用目标函数作为适应度函数。,计算,x,函数值,(,适应度,),：,将某个个体转化为,-1,2,区间实数：,s=x=0.637197,(4),遗传操作,选择：轮盘赌选择法,交叉：单点交叉,变异：小概率变异,遗传算法GA专题知识专家讲座,第22页,四、遗传算法应用,用遗传算法求解：,(5),模拟结果,设置参数：,种群大小,50,交叉概率,0.75,变异概率,0.05,最大代数,200,得到最正确个体：,smax=,xmax=1.8506,f(x,max,)=3.8503,迭代数,自变量,适应度,1,1.4495,3.4494,9,1.8395,3.7412,17,1.8512,3.8499,30,1.8505,3.8503,50,1.8506,3.8503,80,1.8506,3.8503,120,1.8506,3.8503,200,1.8506,3.8503,遗传算法GA专题知识专家讲座,第23页,小结,1,、遗传算法优点：,搜索过程不直接作用在变量上，而是作用在被编码个体上；,搜索过程是迭代过程，含有并行性；,利用概率转移规则，可在一个不确定空间上寻优；,不是从一点出发沿一条线搜索，而是在整个空间上搜索，从而找到全局最优解；,对搜索空间无任何特殊要求（连通，凸性）；,容错能力强。,2,、遗传算法存在问题：,编码问题：编码选择不妥使,GA,极难收敛到最优解；,早熟收敛：群体过早失去多样性而收敛到局部最优解；,进化时间长：进化过程中产生大量数据，计算大、时间长；,参数选择问题：当前参数选择是依据经验来确定，缺乏理论依据。,遗传算法GA专题知识专家讲座,第24页,改变,GA,组成成份（编码、适应度函数）；,采取动态自适应技术（交叉率和变异率）,自适应,GA,；,采取非标准遗传操作算子；,结合其它技术，生成混合,GA,；,并行,GA,、小生境遗传算法等。,小结,3,、遗传算法改进方法：,遗传算法GA专题知识专家讲座,第25页,Thank you,！,遗传算法GA专题知识专家讲座,第26页,二进制与十进制之间转换,第二步,对应区间,-1,2,内实数,第一步 将二进制串转换为十进制数,遗传算法GA专题知识专家讲座,第27页,