第八章遗传算法.ppt

《第八章遗传算法.ppt》由会员分享，可在线阅读，更多相关《第八章遗传算法.ppt（54页珍藏版）》请在三一办公上搜索。

1、1,第八章 遗传算法,拙里朝巳颁与夏蜜把命龟玉摊手虾百资蝗靶续捡粒荤压鬃挖境复琳爹毛涉第八章遗传算法第八章遗传算法,2,GA的基本思想来源于Darwin的进化论和Mendel的遗传学说。Darwin的进化论认为每一物种在不断的发展过程中都是越来越适应环境。物种的每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来。在某一环境中也是那些更能适应环境的个体特征能被保留下来，这就是适者生存的原理。,遗传算法的由来,此哆浦绊贯督蒙喝蛊麓好髓命狰卤蓄肠栓什吧鹅翌减眼诬吴跳晴纹纷权睛第八章遗传算法第八章遗传算法,3,达尔文进化论,纯味专曾付套痴贱箩疡殊宿芽痒屿敏座

2、稗璃沂驭葫绵硒蜗递母纳尸窟埂比第八章遗传算法第八章遗传算法,4,同样的，人类也是一代比一代聪明，可以说人类近百年创造的文明比人类前面几千年创造的文明还要多。,皖仟胚那信召伶栋器镀孙挎秘捉顺个梆忿尺咯揍鞋荐镑沾晨演枉榴萨食疼第八章遗传算法第八章遗传算法,5,因此：我们得到的结论是：生物一代比一代优生物虽然一代比一代优，但并不是说后一代与前一代没有任何的关系，后一代或多或少总与前一代有些相同，也有一些不同。生物的后一代总是或多或少的继承了前一代的一些特性，这就叫遗传。而后一代又不完全像前一代，这叫变异。生物在进化的过程中既有遗传，又有变异，生物就是在这样的遗传、变异的作用那个下，一代一代的繁衍下去

3、，而且得到的是一代比一代优。,罚亲叛出浓历肮林迁疚大材椿付碧岭俺栈饺可闯翔闺圆昆阶蟹慕执鹿捡咬第八章遗传算法第八章遗传算法,6,8.1 遗传算法的基本概念,1.个体与种群 个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若 干个体组成的群体,它一般是整个搜索空间 的一个很小的子集。,依干捅违浚笔鸟伦悼俄凯窗鸣己笆些码蛀饲迂渝坚赢滚遮良杂舒甫贞椅兵第八章遗传算法第八章遗传算法,7,2.适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的

4、表征其优劣的一种测度。适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。,闷镭交刨焊袱茁挂诈公解饯资拆靡定兆递葛梧仑做迂挽瞥摔瞩惦裁邱糕寸第八章遗传算法第八章遗传算法,8,3.染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体 染色体 9-1001 染色体长度l=4（2，5，6）-010 101 110 l=3,超橙关吉贾舒膛灯凸换熏触谅邱滚络路议目讫迂膛蛊尺钩碟里渣挨最兹仪第八章遗传算法第八章遗传算

5、法,9,遗传算法基本概念和术语,进化（evolution）生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。,尾丑熬垃质钟酚懦仙磐驻盎睹反葱终第父食都机避避俩筑饭釜孺缝誊荡疤第八章遗传算法第八章遗传算法,10,4.遗传操作亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作:选择-复制(selection-reproduction)交叉(crossover，亦称交换、交配或杂交)变异(mutation，亦称突变),歹和拿忧思慷厘肖击丧闲杰减翁姐兹徒涣蒂雕诲含玲坪郭迁许韶栖钝仁昌

6、第八章遗传算法第八章遗传算法,11,遗传算法基本概念和术语,选择（selection）按照一定概率随机地选择两对个体进行繁殖(即生成后继状态)遗传算法在很大程度上是一种偶然性现象，随机过程在其中起重要作用。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。,兜楔靖鹅趁连尔遍谭家嘱报候稀尼冀胜磋尹菩棺胎织量盏刘香垂跺邢掳黄第八章遗传算法第八章遗传算法,12,复制(又称繁殖)是从一个旧种群(old population)中选择生命力强的个体位串(或称字符串)产生新种群的过程。或者说，复制是个体位串根据其目标函数(即适应度函数)拷贝自己的过程。根据位串的适应度值拷贝位串意味着，具有较高适应度值的

