《遗传算法综述及简单应用实例优秀PPT.ppt》由会员分享，可在线阅读，更多相关《遗传算法综述及简单应用实例优秀PPT.ppt（186页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、智能优化计算智能优化计算华东理工大学自动化系 2010年 遗传算法综述及简洁应用实例遗传算法综述及简洁应用实例及及Matlab程序程序 1智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 4.1 遗传算法简介遗传算法简介遗传算法简介遗传算法简介 4.1.1 4.1.1 遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问 4.1.3 4.1.3 遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点遗
2、传算法的思路与特点 4.1.4 4.1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 4.1.5 4.1.5 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 4.2 4.2 基本遗传算法基本遗传算法基本遗传算法基本遗传算法 4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 4.2.2 4.2.2 遗传基因型遗传基因型遗传基因型遗传基因型 4.2.3 4.2.3 适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 4.2.4 4.2.4 遗传操作遗传操作遗传操作遗传操作
3、选择选择选择选择 4.2.5 4.2.5 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 4.2.6 4.2.6 遗传操作遗传操作遗传操作遗传操作变异变异变异变异 4.2.7 4.2.7 算法的设计与实现算法的设计与实现算法的设计与实现算法的设计与实现 4.2.8 4.2.8 模式定理模式定理模式定理模式定理 2智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w产生产生w早在早在50年头，一些生物学家起先探讨运用数字计算年头，一些生物学家起先探讨运用数字计算机模拟生物的自然遗传与自然进化过程；机模拟生物的自然遗传与
4、自然进化过程；w1963年，德国柏林技术高校的年，德国柏林技术高校的I.Rechenberg和和H.P.Schwefel，做风洞试验时，产生了进化策略的，做风洞试验时，产生了进化策略的初步思想；初步思想；w60年头，年头，L.J.Fogel在设计有限态自动机时提出在设计有限态自动机时提出进化规划的思想。进化规划的思想。1966年年Fogel等出版了基于模等出版了基于模拟进化的人工智能，系统阐述了进化规划的思想。拟进化的人工智能，系统阐述了进化规划的思想。4 4.1.1 .1.1 遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 3智能优化计算智能优化计算华东理工
5、大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w产生产生w60年头中期，美国年头中期，美国Michigan高校的高校的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然教授提出借鉴生物自然遗传的基本原理用于自然w 和人工系统的自适应行为探讨和串编码技术；和人工系统的自适应行为探讨和串编码技术；w1967年，他的学生年，他的学生J.D.Bagley在博士论文中首次在博士论文中首次提出提出“遗传算法遗传算法(Genetic Algorithms)”一词；一词；w1975年，年，Holland出版了著名的出版了著名的“Adaptation in Natural and A
6、rtificial Systems”，标记遗传算法，标记遗传算法的诞生。的诞生。4 4.1.1 .1.1 遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 4智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w发展发展w70年头初，年头初，Holland提出了提出了“模式定理模式定理”（Schema Theorem），一般认为是），一般认为是“遗传算遗传算法的基本定理法的基本定理”，从而奠定了遗传算法探讨的理论，从而奠定了遗传算法探讨的理论基础；基础；w1985年，在美国召开了第一届遗传算法国际会议，年，在美国召开了第一
7、届遗传算法国际会议，并且成立了国际遗传算法学会并且成立了国际遗传算法学会(ISGA，International Society of Genetic Algorithms)；4 4.1.1 .1.1 遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 5智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w发展发展1988年，年，Holland的学生的学生D.J.Goldherg出版了出版了“Genetic Algorithms in Search,Optimization,and Machine Learning”，对遗传
8、算法及其应用作了全，对遗传算法及其应用作了全面而系统的论述；面而系统的论述；1991年，年，L.Davis编辑出版了编辑出版了Handbook of genetic algorithms，其中包括了遗传算法在工程技术和，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。社会生活中大量的应用实例。4 4.1.1 .1.1 遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 6智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w达尔文的自然选择说达尔文的自然选择说w遗传（遗传（heredity）：子代和父代具有相）：子代
9、和父代具有相w 同或相像的性状，保证物种的稳定性；同或相像的性状，保证物种的稳定性；w变异（变异（variation）：子代与父代，子代不同个体之）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；间总有差异，是生命多样性的根源；w生存斗争和适者生存：具有适应性变异的个体被保生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。留，不具适应性变异的个体被淘汰。w 自然选择过程是长期的、缓慢的、连续的过程。自然选择过程是长期的、缓慢的、连续的过程。4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物
10、进化理论和遗传学的基本学问 7智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w遗传学遗传学(Genetics)基本概念与术语基本概念与术语w染色体（染色体（chromosome）：遗传物质的载体；）：遗传物质的载体；w脱氧核糖核酸（脱氧核糖核酸（DNA）：大分子有机聚合物，双螺）：大分子有机聚合物，双螺旋结构；旋结构；w遗传因子（遗传因子（gene）：）：DNA或或RNA长链结构中占有确长链结构中占有确定位置的基本遗传单位；定位置的基本遗传单位；4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学
11、的基本学问生物进化理论和遗传学的基本学问 8智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w遗传学基本概念与术语遗传学基本概念与术语w基因型（基因型（genotype）：遗传因子组合的模型；）：遗传因子组合的模型；w表现型（表现型（phenotype）：由染色体确定性状的外部）：由染色体确定性状的外部表现；表现；4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问 1 1 1 1 1 1 1 1 1 1 0 1 1 1 9智能优化计算智能优化计算华东理工大学
12、自动化系 2010年 4.1 遗传算法简介遗传算法简介 w遗传学基本概念与术语遗传学基本概念与术语基因座（基因座（locus）：遗传基因在染色体中所占据的位）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因置，同一基因座可能有的全部基因称为等位基因（allele）；）；个体（个体（individual）：指染色体带有特征的实体；）：指染色体带有特征的实体；种群（种群（population）：个体的集合，该集合内个体数）：个体的集合，该集合内个体数称为种群的大小；称为种群的大小；4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理
13、论和遗传学的基本学问生物进化理论和遗传学的基本学问 10智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w遗传学基本概念与术语遗传学基本概念与术语w进化（进化（evolution）：生物在其持续生存的过程中，）：生物在其持续生存的过程中，渐渐适应其生存环境，使得其品质不断得到改良，渐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；这种生命现象称为进化；w适应度（适应度（fitness）：度量某个物种对于生存环境的）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得适应程度。对生存环境适应程度较高的物种将获得更多的
14、繁殖机会，而对生存环境适应程度较低的物更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至渐渐灭亡种，其繁殖机会就会相对较少，甚至渐渐灭亡;4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问 11智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w遗传学基本概念与术语遗传学基本概念与术语w选择（选择（selection）：指确定以确定的概率从种群）：指确定以确定的概率从种群中选择若干个体的操作中选择若干个体的操作；w复制（复制（repr
15、oduction）：细胞在分裂时，遗传物质）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因就继承了旧细胞的基因;w交叉（交叉（crossover）：在两个染色体的某一相同位）：在两个染色体的某一相同位置处置处DNA被切断，其前后两串分别交叉组合形成两被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称个新的染色体。又称基因重组，俗称“杂交杂交”;4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问 12智
16、能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w遗传学基本概念与术语遗传学基本概念与术语变异（变异（mutation）：在细胞进行复制时可能以很小）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使的概率产生某些复制差错，从而使DNA发生某种变发生某种变异，产生出新的染色体，这些新的染色体表现出新异，产生出新的染色体，这些新的染色体表现出新的性状的性状;编码（编码（coding）：表现型到基因型的映射；）：表现型到基因型的映射；解码（解码（decoding）：从基因型到表现型的映射。）：从基因型到表现型的映射。4.1.2 4.1.2 生物进化
17、理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问 13智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w进化论与遗传学的融合进化论与遗传学的融合w 19301947年，达尔文进化论与遗传学走向融年，达尔文进化论与遗传学走向融合，合，Th.Dobzhansky1937年发表的遗传学与物年发表的遗传学与物种起源是融合进化论与遗传学的代表作。种起源是融合进化论与遗传学的代表作。w生物进化与智能学的关系生物进化与智能学的关系w 生物物种作为困难系统，具有奇异的自适应、生物物种作为困难系统，具有奇
18、异的自适应、自组织和自优化实力，这是一种生物在进化过程中自组织和自优化实力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。体现的智能，也是人工系统梦寐以求的功能。4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问 14智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w遗传算法的基本思路遗传算法的基本思路 4 4.1.3 .1.3 遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点 15智能优化计算智能优化计算华
19、东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w自组织、自适应和自学习性自组织、自适应和自学习性w 在编码方案、适应度函数及遗传算子确定后，在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜寻。算法将利用进化过程中获得的信息自行组织搜寻。w本质并行性本质并行性w 内在并行性与内含并行性内在并行性与内含并行性w不需求导不需求导w 只需目标函数和适应度函数只需目标函数和适应度函数w概率转换规则概率转换规则w 强调概率转换规则，而不是确定的转换规则强调概率转换规则，而不是确定的转换规则 4 4.1.3 .1.3 遗传算法的思路与特点遗传算法的思路与特
20、点遗传算法的思路与特点遗传算法的思路与特点 16智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w简洁实例简洁实例w产生初始种群产生初始种群w计算适应度计算适应度 4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 0001100000 0101111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）17智
21、能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w简洁实例简洁实例w选择选择 4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488521071251910140.08695758521071
22、251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.15217418智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w简洁实例简洁实例w选择选择 4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率100011000008201011110015300000001012410011101001051010101010761110010110127
23、1001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.00000019智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w简洁实例简洁实例w选择选择w在在01之间产生一个之间产生一个w随机数：随机数：4
24、 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.141
25、3040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！淘汰！淘汰！20智能优化计算智能优化计算华东理工大学自动化系 2010年 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 00010100114.
26、1 遗传算法简介遗传算法简介 w简洁实例简洁实例w交叉交叉 4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 0001010011000111101000000101101111000010110101101111000010011101000001100111010011000000011010101000101001001121智能优化计算智能优化
27、计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w简洁实例简洁实例w变异变异 4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 00010100110001111010000001011011110000101101011011110000100101010000011001110100110000000110101010001
28、0100100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011000111101000000101101111000010110101101111000010011101000001100111010011000000011010101000101001001122智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w简洁实例简洁实例w至下一代，适应度计算至下一代，适应度计算选择选择交
29、叉交叉变异，直变异，直至满足终止条件。至满足终止条件。4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 23智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w选择选择 1.适应度计算适应度计算：按比例的适应度函数（按比例的适应度函数（proportional fitness assignment）基于排序的适应度计算（基于排序的适应度计算（Rank-based fitness assignment）4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 24
30、智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w选择选择 2.选择算法选择算法：轮盘赌选择（轮盘赌选择（roulette wheel selection）随机遍历抽样（随机遍历抽样（stochastic universal selection）局部选择（局部选择（local selection）截断选择（截断选择（truncation selection）锦标赛选择（锦标赛选择（tournament selection）4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 25智能优化计算智能优化计算华
31、东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w交叉或基因重组交叉或基因重组 实值重组（实值重组（real valued recombination）：离散重组（离散重组（discrete recombination）中间重组（中间重组（intermediate recombination）线性重组（线性重组（linear recombination）扩展线性重组（扩展线性重组（extended linear recombination）4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 26智能优化计算智能优化计算华东理工大
32、学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w交叉或基因重组交叉或基因重组w 二进制交叉（二进制交叉（binary valued crossover）：）：w单点交叉（单点交叉（single-point crossover）w多点交叉（多点交叉（multiple-point crossover）w匀整交叉（匀整交叉（uniform crossover）w洗牌交叉（洗牌交叉（shuffle crossover）w缩小代理交叉（缩小代理交叉（crossover with reduced surrogate）4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操
33、作遗传算法的基本操作 27智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w变异变异 实值变异实值变异 二进制变异二进制变异 4 4.1.4 .1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 28智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w函数优化函数优化w 是遗传算法的经典应用领域是遗传算法的经典应用领域;w组合优化组合优化w 实践证明，遗传算法对于组合优化中的实践证明，遗传算法对于组合优化中的NP完全完全问题特别有效问题特别有效;w自动限制自动限制w 如基于遗传算
34、法的模糊限制器优化设计、基于如基于遗传算法的模糊限制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等网络的结构优化设计和权值学习等;4 4.1.5 .1.5 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 29智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w机器人智能限制机器人智能限制w 遗传算法已经在移动机器人路径规划、关节机遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人运动轨迹规划、机器人逆运动学求解、细胞机
35、器人的结构优化和行动协调等器人的结构优化和行动协调等;w组合图像处理和模式识别组合图像处理和模式识别w 目前已在图像复原、图像边缘持征提取、几何目前已在图像复原、图像边缘持征提取、几何形态识别等方面得到了应用形态识别等方面得到了应用;4 4.1.5 .1.5 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 30智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 遗传算法简介遗传算法简介 w人工生命人工生命w 基于遗传算法的进化模型是探讨人工生命现象基于遗传算法的进化模型是探讨人工生命现象的重要理论基础，遗传算法已在其进化模型、学习的重要理论基础，遗传算法已在其进化模型、
36、学习模型、行为模型等方面显示了初步的应用实力；模型、行为模型等方面显示了初步的应用实力；w遗传程序设计遗传程序设计w Koza发展了遗传程序设计的慨念，他运用了以发展了遗传程序设计的慨念，他运用了以LISP语言所表示的编码方法，基于对一种树型结构语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序。所进行的遗传操作自动生成计算机程序。4 4.1.5 .1.5 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 31智能优化计算智能优化计算华东理工大学自动化系 2010年 4.1 4.1 遗传算法简介遗传算法简介遗传算法简介遗传算法简介 4.1.1 4.1.1 遗传算
37、法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 4.1.2 4.1.2 生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问生物进化理论和遗传学的基本学问 4.1.3 4.1.3 遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点 4.1.4 4.1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 4.1.5 4.1.5 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 4.2 4.2 基本遗传算法基本遗传算法基本遗传算法基本遗传算法 4.2.1 4.2.1 简
38、洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 4.2.2 4.2.2 遗传基因型遗传基因型遗传基因型遗传基因型 4.2.3 4.2.3 适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 4.2.4 4.2.4 遗传操作遗传操作遗传操作遗传操作选择选择选择选择 4.2.5 4.2.5 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 4.2.6 4.2.6 遗传操作遗传操作遗传操作遗传操作变异变异变异变异 4.2.7 4.2.7 算法的设计与实现算法的设计与实现算法的设计与实现算法的设计与实现 4
39、.2.8 4.2.8 模式定理模式定理模式定理模式定理 32智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w问题的提出问题的提出 一元函数求最大值：一元函数求最大值：4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 33智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w问题的提出问题的提出 用微分法求取用微分法求取f(x)的最大值：的最大值：解有无穷多个：解有无穷多个：4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化
40、的实例 34智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w问题的提出问题的提出w 当当i为奇数时为奇数时xi对应局部极大值点，对应局部极大值点，i为偶数时为偶数时xi对应局部微小值。对应局部微小值。x19即为区间即为区间-1,2内的最大值内的最大值点：点：w 此时，函数最大值此时，函数最大值f(x19)比比f(1.85)=3.85稍大。稍大。4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 35智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w编码编码 表
41、现型：表现型：x 基因型：二进制编码（串长取决于求解精度）基因型：二进制编码（串长取决于求解精度）串长与精度之间的关系串长与精度之间的关系：若要求求解精度到若要求求解精度到6位小数，区间长度为位小数，区间长度为2-(-1)3，即需将区间分为，即需将区间分为3/0.000001=3106等份。等份。所以编码的二进制串长应为所以编码的二进制串长应为22位。位。4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 36智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w产生初始种群产生初始种群 产生的方式：随机产生
42、的方式：随机 产生的结果：长度为产生的结果：长度为22的二进制串的二进制串 产生的数量：种群的大小（规模），如产生的数量：种群的大小（规模），如30，50，4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 37智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w计算适应度计算适应度w 不同的问题有不同的适应度计算方法不同的问题有不同的适应度计算方法w 本例：干脆用目标函数作为适应度函数本例：干脆用目标函数作为适应度函数w 将某个体转化为将某个体转化为-1,2区间的实数：区间的实数：w 计算计算x的函数值（
43、适应度）：的函数值（适应度）：w f(x)=xsin(10 x)+2.0=2.586345 4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 38智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w计算适应度计算适应度w 二进制与十进制之间的转换：二进制与十进制之间的转换：w 第一步，将一个二进制串（第一步，将一个二进制串（b21b20b0）转化为）转化为10进制数：进制数：w 其次步，其次步，x对应的区间对应的区间-1,2内的实数：内的实数：4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简
44、洁函数优化的实例简洁函数优化的实例 (0000000000000000000000)-139智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w遗传操作遗传操作 选择：轮盘赌选择法；选择：轮盘赌选择法；交叉：单点交叉；交叉：单点交叉；变异：小概率变异变异：小概率变异 4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 40智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w模拟结果模拟结果 设置的参数设置的参数：种群大小种群大小50；交叉概率；交叉概率0.75；变异
45、概率；变异概率0.05；最大；最大代数代数200。得到的最佳个体得到的最佳个体：smax xmax=1.8506;f(xmax)=3.8503;4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 41智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w模拟结果模拟结果 进化的过程进化的过程：4.2.1 4.2.1 简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例简洁函数优化的实例 世代数世代数自变量自变量适应度适应度11.44953.449491.83953.7412171.85123.8499301
46、.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.850342智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w编码原则编码原则w完备性（完备性（completeness）：问题空间的全部解都）：问题空间的全部解都能表示为所设计的基因型；能表示为所设计的基因型；w健全性（健全性（soundness）：任何一个基因型都对应）：任何一个基因型都对应于一个可能解；于一个可能解；w非冗余性（非冗余性（non-redundancy）：问题空间和表达）：问题空间和表达空间一一对应。空
47、间一一对应。4 4.2.2 .2.2 遗传基因型遗传基因型遗传基因型遗传基因型 43智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w多种编码方式多种编码方式二进制编码；二进制编码；浮点数编码；浮点数编码；格雷码编码；格雷码编码；符号编码；符号编码；复数编码；复数编码；DNA编码等。编码等。4 4.2.2 .2.2 遗传基因型遗传基因型遗传基因型遗传基因型 44智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w二进制编码与浮点数编码的比较二进制编码与浮点数编码的比较在交叉操作时，二进制编码比浮点数编码产生新
48、个在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；成的超体的限制；在变异操作时，二进制编码的种群稳定性比浮点数在变异操作时，二进制编码的种群稳定性比浮点数编码差。编码差。4 4.2.2 .2.2 遗传基因型遗传基因型遗传基因型遗传基因型 45智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w适应度函数的重要性适应度函数的重要性w 适应度函数的选取干脆影响遗传算法的收敛速适应度函数的选取干脆影响遗传算法的收敛速度以及能否找到最优解。度以及能否找到最优解。
49、w 一般而言，适应度函数是由目标函数变换而成一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的的，对目标函数值域的某种映射变换称为适应度的尺度变换（尺度变换（fitness scaling）。）。4 4.2.3 .2.3 适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 46智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w适应度函数的设计适应度函数的设计w单值、连续、非负、最大化单值、连续、非负、最大化w合理、一样性（能够反映解的优劣）合理、一样性（能够反映解的优劣）w计算量
50、小计算量小w通用性强通用性强 4 4.2.3 .2.3 适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 47智能优化计算智能优化计算华东理工大学自动化系 2010年 4.2 基本遗传算法基本遗传算法 w几种常见的适应度函数几种常见的适应度函数w干脆转换干脆转换w 若目标函数为最大化问题：若目标函数为最大化问题：Fit(f(x)=f(x)w 若目标函数为最小化问题：若目标函数为最小化问题：Fit(f(x)=-f(x)4 4.2.3 .2.3 适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 48智能优化计算智能优化