《第八章遗传算法名师编辑PPT课件》由会员分享，可在线阅读，更多相关《第八章遗传算法名师编辑PPT课件（37页珍藏版）》请在金锄头文库上搜索。
1、机械优化设计机械优化设计太原科技大学张学良琶捌贤堑妇迅楷滥瘪婴纵塞黍浙儒光子巾忧徐射濒搓至桂梭娇买韦往鹏认第八章遗传算法第八章遗传算法第八章 遗传算法自自然然界界充充满满了了奇奇迹迹与与生生机机，而而生生命命的的繁繁衍衍更更是是奇奇妙妙无无穷穷。人人类类之之所所以以能能够够向向其其自自身身的的演演化化学学习习以以增增强强决决策策问问题题的的能能力力，是是因因为为自自然然演演化化过过程程本本质质就就是是一一个个学学习习与与优优化化的的过过程程。这这一一优优化化过过程程的的目目的的是是使使生生命命体体达达到到适适应应环环境境的的最最佳结构与效果。佳结构与效果。8.1遗传算法的起源遗传算法的起源遗传
2、算法的遗传算法的生物学基础生物学基础抄喉腺蜜波篮慑因迂妈甭巨刺柴黍虹秤宵陌戚晶懈猿福敷兵硫铃乌汤跑植第八章遗传算法第八章遗传算法曾经主宰地球的恐龙由于庞大的身躯跟曾经主宰地球的恐龙由于庞大的身躯跟不上环境的变迁而灭绝；长颈鹿为了觅食不上环境的变迁而灭绝；长颈鹿为了觅食而长长了脖子；老鼠的机敏是为了生存而而长长了脖子；老鼠的机敏是为了生存而挣扎的结果；青蛙的存活则得益于其两栖挣扎的结果；青蛙的存活则得益于其两栖式左右逢源的能力；人类解放出有力的双式左右逢源的能力；人类解放出有力的双手，得益于类人猿求生的努力，而正是这手，得益于类人猿求生的努力，而正是这一对与其它动物的不同的、不再用于进行一对与其
3、它动物的不同的、不再用于进行行走的双手，使人类成了这个世界的主宰。行走的双手，使人类成了这个世界的主宰。自然演化遵循着一种奇妙的规律，这就是自然演化遵循着一种奇妙的规律，这就是达尔文发现的自然演化规律：物竟天择，达尔文发现的自然演化规律：物竟天择，适者生存。适者生存。修东蒸藉表奎弄王工穗欣级肠拂碌村窜梁鲍郴目盂峦愤翼承瞻咎进绑松活第八章遗传算法第八章遗传算法 自自然然界界特特别别是是生生物物界界神神奇奇的的进进化化过过程程是是一一个个不不断断优优化化的的过过程程。近近代代基基因因遗遗传传工工程程的的研研究究成成果果正正在在不不断断揭揭示示着着这这一一过过程程的的本本质质机机理理。人人们们为为什
4、什么么不不能能师师法法大大自自然然，把把生生物物学学进进化化的的一一些些基基本本概概念念和和机机理理引引伸伸到到工工程程问问题题的的研研究究中中来来呢呢？1975年年，Holland提提出出了了建建立立基基因因遗遗传传优优化化的的计计算算机机仿仿真真遗遗传传算算法法的的基基本本概概念念和和技技巧巧，其其本本意意是是在在人人工工适适应应系系统中设计的一种基于自然演化原理搜索机制。统中设计的一种基于自然演化原理搜索机制。踢阴侍噎制合菱乌乙陛促嚣糊诈炒签抱造燃扒整耪则败肚鞍寇酞遇舌年辩第八章遗传算法第八章遗传算法 遗遗传传算算法法是是基基于于自自然然选选择择和和遗遗传传机机制制，在在计计算算机机上上
5、模模拟拟自自然然界界生生物物进进化化过过程程与与机机制制的的寻寻优优搜搜索索仿仿生生智智能能算算法法，它它模模拟拟的的机机制制是是一一切切生生命命与与智智能能的的产产生生与与进进化化过过程程。它它模模拟拟达达尔尔文文的的自自然然演演化化规规律律的的原原理理激激励励好好的的结结构构，模模拟拟孟孟德德尔尔的的遗遗传传变变异异理理论论在在迭迭代代过过程程中中保保持持已已有有的的结结构构，同同时时寻寻找找更更好好的的结结构构。它它是是一类自组织、自适应人工智能技术。一类自组织、自适应人工智能技术。斜履宵子能摊捕逼志脏飞饲卷糟世盈造湾垒殉朗社赵边曳檀颐拍楼褒布圆第八章遗传算法第八章遗传算法自自然然界界的
6、的生生物物从从其其父父代代继继承承特特征征或或性性状状，这这种种生生命命现现象象称称之之为为遗遗传传（HeredityHeredity），研研究究这这种种生生命命现现象象与与机机理理的的科科学学即即为为遗遗传传学学（GeneticsGenetics）。由由于于有有遗遗传传作作用用，自自然然界界才才有有稳稳定定的的物物种种，人人们们种种瓜瓜得得瓜瓜，种种豆豆得得豆豆，之之所所以以鱼鱼至至今今还还仍仍然然会会在在水水中中遨遨游游，鸟鸟仍仍然然在在天天空空中中飞飞翔翔都都是是这这个个缘缘由由。自自然然界界之之所所以以稳稳定定有有序序，持持久久永永恒恒，而而非非天天翻翻地地覆覆，恐恐怕怕也得益于这一点
7、。也得益于这一点。卧构镁捉落虹嚣渺胃讶揉辉好耗锐惮盘澳茧吩浩铜措且频疙孪屁衡矮糙粟第八章遗传算法第八章遗传算法构成生物的基本结构与功能单位是细胞构成生物的基本结构与功能单位是细胞(Cell). (Cell). 细胞中的一种微小的丝状化合物称细胞中的一种微小的丝状化合物称为染色体（为染色体（ChromosomeChromosome），生物的所有遗传），生物的所有遗传信息都包含在这个复杂而又微小的染色体中。信息都包含在这个复杂而又微小的染色体中。遗传信息是由基因（遗传信息是由基因（GeneGene）组成的，生物的）组成的，生物的各种性状由其相应的基因所决定，基因是遗各种性状由其相应的基因所决定，基
8、因是遗传的基本单位。细胞通过分裂具有自我复制传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂过程中，其遗传基因也的能力，在细胞分裂过程中，其遗传基因也同时被复制到下一代，从而其性状也被下一同时被复制到下一代，从而其性状也被下一代所继承。代所继承。黔缚斋命不兜瞻了箱星煽胜喻篡熄棉态泣坪撬谭伪铰旦涸搅匣指虏立最俘第八章遗传算法第八章遗传算法遗遗传传学学认认为为，遗遗传传是是作作为为一一种种指指令令遗遗传传码码封封装装在在每每个个细细胞胞中中，并并以以基基因因的的形形式式包包含含在在染染色色体体中中，每每个个基基因因有有其其特特殊殊的的位位置置并并控控制制某某个个特特殊殊的的性性质质，每每个
9、个基基因因产产生生的的个个体体对对环环境境有有一一定定的的适适应应性性。细细胞胞在在分分裂裂时时，遗遗传传物物质质DNA通通过过复复制制（Reproduction）而而转转移移到到新新产产生生的的细细胞胞中中，新新细细胞胞就就继继承承了了旧旧细细胞胞的的基基因因。这这正正是是子子代代与与父父代代相相象象的的主主要要原原因因所所在在。另另外外，在在进进行行细细胞胞复复制制时时，虽虽然然概概率率很很小小，但但也也可可能能产产生生某某些些复复制制差差错错，从从而而使使DNA中中的的某某些些基基因因发发生生变变异异（Mutation），产产生生出出新新的的染染色色体体。这这正正是是为为什什么么子子代代
10、与与父父代代相相象象，但但又又不不是是完完全全一一样样的的缘缘故故。否否则则，就就不不叫叫遗遗传传，恐恐怕怕是是克克隆隆（Clone）了了。这这些些新新的的染染色色体体表表现现出出新新的的性性状状。如如此此这这般般，遗遗传传基基因因或或染染色色体体在在遗遗传传过过程程中中由由于于各种各样的原因而发生变化。各种各样的原因而发生变化。闲撵忍有德似葡艘危痉彤胰督呐阎吗标匡伊秒暑干侵她悯果您罐扫山中手第八章遗传算法第八章遗传算法生生物物在在其其延延续续生生存存的的过过程程中中，逐逐渐渐适适应应于于其其生生存存环环境境，使使得得其其品品质质不不断断得得到到改改良良，这这种种生生命命现现象象称称为为进进化
11、化（Evolution）。生生物物的的进进化化是是以以集集团团的的形形式式共共同同进进行行的的，这这样样的的团团体体称称为为种种群群或或群群体体（Population），组组成成种种群群的的单单个个生生物物称称为为个个体体（Individual）。每每一一个个生生物物个个体体对对其其生生存存环环境境都都有有不不同同的的适适应应能能力力，这这种种能能力力称称为为个个体体的的适适应应度度（Fitness）。达达尔尔文文的的自自然然选选择择学学说说认认为为，通通过过不不同同生生物物间间的的交交配配以以及及其其他他一一些些原原因因，生生物物的的基基因因有有可可能能发发生生变变异异而而生生成成一一种种新
12、新的的生生物物基基因因，这这部部分分变变异异了了的的基基因因也也将将遗遗传传到到下下一一代代。尽尽管管这这种种变变化化的的概概率率可可以以预预测测，但但具具体体哪哪一一个个个个体体发发生生变变化化却却是是偶偶然然的。的。羽倦打松胖气丈沿纫峪枷僵配烽瞬寻遁沛隔役鬼龙拷偷功松孺蛊墓古缩土第八章遗传算法第八章遗传算法这这种种新新的的基基因因根根据据其其与与环环境境的的适适应应程程度度决决定定其其增增殖殖能能力力，有有利利于于生生存存环环境境的的基基因因逐逐渐渐增增多多，而而不不利利于于生生存存环环境境的的基基因因逐逐渐渐减减少少。借借助助于于这这种种自自然然的的选选择择机机制制，物物种种将将逐逐渐渐
13、地地向向适适应应于于生生存存环环境境的的方方向向进进化化，从从而而产产生生出出越越来来越越适适应应环环境境的的物物种种。不不适适应应环环境境的的物物种种，也也会会逐逐渐渐灭灭绝绝，销销声声匿匿迹迹。就就是是“物物竟竟天天择择，适者生存适者生存”的原理。的原理。颓位萤垮屎绦材谭作跑钠魄凯跟晌湛敞更攀蒋塌侠辨疆啤裤开牙崖予胰潮第八章遗传算法第八章遗传算法人们对遗传与进化的特征已形成了如下的共识：人们对遗传与进化的特征已形成了如下的共识：1染染色色体体中中包包含含了了生生物物的的所所有有遗遗传传信信息息（基基因因），染染色色体体决决定定个个体体的的生生物物特特征征（表表现现型型），而而表表现现型型决
14、定个体对环境的适应度。决定个体对环境的适应度。2可可以以认认为为生生物物体体的的基基因因在在染染色色体体上上呈呈线线性性排排列列，所有遗传与进化过程均发生在染色体上所有遗传与进化过程均发生在染色体上。3生生物物的的繁繁殖殖是是由由其其基基因因的的复复制制来来完完成成的的，交交叉叉重组重组是有性繁殖的基因复制的基本形式。是有性繁殖的基因复制的基本形式。4同同源源染染色色体体之之间间的的交交叉叉或或染染色色体体上上基基因因的的变变异异（突突变变）产产生生新新的的物物种种，使使生生物物体体呈呈现现新新的的性性状状，变异是物种进化的根本保证变异是物种进化的根本保证。脚笼跺淘赡衷榷哭楔垒撤拯刽蛋浦还屹稗
15、祭组获病导疼椎贞笆畅了位仍拽第八章遗传算法第八章遗传算法5自然依据个体生物的适应度决定其在种自然依据个体生物的适应度决定其在种群中是否存活群中是否存活，对环境适应性强的基因或染对环境适应性强的基因或染色体经常比适应性差的基因或染色体具有更色体经常比适应性差的基因或染色体具有更多的机会遗传到下一代。多的机会遗传到下一代。6竞争存在于生物种群以及种群与种群之竞争存在于生物种群以及种群与种群之间，间，竞争是规模无限扩大趋势的生物分享有竞争是规模无限扩大趋势的生物分享有限资源的直接结果，是物种进化的促进剂限资源的直接结果，是物种进化的促进剂。7有竞争必然有选择，自然选择是生物进有竞争必然有选择，自然选
16、择是生物进化的最基本规律。化的最基本规律。斥刷稿教醋径儿样缎防刃谷啮格氢告摇运肉扛游耸绸障软椽巨磷赂木奈忧第八章遗传算法第八章遗传算法8.2遗传算法遗传算法的基本原理的基本原理 遗遗传传算算法法是是基基于于自自然然选选择择和和遗遗传传机机制制，在在计计算算机机上上模模拟拟生生物物进进化化机机制制的的寻寻优优搜搜索索仿仿生生智智能能算算法法，它它模模拟拟的的机机制制是是一一切切生生命命与与智智能的产生与进化过程。能的产生与进化过程。 在在自自然然界界的的演演化化过过程程中中，生生物物体体通通过过遗遗传传（传传宗宗接接代代、后后代代和和双双亲亲非非常常相相像像）、变变异异（后后代代与与双双亲亲又又
17、不不完完全全相相像像）来来适适应应外外界界环境，一代又一代地优胜劣汰、繁衍进化。环境，一代又一代地优胜劣汰、繁衍进化。沮景芭纪殆廉须睫奏龟谦康评琢法推然餐瞄路幂着附梧责届躬懈汞柔利海第八章遗传算法第八章遗传算法 GAGA则则模模拟拟了了上上述述进进化化现现象象，它它把把搜搜索索空空间间（所所求求问问题题的的解解的的隶隶属属空空间间）映映射射为为遗遗传传空空间间，即即把把每每一一个个可可能能的的解解编编码码为为一一个个向向量量（二二进进制制或或十十进进制制数数字字或或字字符符串串），称称为为一一个个染染色色体体或或个个体体，向向量量的的每每个个元元素素称称为为基基因因，所所有有染染色色体体组组成
18、成群群体体或或种种群群，并并按按预预定定的的目目标标函函数数（或或某某种种评评价价指指标标）对对每每个个染染色色体体进进行行评评价价，据据其其评评价结果给出一个适应度值。价结果给出一个适应度值。 弗庞恬兜哈基迭肮凭谅网缎骂沽蛾岩钧腐味枝爽聘畜垂盗穿镊换婴蝉褥餐第八章遗传算法第八章遗传算法 算算法法开开始始时时先先随随机机地地产产生生一一些些染染色色体体（即即所所求求问问题题的的侯侯选选解解），计计算算其其适适应应度度，据据适适应应度度大大小小对对诸诸染染色色体体进进行行选选择择、交交叉叉（杂杂交交）、变变异异等等遗遗传传操操作作，剔剔除除适适应应度度低低（性性能能不不佳佳、不不适适宜宜环环境境
19、生生存存）的的染染色色体体，留留下下适适应应度度高高（性性能能优优良良、适适宜宜环环境境生生存存）的的染染色色体体，从从而而得得到到新新的的群群体体。由由于于新新群群体体的的成成员员是是上上一一代代群群体体的的优优秀秀者者，继继承承了了上上一一代代的的优优良良性性能能，因因而而明明显显优优于于上上一一代代。GAGA就就是是这这样样反反复复地地操操作作，向向着着更更优优解解的的方方向向进进化化，直到满足某种预定的优化收敛指标。直到满足某种预定的优化收敛指标。 惰瓢务睦灸受旷素塔疙淑八锁轰顶卖波长见没殃彤狠誉轿港确腥潍蔑汝肪第八章遗传算法第八章遗传算法8.3遗传算法的几个基本概念遗传算法的几个基本
20、概念个体个体种群和种群规模种群和种群规模 适应度函数适应度函数 生物群体中的染色体，设计向量映射到遗生物群体中的染色体，设计向量映射到遗传空间中的一个编码串。具体地说，就是一个传空间中的一个编码串。具体地说，就是一个侯选解。侯选解。一个生物群体就是一个种群，其中的生物一个生物群体就是一个种群，其中的生物个体的总数目就是种群规模。编码串总数目。个体的总数目就是种群规模。编码串总数目。适应度是生物个体适应环境生存的能力大适应度是生物个体适应环境生存的能力大小，或评价个体性能优劣的指标，与染色体之小，或评价个体性能优劣的指标，与染色体之间存在一定的关系。间存在一定的关系。臻平修绘螟煮膀筏惫苦扬活亨徊
21、棉甩热肝迟丰诽脆葫吏允辛佬漏面碑惊吼第八章遗传算法第八章遗传算法8.4遗传算法的基本算子遗传算法的基本算子 选择（选择（SelectionSelection）算子）算子 选选 择择 算算 子子 又又 称称 为为 繁繁 殖殖 、 再再 生生 或或 复复 制制（Reproduction）算算子子，它它是是用用以以模模拟拟生生物物界界去去劣劣存存优优的的自自然然选选择择现现象象。它它从从旧旧种种群群中中选选择择出出适适应应性性强强（适适应应度度高高）的的某某些些个个体体（染染色色体体），放放入入匹匹配配（交交配配或或配配对对）集集（MatingPool），为为通通过过染染色色体体交交叉叉和和变变异异
22、产产生生新新的的种种群群作作准准备备。适适应应度度越越高高的的染染色色体体被被选选择择的的可可能能性性越越大大，其其遗遗传传基基因因在在下下一一代代种种群群中中的的分分布布就就越越广广，其其子子孙孙（后后代代）在在下下一代出现的数量就越多。一代出现的数量就越多。滚贺抒稚翅媚腾评浩氦牙湿脂卓皮缉负撩熟勾媚轰癌矿封饮训蚌喊捎腾窑第八章遗传算法第八章遗传算法选选择择是是遗遗传传算算法法中中的的最最主主要要的的算算子子（机机制制），也也是是影影响响遗遗传传算算法法性性能能的的最最主主要要的的因因素素。但但选选择择只只能能从从旧旧的的种种群群中中选选择择出出优优秀秀者者，而而不不能能创创造造出出新新的的
23、染染色色体体。选选择择压压（SelectionPressure）描描述述了了选选择择算算子子挑挑选选种种群群中中不不同同个个体体做做母母体体的的概概率率大大小小的的差差异异。选选择择压压过过大大，会会造造成成几几个个较较好好可可行行解解（不不一一定定是是近近似似全全局局最最优优解解）迅迅速速占占领领了了整整个个种种群群；选选择择压压过过小小，则会使算法呈现出纯粹的随机徘徊行为。则会使算法呈现出纯粹的随机徘徊行为。九妒凡侍鼎铺铲瞅瞳厄堵湖貉聪垛抿牡杰赠恕鼻祥视丫抽腺漫英蛋掇舶煌第八章遗传算法第八章遗传算法选选择择有有多多种种方方法法，如如适适应应度度比比例例法法、期期望望值值法法、顺顺序序法法、
24、秩秩选选择择、适适应应度度函函数数的的尺尺度度变变换换、杰杰出出者者选选择择（ElitistSelection）。其其中中，适适应应度度比比例例法法是是比比较较普普遍遍采采用用的的策策略略，其其缺缺陷是易造成选择压过大或过小。陷是易造成选择压过大或过小。适适应应度度比比例例选选择择法法又又称称轮轮转转法法，它它把把种种群群中中的的所所有有染染色色体体适适应应度度的的总总和和看看作作一一个个轮轮子子的的圆圆周周，而而每每个个染染色色体体按按其其适适应应度度在在总总和和中中所所占占的的比比例例占占据据轮轮子子的的一一个个扇扇区区片片。每每次次染染色色体体的的选选择择可可看看作作轮轮子子的的一一次次
25、随随机机转转动动，它它转转到到哪哪个个扇扇区区停停下下来来，哪哪个个扇扇区区对对应应的的染染色色体就被选中。尽管体就被选中。尽管这种选择方法是随机的，这种选择方法是随机的，漆逐鞘侦蜡宴莆藉遂琅贼姥嚼溺韦镇纯更驱剔腰方董螺咽趾析漆菏母詹蹦第八章遗传算法第八章遗传算法但它与各染色体适应度成比例。这是因为适但它与各染色体适应度成比例。这是因为适应度大的染色体占据轮子扇区面积大，被选应度大的染色体占据轮子扇区面积大，被选中的概率就高（机会多），而适应度小的染中的概率就高（机会多），而适应度小的染色体占据的扇区面积小，被选中的概率就低色体占据的扇区面积小，被选中的概率就低（机会少）。（机会少）。1234
26、5687910M更煞宦碘崇气酞镜域岳厕创窝摊猛洼枕吵玫就缓发桔装臣睛恒颊疑瞄数纲第八章遗传算法第八章遗传算法举例：举例：儒腕词氖慨扰匆掐勒门解俊耻因剔臭羡根味尸鸯完垃梗放埠酚趋芥咸擒啼第八章遗传算法第八章遗传算法交叉（交叉（CrossoverCrossover，又称杂交）算子，又称杂交）算子 选选择择算算子子虽虽然然能能够够从从旧旧种种群群中中选选择择出出优优秀秀者者，但但不不能能创创造造新新的的染染色色体体，因因此此，遗遗传传算算法法的的开开创创者者提提出出了了交交叉叉算算子子。交交叉叉算算子子是是用用于于模模拟拟生生物物进进化化过过程程中中的的繁繁殖殖杂杂交交现现象象，它它通通过过两两个个
27、染染色色体体的的交交叉叉组组合合来来产产生生新新的的染染色色体体，即即在在匹匹配配集集中中任任选选两两个个染染色色体体（又又称称双双亲亲），随随机机地地选选择择一一个个交交叉叉点点（称称为为单单点点交交叉叉、单单点点杂杂交交），通通过过交交换换双双亲亲染染色色体体交交叉叉点点右右边边的的部部分分，从从而而得得到到两两个个新新的的染染色色体体（后后代代）。交交叉叉的的结结果果，有有可可能能使使各各个个个个体体的的优优点点互互相相补补充充而而产产生生更更优优的的后后代代。由由于于交交叉叉算算子子能能够够创创造造新新的的染染色色体体，从从而而允允许许测测试试产产生生于于搜搜索索空空间间中中的的新新点
28、点，它它体体现现了了自然界信息交换的思想。自然界信息交换的思想。镑尊隘瓦氖彪漏噎乓膊尺径囊溅妥芯必灼嫂而沏骑市抽屏宫预穆畦肯燕狰第八章遗传算法第八章遗传算法蚜馒吁凛穿枫刘骸襟易店灌友拾笺气粹宗疲迅郎审干维词虱讲钮措甭构饺第八章遗传算法第八章遗传算法变异（变异（MutationMutation）算子）算子选选择择和和交交叉叉算算子子实实现现了了遗遗传传算算法法的的大大范范围围搜搜索索过过程程，而而变变异异的的目目的的在在于于增增强强遗遗传传算算法法搜搜索索最最优优解解的的能能力力。变变异异算算子子用用以以模模拟拟生生物物在在自自然然的的遗遗传传环环境境中中由由于于各各种种偶偶然然因因素素引引起起
29、的的基基因因突突变变，它它以以很很小小的的概概率率随随机机地地改改变变遗遗传传基基因因（表表示示染染色色体体的的数数字字串串的的某某一一位位）的的值值。在在染染色色体体以以二二进进制制编编码码的的系系统统中中，它它随随机机地地将将染染色色体体的的某某一一个个基基因因由由1变变成成0或或由由0变变为为1。卞认价钩用旁众曲匡士秋谈苯娶链糯常歪溺套扼宽祝皱娥茬制档奥痢暗吾第八章遗传算法第八章遗传算法 如如果果只只有有选选择择和和交交叉叉算算子子，而而没没有有变变异异算算子子，则则无无法法在在初初始始基基因因组组合合以以外外的的空空间间进进行行搜搜索索，从从而而使使进进化化过过程程的的早早期期就就陷陷
30、入入局局部部解解而而终终止止进进化化过过程程，使使解解的的质质量量受受到到很很大大限限制制。通通过过变变异异算算子子可可以以确确保保群群体体中中遗遗传传基基因因类类型型的的多多样样性性，以以使使搜搜索索能能在在尽尽可可能能大大的的空空间间中中进进行行，避避免免丢丢失失在在搜搜索索中中有有用用的的遗遗传传信信息息而而陷陷入入局局部部解解，从从而而获获得得质质量量较较高高的的优优化化解解。变变异异算算子子是是个个体体空空间间到到个个体体空空间间的的随随机机映映射射，其其作作用用方方式式为为独独立立地地以以概概率率P Pm m改改变变个个体体分分量量取值。称取值。称P Pm m为变异概率。为变异概率
31、。欧如在辆臂躲读绿卧豺比泅而砰滋隘炒君孝肝桌村别予阶柔肺开殊驱赤接第八章遗传算法第八章遗传算法遗遗传传算算法法的的上上述述三三个个基基本本算算子子：选选择择、交交叉叉和和变变异异算算子子，各各有有其其功功能能。单单纯纯利利用用选选择择可可找找到到局局部部最最优优值值，变变异异可可以以使使搜搜索索空空间间遍遍及及整整个个空空间间，而而交交叉叉结结果果依依赖赖于于初初始始分分布布。因因此此，一一个个完完整整的的遗遗传传算算法法应应当当是是选选择择、交交叉和变异运算共同构成的。叉和变异运算共同构成的。娶腮姿涉阶裔捡泳辫燎永众迅辑蓝烤闭耽果务镇节肉响谢湛棍使病存堆极第八章遗传算法第八章遗传算法8.4遗
32、传算法实现举例遗传算法实现举例假假设设一一个个快快餐餐店店追追求求的的目目标标是是最最高高的的利利润润，要要达达到到这这一一目目标标，必必须须选选择择适适当当的的经经营营策策略略。一种可能的策略是对以下三个问题作出决策。一种可能的策略是对以下三个问题作出决策。1)每盘炒米粉的价格是每盘炒米粉的价格是5元还是元还是10元元2)与与炒炒米米粉粉配配套套的的饮饮料料是是非非常常可可乐乐还还是是椰椰子子汁汁3)提供快速还是排队慢速服务提供快速还是排队慢速服务以以下下介介绍绍用用遗遗传传算算法法来来解解决决这这个个决决策策问问题题的的方法和过程。方法和过程。氛疏万敞子拢卓碍乱籍户搏则值眩倘哦隶保缠蛤洁鳞
33、恒褒卉繁熏迷羊则裹第八章遗传算法第八章遗传算法（1）把把问问题题的的可可能能解解表表示示为为染染色色体体数数字字串串（问题编码）（问题编码）由由于于这这个个问问题题有有三三个个决决策策变变量量，其其取取值值为为是是或或否否，可可以以用用1或或0来来表表示示，于于是是可可以以用用三三位位的的二二进进制制数数字字表表征征一一种种可可能能的的经经营营策策略略，解解的的搜搜索索空空间间为为23=8，即即有有8种种经经营营策策略略可可供供选选择择。表表3给给出出了了其其中中快快餐餐店店经经理理已已知知的的4种种经经营营策策略略（初初始始解解）。表表中中数数字字串串的的第第一一位位取取0表表示示价价格格高
34、高，1表表示示价价格格低低；第第二二位位取取0表表示示椰椰子子汁汁，取取1表表示示非非常常可可乐乐；第第三三位位取取0表表示示排排队队慢慢速速服服务务，取取1表示快速服务。表示快速服务。谣描扎呈屡涨团始歉蛤艇鼓澜葡反袄擅衅敌夕语缝骨揩诱哼事鸽歇沮镭焊第八章遗传算法第八章遗传算法举蚊坪旦怜昨由叠允熔章嘶担钎党式气淋桑炮辣感拷耘帜他踪肌障冈拴止第八章遗传算法第八章遗传算法a)求各染色体的适应度。求各染色体的适应度。 这这个个问问题题中中，一一个个染染色色体体的的适适应应度度假假设设恰恰好好是是其其二二进进制制数数字字串串等等价价的的十十进进制制数数，也也是是对对应应的经营策略的利润。的经营策略的利
35、润。绵禁孜锦轧哥当语闯抽拟践仁坍晓跃国般柱渴半昌乐溢桥老安戊厩皆谐出第八章遗传算法第八章遗传算法b)选择进入交叉集的染色体选择进入交叉集的染色体 由由表表4可可见见，所所有有染染色色体体串串的的适适应应度度的的总总和和是是12，数数字字串串110的的适适应应度度是是6，占占适适应应度度总总和和的的1/2，也也就就是是说说该该串串被被选选中中的的机机会会有有两两次次，其其概概率率为为1/2；串串011，001，010被被选选中中的的概概率率分分别别为为3/12=1/4，1/12，2/12=1/6。按按前前述述的的适适应应度度比比例例法法，选选择择进进入入交交叉叉集集的的染染色色体体串串及及其其适
36、适应应度度值见表值见表5所示。所示。臭某冻也修豌衫膜曲魄粕激复秸丘阮睡杂边瞧姆寺隶叮泳烛舍捷俏做医躯第八章遗传算法第八章遗传算法摈拔咙左警涌望券本驶予盯泄种售糯慑窖编泅激南息盂语杂删澈牺拾叭虹第八章遗传算法第八章遗传算法 从从表表5可可知知，选选择择算算子子的的作作用用确确实实是是改改进进了了种种群群的的平平均均适适应应度度，使使其其由由原原来来的的3提提高高到到了了4.25，最最坏坏的的适适应应度度由由原原来来的的1改改进进为为2，性性能能最最差差的的染染色色体体已已从从种种群群中中删删除除。但但是是，选选择择不不能能创创造造新新的的染染色色体体，为为了了改改进进这这一一缺缺点点，寻寻找找搜
37、搜索索空空间间内内的的新新的的检检测测点点，必必须须进进行交叉操作。行交叉操作。柔刷嫂疵嚏诛横胳纠祟獭评搔韦吧郁翔荧襟诅淘恤椒哀向厢蜕辟戳局绩净第八章遗传算法第八章遗传算法 c)交叉操作交叉操作 这这里里采采用用单单点点交交叉叉算算子子进进行行交交叉叉操操作作，随随机机产产生生的的交交叉叉点点是是2，从从交交叉叉集集中中任任取取一一对对染染色色体体如如011和和110，互互换换它它们们的的第第3位位，得得到到子子孙孙（后后代代）染染色色体体010和和111，其其中中111是是交交叉叉算算子子操操作作创创造造出出的的新新的的染染色色体体。因因为为本本例例中中交交叉叉概概率率为为0.5，交交叉叉集
38、集中中剩剩下下两两个个染染色色体体不不再再参参加加交交叉叉操操作作，而而与与交交叉叉操操作作后后得得到到的的子子孙孙一一起起作作为为下下一一代代种种群群的的成成员员。由由此此得得到到第第一一次次交交叉叉操操作作后后的的第第一一代代种种群群，如如表表6中所示中所示咬蚕蝎孪锦疮丰啄扁涵沙读毯剥纳萝酚盎费哼澜撅减郎军嫩蟹蛇凿弦赐昨第八章遗传算法第八章遗传算法镣州抒敢霖土铱绊抑梢责喧月咎玩气忌鲤臻屋威范募胸它视烟柏盛图借镶第八章遗传算法第八章遗传算法显显然然，经经过过交交叉叉操操作作，种种群群中中产产生生了了新新的的染染色色体体（个个体体）111，而而且且其其适适应应度度最最高高，即即性性能能最优。最
39、优。d)对新一代种群的适应度进行评价对新一代种群的适应度进行评价经经过过交交叉叉操操作作，在在新新一一代代（第第1代代）种种群群中中，最最优优染染色色体体的的适适应应度度由由原原来来的的6提提高高到到了了7，其其对对应应的的代代码码串串是是111，表表示示一一种种优优化化的的经经营营策策略略，即即低低价价格格销销售售炒炒米米粉粉，配配套套供供应应的的饮饮料料为为非非常常可可乐乐，而而且且通通过过快快速速服服务务可可获获得得最最高高利利润润7元元，即即数数字字串串111的的适适应应度度。平平均均适适应应度度由由原原来来的的3提提高高到到了了4.25，最最坏坏适适应应度度由由原原来来的的1提提高高到到了了2，整整个个种种群群的的适适应应度度在在总总体体上上得得到到了了提提高高，被被优化了。优化了。膘鼻员莹玄霄勺临砰舞玻仇另扶蓖箭废枫浩恃池惋拴炸黔椭驻伞滩转作怖第八章遗传算法第八章遗传算法谢谢谢谢大大家家！穗摊垮蒋锤释还独荧紧替桩也哀乐努牌刁娟笋腺骆景趟稗蛤砂塞现怀毯陀第八章遗传算法第八章遗传算法