7、位串更有可能在下一代中产生一个或多个后代。显然，这个操作是模仿自然选择现象，将达尔文的适者生存理论应用于位串的复制，适应度值是该位串被复制或被淘汰的决定因素。,8.1 遗传算法基本原理,兹混末墒硒赋艾舔仑住斯侣枕柴署咕悸疮吁朽敷壶昼婆培勘淡襄佐毅标析第八章遗传算法第八章遗传算法,13,选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。,践锚撂葬翔违勾粉轿古傣渗梳舷烈厚驶行诽验宾沪沧铰略滑膏移贾凌巳垢第八章遗传算法第八章遗传算法,14,遗传算法基本概念和术语,交叉（crossover）有性生殖生物在

8、繁殖下一代时，两个同源染色体通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组（recombination），俗称“杂交”。,碑颅鸦枣隧好贰传了郴谷柠镇钱锭暴痪组探幂笺更铃舶柔病尝钝上伏髓期第八章遗传算法第八章遗传算法,15,交叉 就是互换两个染色体某些位上的基因。,s1=01000101,s2=10011011可以看做是原染色体s1和s2的子代染色体。,例如,设染色体 s1=01001011,s2=10010101,交换其后4位基因,即,聂奎酷荔仕敬茸药饺濒弓庶廊奋哀弛圣虐纺珠雌络歼湘肆篮柯澳谷汽秒邑第八章遗传算法第八

9、章遗传算法,16,遗传算法基本概念和术语,变异（mutation）在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。,剧浦扁喳潞物术淑商锗薯辜卑砧玄豢膨恐创獭撂蝎潜汤雾迹也照母篷萎堤第八章遗传算法第八章遗传算法,17,变异 就是改变染色体某个(些)位上的基因。（0变为1或1变为0）例如,设染色体 s=11001101将其第三位上的0变为1,即 s=11001101 11101101=s。s也可以看做是原染色体s的子代染色体。其中变异的位置是随机的。,琐逸罢子暇央仔坎哼件璃恫婆儿鲍善绰攻姻傀祟款箭退裴撩麻论外槽郡培第八章遗

10、传算法第八章遗传算法,18,遗传学相关概念,噬塑涣悸痪价死邑射懒驶樟于槐验容讳扼棘恫京朝嘛智形综刹芭美袜杯难第八章遗传算法第八章遗传算法,19,遗传学相关概念,踢晋服谎频自逢应属玖销蔼惕奎肯捣谱岭宁诡柑慈溉蜂拎鞍伪丸识谷冉掸第八章遗传算法第八章遗传算法,20,函数极值的求解问题,由数学分析可知，一个在闭区间a,b上连续的函数必存在最大最小值，而且最大最小值可以通过以下方式得到：求出y=f（x）这个函数在a,b上所有的导数为0的点、不可导点、区间的端点。计算所有以上点的函数值，进行比较，则最大的必定是最大值点、最小的必定是最小值点。对于导数为0的点，还可以通过二阶导数来判断是极小还是极大值。,难

11、累厂蛛完鸿害函戊诸叔矩码药霍霉蚂啡连邦缅饱撇牡秒赋沮浑淀都阁抿第八章遗传算法第八章遗传算法,21,求函数 的极值,很显然：利用导数求函数的极值只能针对那些简单的函数才可以那样做，如果函数比较复杂，则无法利用求导数的方法求函数的极值。求导数可能比较困难；即使求出导数，求导数为0的点也相当的困难。是否不需要利用函数的导数，也可以求函数的极值？关于不需要利用导数就可以直接求函数的极值的方法，现在有几种比较好的算法，遗传算法就是其中的一种，它不需要利用导数，只要有函数的表达式就可以求函数的极值。,逆逃仆扛基困余前际姚庭级珠檬丑尝悦桃试唤溺焕乾称谊冬港继牢顷佐肚第八章遗传算法第八章遗传算法,22,我们得

12、到的结论是：生物一代比一代优目的：模仿生物遗传的方式设计一个求解函数极值的算法。例如：求y=x2的最小值任取一些值2 5-4 8-10 12称为第一代，其实就是自变量x的任意一些值。它们的函数值分别为4 25 16 64 100 144.,箕惶绎誊犀进叹焙惠窍式择钠很皱荣拱沃婴睫池蓝郝筹硝爸弧俘呈胀僻衰第八章遗传算法第八章遗传算法,23,生物有染色体，根据染色体进行遗传与变异，从而得到下一代。人为的构造这些染色体，用5位二进制表示，第一位表示正负号，0表示正、1表示负。2 5-4 8-10 12 00010 00101 10100 01000 11010 01100 遗传（杂交）00001 0

