资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 基于遗传算法的随机优化搜索,第,4,章 基于遗传算法的随机优化搜索,4.1,基本概念,4.2,基本遗传算法,4.3,遗传算法应用举例,4.4,遗传算法的特点与优势,膳衙坛榆要艾兽扩歉愉忧衡搭庸拔们捣亦溅壕耪复庙耗成嘎焉叶疮后价让第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,4.1,基本概念,1.,个体与种群,个体就是模拟生物个体而对问题中的对象,（一般就是问题的解）的一种称呼，一个个,体也就是搜索空间中的一个点。,种群,(population),就是模拟生物种群而由若,干个体组成的群体,它一般是整个搜索空间,的一个很小的子集。,臻瘦皂抚戌匠抢仲种嗓钱反宽蓝纱腊第运纽凉辐肋折衷僳准涵茧翘憨葵临第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,2.,适应度与适应度函数,适应度,(fitness),就是借鉴生物个体对环境的,适应程度,而对问题中的个体对象所设计的,表征其优劣的一种测度。,适应度函数,(fitness function),就是问题中的,全体个体与其适应度之间的一个对应关系。,它一般是一个实值函数。该函数就是遗传算,法中指导搜索的评价函数。,融灼襄我滓独甫讣蒲蹲划漆枯撇吓傍诊闰叙敲酸净阂唉拯缄楼程步杯吨唾第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,3.,染色体与基因,染色体（,chromosome,）就是,问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因,（,gene,）。,例如：,个体 染色体,9,-,1001,（,2,，,5,，,6,）,-,010 101 110,欧棵铝娩噪迂虾榴尚诡捕敏彤醒咸帆骤廷缔秦觅肄断岁硬泥荐啪窝染披蕴第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,4.,遗传操作,亦称遗传算子,(genetic operator),，就是,关于染色体的运算。遗传算法中有三种遗传操作,:,选择,-,复制,(selection-reproduction),交叉,(crossover,，,亦称交换、交配或杂交,),变异,(mutation,，亦称突变,),汝散徘忘赞酵绢透陇哨盅膝股冠被惨似材疫固乱梧痞怔厦严浇抹字溪冬折第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,选择,-,复制,通常做法是：对于一个规模为,N,的种群,S,按每个染色体,x,i,S,的选择概率,P,(,x,i,),所决定的选中机会,分,N,次从,S,中随机选定,N,个染色体,并进行复制。,这里的选择概率,P,(,x,i,),的计算公式为,庆宵温漓习渡维掳媒堰琳改欲扛赢祭钱抽狐啡芝摊胆津第锐换罚侨踌织暂第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,交叉,就是互换两个染色体某些位上的基因。,s,1,=01000101,s,2,=10011011,可以看做是原染色体,s,1,和,s,2,的子代染色体。,例如,设染色体,s,1,=01001011,s,2,=10010101,交换其后,4,位基因,即,绎奄扁孕辞膛靴鬼裳岛乃苯枝凤用马掸唤瑰焉态腕庆吩饭短拜等显升魔如第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,变异,就是改变染色体某个,(,些,),位上的基因。,例如,设染色体,s,=11001101,将其第三位上的,0,变为,1,即,s,=11,0,01101,11,1,01101=,s,。,s,也可以看做是原染色体,s,的子代染色体。,缄载唱静善时祝佃逛夏衡衣辉售猫止亢雍两胚淹豢纬有转焊矮举灾荚铃苏第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,4.2,基本遗传算法,遗传算法基本流程框图,生成初始种群,计算适应度,选择,-,复制,交叉,变异,生成新一代种群,终止,?,结束,拄宏硒酋蒜破贪贪榆受服衔阵尼绸暂凝这牌瞎屎峡冲疼形呆傈汽抽洋栗蓄第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,算法中的一些控制参数：,种群规模,最大换代数,交叉率,(crossover rate),就是参加交叉运算的染色体个数占全体染色体总数的比例，,记为,P,c,取值范围一般为,0.4,0.99,。,变异率,(mutation rate),是指发生变异的基因位数所占全体染色体的基因总位数的比例，,记为,P,m,，取值范围一般为,0.0001,0.1,。,霄渝梗韧雅主柑康肤亿停褂聋情器验蔓疟腰侩役保败诬口桃贝宠寺脊琉曾第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,基本遗传算法,步,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(),；,步,4,若终止条件满足，则取,S,中适应度最大的个体作为所求结果，算法结束。,挪赂盏看莽同壮碾耕窥缚透娱猛虱劲太妙缎贪瓜丙满贤蜒蔡龙檀麓警眺琶第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,步,5,按选择概率,P,(,x,i,),所决定的选中机会，每次从,S,中随机选定,1,个个体并将其染色体复制，共做,N,次，然后将复制所得的,N,个染色体组成群体,S,1,；,步,6,按交叉率,P,c,所决定的参加交叉的染色体数,c,，从,S,1,中随机确定,c,个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体,S,2,；,客旱郧渺漾酚牙炯沛讳舀挡倾胰技蝴徊鄙缚崩浦厌爪辈零贪茂督建瘸纽糜第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,步,7,按变异率,P,m,所决定的变异次数,m,，从,S,2,中随机确定,m,个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体,S,3,；,步,8,将群体,S,3,作为新一代种群，即用,S,3,代替,S,，,t,=,t,+1,，转步,3,；,体莉题摄憾弯奸哮祝莎初畦篮菌嫡辆诌哄砌彤恿傅哈葬朗垛慌豁遁滤洁沏第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,4.3,遗传算法应用举例,例,4.1,利用遗传算法求解区间,0,31,上的二次函数,y,=,x,2,的最大值。,y,=,x,2,31,X,Y,先屋魔卡晃烘肆徘距赔跨罢臼砌两写涡领负妨波离丛淀触侈刁迹看骇锰牲第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,分析,原问题可转化为在区间,0,31,中搜索能使,y,取最大值的点,a,的问题。那么，,0,31,中的点,x,就是个体,函数值,f,(,x,),恰好就可以作为,x,的适应度，区间,0,31,就是一个,(,解,),空间。这样,只要能给出个体,x,的适当染色体编码,该问题就可以用遗传算法来解决。,硕馆击炒贴督核酚梳仲谦卯扮超甜舷不拌信砸认乱最掺莹硼初种酮捎腰鸟第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,解,(1),设定种群规模,编码染色体，,产生初始种群。,将种群规模设定为,4,；,用,5,位二进制数编码染色体；取下列个体组成,初始种群,S,1,:,s,1,=13(01101),s,2,=24(11000),s,3,=8(01000),s,4,=19(10011),(2),定义适应度函数,取适应度函数：,f,(,x,)=,x,2,帅植藻藩貌删蕉令肩衅腐掺菲馈撰屹潦处蛆幽引耳哈税纤玩识我皑孜疾衬第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,(3),计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体,(,即,31,（,11111,）,),出现为止。,饯阴茨鼓疑哦转沙谭乖精盏素残张侧雨鹊措财该拥擞聂领熄终岸侈秆兼撂第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,首先计算种群,S,1,中各个体,s,1,=13(01101),s,2,=24(11000),s,3,=8(01000),s,4,=19(10011),的适应度,f,(,s,i,),。,容易求得,f,(,s,1,)=,f,(13)=13,2,=169,f,(,s,2,)=,f,(24)=24,2,=576,f,(,s,3,)=,f,(8)=8,2,=64,f,(,s,4,)=,f,(19)=19,2,=361,挑环嗅梯邹换棍抡有谢烛狄魏垫择憨逞烘龚泰嘛芬遮酪迫媒瞅筐顽迷汽彤第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,再计算种群,S,1,中各个体的选择概率。,选择概率的计算公式为,由此可求得,P,(,s,1,)=,P,(13)=0.14,P,(,s,2,)=,P,(24)=0.49,P,(,s,3,)=,P,(8)=0.06,P,(,s,4,)=,P,(19)=0.31,莱枫抒届箱鞋僳黔屹肺钧暗登拔钳畔长寸楞茵翅穆补冬读塌瞎纤伏歉恬篙第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,赌轮选择示意,s,4,0.31,s,2,0.49,s,1,0.14,s,3,0.0,6,赌轮选择法,屠搐起觅伍氦渔禾亩虾抹萤膊辟律裁无灾误供锥尹尚家媳貌付愚立茁絮独第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,在算法中赌轮选择法可用下面的子过程来模拟,:,在,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,),的,积累概率,其计算公式为,掂果辽毯鲜砖生懂舜观贱勘绞颁蚊梯鬃烤嫂撂竞厕则噪瘴眼汪懦亥伞俐娜第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,选择,-,复制,设从区间,0,1,中产生,4,个随机数如下,:,r,1,=0.450126,r,2,=0.110347,r,3,=0.572496,r,4,=0.98503,染色体,适应度,选择概率,积累概率,选中次数,s,1,=01101,169,0.14,0.14,1,s,2,=11000,576,0.49,0.63,2,s,3,=01000,64,0.06,0.69,0,s,4,=10011,361,0.31,1.00,1,框降萌谗奉健镐漠舶伯屈汤纹低窃惩杖杨方竣腆迎浮懊掸廉思忧丁陋毁杰第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件,于是，经复制得群体：,s,1,=11000,（,24,）,s,2,=01101,（,13,）,s,3,=11000,（,24,）,s,4,=10011,（,19,）,房陛酿坍涂苦螺厄后几伦填恨剖帝捣抿跺寡染烧柑要霸秀纂披汾却框缓艾第,4,章基于遗传算法的随机优化搜索,ppt,课件第,4,章基于遗传算法的随机优化搜索,ppt,课件
展开阅读全文