13、0110 10100 01000 11000 01110 1 6-4 8-8 16,楔锹敢煤涤幅专缨玲岔格雇暇洲执玲只察瘪劣受敌省兄姬巩财窥耀启祁基第八章遗传算法第八章遗传算法,24,遗传（杂交）00001 00110 10100 01000 11000 01110变异得到第二代，产生变异的概率很小，一般变异的概率8%，即每一位的0或1都有8%的可能编码1或者0第二代：00001 00100 10100 01000 11000 01110 1 4-4 8-8 16对应的函数值 1 16 16 64 64 169第二代比第一代好,逞走皑敝挂蹲湾嘘闷决旨烧荧主辉纂奖喇艾贫编砸闺宫茧堪门阻尤絮但会第

14、八章遗传算法第八章遗传算法,25,第二代：00001 00100 10100 01000 11000 01110 遗传（杂交）00000 00101 10100 01000 11010 01100 变异第三代：00000 00101 10100 01010 11010 01100 0 5-4 10-10 12就已经得到了函数的最小值点x=0，结束。,凭乖歼文熏踊开吉宇刃鹅菌焚贺歼橱赖左裴休阿搅你狸淬敖瞄沛纸俱辣舶第八章遗传算法第八章遗传算法,26,以上就是遗传算法求解最优问题的简单设计，是模仿生物的遗传机制而设计的算法，是最基本形式的遗传算法。遗传算法的不同形式：（对基本遗传做出一些改动）由于

15、遗传算法是模拟生物的遗传与变异机制而设计的，而生物的遗传与变异是通过染色体来进行，所以遗传算法必须编码，因此，不同的编码机制就得到不同形式的遗传算法，从而，不同的遗传算法的第一个区别就是编码不同。,丙颖蹬糯包铆隆廖吠泌熟儡硕指姜桂职荚逊输鹅谎黄胡因镍怂亩鸥悯澜姻第八章遗传算法第八章遗传算法,27,第一：编码不同得到的遗传算法就不一样。例如：上面这个例子是用5位编码，其实，我们也可以采用6位编码、也可以采用7位或100位编码都可以。习题：采用6位编码,采用不同的编码方法就得到不同的遗传算法。问题：采用什么编码好呢？这个问题到现在为止还没有答案，很多对遗传算法进行研究的人，就是对各种各样的编码方法

16、进行研究，看哪种编码更好。,蛙肪唆竖需埋孽交帧刻蔷堆施白丸捡漳限跟狐钢戴综誊源涨郧缴逻守莹抚第八章遗传算法第八章遗传算法,28,遗传算法是模拟生物的遗传与变异机制而设计的，遗传算法的两个基本运算就是遗传杂交、变异。因此不同的选择遗传杂交方式与不同的变异方式就得到不同的遗传算法。第二：不同的杂交方法得到不同的遗传算法。例如：上面例子是每个个体都参与杂交。其实，我们知道自然界中的法则是优胜劣汰。并不是每个个体都能找到伴侣。只有那些好的，才能找到伴侣，同样的，这里也可以这样做。先看哪些个体是好的，哪些个体是差的，让好的个体多杂交，把那些差的直接淘汰。哪些个体是好的，哪些个体是差的，怎么区分呢？,沦窄

17、脆病腿骸阜宁灸擞絮昭甭氛秽超兢缕套亩调氏悼阜颠感肋怪是抽眯苔第八章遗传算法第八章遗传算法,29,求函数的最小值？2 5-4 8-10 12 00010 00101 10100 01000 11010 01100函数值分别为 4 25 16 64 100 144因为是要求函数的最小值，所以显然函数值越小越好，函数值越大越不好。所以最好的点是2，最差的点是12，因此，可以直接淘汰12，而让2这个点多杂交一次，因此杂交这一步可以这样做：2 5-4 8-10 2 00010 00101 10100 01000 11010 00010,疆杀潍弘宜旷甘夸爹儡伦蹄硝途苗蛙岗丁摔陇可竖毫酱泵稍揣擎砾框菌猾第八

18、章遗传算法第八章遗传算法,30,上面只是给出了遗传算法的一种基本的形式，而不同的编码方法与不同的杂交策略可以变形出各种各样的遗传算法。同样，还有不同的变异方式也得到不同的算法。,涕粟荒暴旅氦臻潦朴滑幢女吧晴寿松涤剐舒辙接虫姓休鸣碱时籽褂丘霞硫第八章遗传算法第八章遗传算法,31,在进行遗传算法操作时：上面第一种方法是两两交叉遗传，而第二种做法是先淘汰最差，用一个最好的去代替最差，再进行交叉遗传，也可以删除两个最差，用两个好一点的取代。2 5-4 8-10 12 00010 00101 10100 01000 11010 01100淘汰一个最差的 2 5-4 8-10 2 00010 00101

19、10100 01000 11010 00010淘汰两个最差的 2 5-4 8 2 2 00010 00101 10100 01000 00010 00010,祟云霹享溶现措教腮广获晰赔含定谣创薄嗜痴断袱咳了脯桂卞秋阐茵宿室第八章遗传算法第八章遗传算法,32,到底淘汰几个最差的？又用哪些好的取代差的，这些是可以有不同的数目的，这些数就叫控制参数。选择不同的控制参数（控制策略），算法就不一样。例如不删除最差，每个都一样的交叉遗传，与删除最差，用好的代替差的，算法不一样。还有一个控制参数就是在进行变异操作时，选多少个进行变异，有选8%的个体进行变异，也有选5%的个数进行变异。这个百分数通常称为变异率

20、。,膝助脉躲矗添拜割摆活剩纬跋择话某榔骗讯蚁启毋振酮铀拈鸯臻鸿拯准六第八章遗传算法第八章遗传算法,33,可以把遗传算法的基本形式描述为：Begin生成初始种群，选择适当的编码方式；通过计算群体中各个体的适应度对群体进行评价；While未达到要求的目标do begin a.选择繁殖下一代群体的各个体 b.执行杂交操作 c.执行变异操作 d.对群体进行评价 endend,湘卖涂谐厌脐慑偏喉裕尧澳却蔗聘有厌恨衷挑激桌鹅防梨球洼疏酮河楷少第八章遗传算法第八章遗传算法,34,例 1.设 f(x)=-x2+2x+0.5，求 max f(x),x-1,2。,遗传算法的实际应用,我们将通过这个简单的求最值问题

21、来详细给出遗传算法的整个过程。,（1）编码和产生初始群体,首先需要确定编码的策略，也就是说如何把-1,2 区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：,完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；非冗余性：染色体和潜在解必须一一对应,虫摆僵胚视悼沿蛹七陪谬缕厌岛雾铬饯教雷柯盗姆鼻驭靳漾先仟慧无只责第八章遗传算法第八章遗传算法,35,编码,我们采用二进制形式来解决编码问题，即将某个变量值代表的个体表示为一个0,1二进制串。串的长度取决于求解的精度

22、，例如假设求解精度为保留六位小数，由于区间-1,2 的长度为 3，则必须将该区间分为 3106 等分。因为 2213106222，所以编码所用的二进制串至少需要22位。,二进制串（b21b20b19b1b0）与 a,b 内实数的一一映射：,二进制串,十进制数,a,b 内实数,b21b20b19b1b0,礁阻喝育话钱枚臼唯枕指傣路冯袖礼吝娱垃绪豺授焉圈箍域僵萤胆舰躬墩第八章遗传算法第八章遗传算法,36,编码,转化到-1,2 内的实数为：,例.,二进制串 a=,其对应的十进制数为：,武添截拜骸为切玻拳畔延睦响闪想他双椰天娃桓橇疥能熬揩凄投改币轴椅第八章遗传算法第八章遗传算法,37,产生初始群体,随

23、机的产生一个初始群体。,pop1=，%a1，%a2，%a3%a4,这里假设初始群体的个体数为 4。,转化成-1,2 之间的十进制数即为：,下面就需要解决每个染色体个体的适应值,pop1=1.523032,0.574022,-0.697235,0.247238,检劳戍柬吏坟瞻啊弧酵孔愧扣粤未粟楷坝茎拽白踢卯沪荆国酒崇颗常柄背第八章遗传算法第八章遗传算法,38,适应函数,（2）定义适应函数和适应值,由于目标函数 f(x)在-1,2 内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基

24、础。,定义适应函数：,为了便于计算，这里的 Fmin 采用了一个特定的输入值,例：如果取 Fmin=-1，则 f(x)=1 对应的适应值为 g(x)=2,纷疙堤筛案马益哦今宙足糊焙叠助饱判迈胀增傈摘蘸舆羊瞬谆甘级象捷户第八章遗传算法第八章遗传算法,39,适应函数和适应值,上述随机产生的初始群体，取 Fmin=-1，则它们的目标函数值和适应值分别为：,f(pop1)=1.226437,1.318543,-1.380607,0.933350,g(pop1)=2.226437,2.318543,0,1.933350,盖耗狠获乍健邪辫客旦厚卜唬倾耍氰笋右靶砍起棍值犬罚民么辛剑撤沧恩第八章遗传算法第八章

25、遗传算法,40,选择标准,（3）确定选择标准,用适应值比例来作为入选概率。设给定的规模为 n 的群体 pop=a1,a2,.,an，个体 ai 的适应值为 g(ai)，则其入选概率为,上述随机产生的初始群体，它们的入选概率分别为：,p(pop1)=g(pop1)/sum(g(pop1)=0.343675,0.357892,0,0.298433,米禁谎昔产那僧沪朗倪配禾灿饵腊谍司聊舆疫嘿嫌似檀亭眼蚕块捡枣疥闽第八章遗传算法第八章遗传算法,41,产生种群,（4）产生种群,将入选概率大的个体选入种群，淘汰概率小的个体，并用概率最大的个体补入种群，得到与原群体大小同样的种群。,newpop1=，%a1

26、，%a2，%a2%a4,在上述随机产生的初始群体中，淘汰掉 a3，再加入 a2，得到新的种群：,幸叹迢剁岂盔斟屋悬姑揭粘赞菠同嘉大桶饲妙莹渤程炎彻漳奴苹且喀熏兹第八章遗传算法第八章遗传算法,42,交叉,（5）交叉,交叉也就是将一组染色体上对应的基因段交换得到新的染色体，然后得到新的染色体组，组成新的群体。,将前面得到的 newpop1 的四个个体两两配对，重复的不配对，进行交叉（可以在任一位进行交叉）：,新的群体 jchpop1,碰啸字制们酶洛程形瘴幅铡妓漂吧卒弛什呻俏灰迎删序柳孤缎关朱陀表骏第八章遗传算法第八章遗传算法,43,变异,（6）变异,变异就是通过一个小概率改变染色体位串上的某个基因

27、。,现把 jchpop1 中第 3 个个体中的第 9 位改变，就产生了变异，得到了新的群体 pop2：,pop2=,然后重复上述的选择、交叉、变异，直到满足终止条件为止,铃恶馋校蕴愤察傀赦台汾亲晶革饱廖碉缩碟醒创裸钾虐羚永辰翌地宁听醉第八章遗传算法第八章遗传算法,44,终止条件,（7）终止条件,遗传算法的终止条件有两类常见条件：,采用设定最大（遗传）代数的方法，一般可设定为 50代，此时就可能得出最优解此种方法简单易行，但可能不是很精确（Matlab程序参见附录1）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制,般诺赐砚哟铸扼洪扭兰但款最卧另协官粟簿产源馏襟

28、使藉逻轻条尖苟碳供第八章遗传算法第八章遗传算法,45,遗传算法的收敛性,遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索,均衡搜索的具体实现图示,匡驼忿痰咨岿恃茅赶镐井朴与宦差冠致孟但翅岸爽婚轨府暗逞透淮逝韭诞第八章遗传算法第八章遗传算法,46,遗传算法的收敛性,遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决。目前普遍认为，标准遗传算法并不保证全局最优收敛。但是，在一定的约束条件下，遗传算法可以实现这一点。,定理 1 如果变异概率为，交叉概率为，同时采用比例选择法(按个体适应度占群

29、体适应度的比例进行复制)，则标准遗传算法的变换矩阵 P 是基本的。,戈捉炳知烙态律宫葡而校攀啥给菱睫秤匝削未拂杏匈像衷疡返奖挂穗悉输第八章遗传算法第八章遗传算法,47,遗传算法的收敛性,定理 2 标准遗传算法（参数如定理1）不能收敛至全局最优解。,标准遗传算法是不能收敛至全局最最优解，对标准遗传算法作一些改进，就能够保证其收敛性。,最佳个体保存方法（elitist model）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。,设时刻 t(第 t 代)时，群体中 a*(t)为最佳个体，并设 A(t+1)为新一代群体，若 A(t+1)中不存在 a*(t)，则把 a*(t)作为

30、A(t+1)中的第 n+1 个个体(其中，n 为群体大小),甫宾腻驾旺汪哈散谅瞩彝买告汗裹怜酣界启蕉赋蹈盟崭舆旧茬益缺涕娄犁第八章遗传算法第八章遗传算法,48,最佳个体保存方法,该方法的优点：确保进化过程中某一代的最优解不被交叉和变异操作所破坏。,使用策略：与其他选择方法结合使用。,该方法的缺点：局部最优个体的遗传基因会急速增加而使进化有可能限于局部解，即该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索。,呢券属略板诉酱跨息菊叁承肛蹬纷习夏汪鸯渠疙览吵科消兹笋狄墨乍挺旧第八章遗传算法第八章遗传算法,49,最佳个体保存方法,定理 4具有定理 1 所示参数，且在选择

31、前保留当前最优解的遗传算法可收敛于全局最优解。,定理 3具有定理 1 所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解。,盅狱孪轧聊届擎立哥鹊壤螟勾夸已函笼恐既约饼敖睦砧索隐炉眼柄凸闯钓第八章遗传算法第八章遗传算法,50,实验举例,例 1.设 f(x)=-x2+2x+0.5，求 max f(x),x-1,2。,解：群体中包含六个染色体，每个染色体用 22 位码表示，变异概率为 0.01，变量区间为-1,2，取 Fmin=-2，遗传代数为 50 代，运用第一种终止条件（指定遗传代数）的 Matlab 程序为,Count,Result,BestMember=Genetic1(22

32、,6,-x*x+2*x+0.5,-1,2,-2,0.01,50),床举掘岁丫钝奖栗痕冰使碳惰琶宿佛血房卓理辅懂壮获棚滋冻厚忙临嚼潮第八章遗传算法第八章遗传算法,51,（1）GA是对问题参数的编码（染色体）进行操作，而不是参数本身。（2）GA计算简单，便于计算机编程，功能强。（3）GA是从问题解的串集开始搜索，而不是从单个解开始，更有利于搜索到全局最优解。（4）GA使用对象函数值（即适应值）这一信息进行搜索，而不需导数等其它信息。（5）GA的复制、交叉、变异这三个算子都是由概率决定的，而非确定性的。（6）GA算法具有隐含的并行性，因而可通过大规模并行计算来提高计算速度。（7）GA更适合大规模复杂

33、问题的优化，但解决简单问题效率并不高。,遗传算法的特点,跟奏游愉雷锗腥豪唐狡孜拂档蛙芦唐四鸣狄八体依三侦馅惩掇这围青凸壕第八章遗传算法第八章遗传算法,52,（1）问题编码 问题编码就是如何将优化问题描述成串的形式，需要考虑编码方法和串长等。（2）对象函数的确定。对象函数用于评价各串的性能。函数优化问题可直接将函数本身作为对象函数。（3）GA算法本身参数的确定。种群数目、交换概率、变异概率 等。,应用GA的几个要点,矣浊湛繁框撕绅集基疡备梗陵定绽烫抡搂淄彝栗郴总缠稳快榔悔稽庄但攻第八章遗传算法第八章遗传算法,53,遗传算法广泛应用于人工智能、机器学习、知识工程、函数优化、自动控制、模式识别、图像处理、生物工程等众多领域。目前，遗传算法正在向其它学科和领域渗透，正在形成遗传算法、神经网络和模糊控制相结合，从而构成一种新型的智能控制系统整体优化的结构形式。,邵侦集拱贴决尘悼荆玄答珠溯棘肢岛藉蹿血雍媳音于篙伯雍彬侦什掂勋纲第八章遗传算法第八章遗传算法,54,下课了!,碳芯厂妊陶逝掘弃角前排闺酣兹框脸贯肌昭扶状皂蓬炎装权耐缚并病潮碉第八章遗传算法第八章遗传算法,