《张砦-遗传算法在多目标优化中的应用培训讲学.ppt》由会员分享，可在线阅读，更多相关《张砦-遗传算法在多目标优化中的应用培训讲学.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、遗传算法在多目标遗传算法在多目标(mbio)优化优化中的应用中的应用张砦张砦第一页，共45页。目目 录录一、遗传算法概述一、遗传算法概述二、多目标二、多目标(mbio)(mbio)优化问题优化问题三、实例三、实例1Rosenbrock1Rosenbrock函数最值问题函数最值问题四、实例四、实例22智能组卷问题智能组卷问题第二页，共45页。一、遗传算法概述一、遗传算法概述(i sh)1.1 1.1 遗传算法的生物学基础遗传算法的生物学基础1.2 1.2 遗传算法搜索机制遗传算法搜索机制 1.3 1.3 遗传算法的发展遗传算法的发展1.4 1.4 基本遗传算法（基本遗传算法（SGASGA）1.5
2、 1.5 遗传算法的特点遗传算法的特点1.6 1.6 遗传算法的收敛性分析遗传算法的收敛性分析1.7 1.7 遗传算法研究遗传算法研究(ynji)(ynji)的主要问题的主要问题1.8 1.8 遗传算法的应用遗传算法的应用第三页，共45页。1.1 1.1 遗传算法的生物学基础遗传算法的生物学基础 生物在自然界中的生存繁衍，显示出了其对自生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生然环境的自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。适应系统
3、的设计和开发提供了广阔的前景。遗传算法遗传算法(Genetic Algorithms(Genetic Algorithms，简称，简称GAs)GAs)所所借鉴的生物学基础是生物的遗传和进化。借鉴的生物学基础是生物的遗传和进化。(1)(1)生物的所有遗传信息都包含在其染色体中，生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；染色体决定了生物的性状；(2)(2)染色体是由基因及其有规律的排列所构成的，染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；遗传和进化过程发生在染色体上；(3)(3)生物的繁殖过程是由其基因的复制过程来完生物的繁殖过程是由其基因的复制过程来
4、完成的；成的；(4)(4)通过同源染色体之间的交叉通过同源染色体之间的交叉(jioch)(jioch)或染或染色体的变异会产生新的物种，使生物呈现新的性状。色体的变异会产生新的物种，使生物呈现新的性状。(5)(5)对环境适应性好的基因或染色体经常比适应对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。性差的基因或染色体有更多的机会遗传到下一代。第四页，共45页。1.2 1.2 遗传算法搜索遗传算法搜索(su su)(su su)机制机制 遗传算法模拟自然选择和自然遗传过程中发生的繁遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象（染色体的变化）
5、，将实际问殖、交叉和基因突变现象（染色体的变化），将实际问题的解答描述成染色体的形式，进行类似生物进化现象题的解答描述成染色体的形式，进行类似生物进化现象的操作以求解。对每次迭代中保留的候选解，按某种指的操作以求解。对每次迭代中保留的候选解，按某种指标从解群中选取较优的个体，利用遗传算子标从解群中选取较优的个体，利用遗传算子(sun z)(sun z)(选择、交叉和变异选择、交叉和变异)对这些个体进行组合，产生新一代对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。的候选解群，重复此过程，直到满足某种收敛指标为止。第五页，共45页。1.3 1.3 遗传算法的发展遗
6、传算法的发展(1)(1)萌芽期萌芽期(50(50年代后期至年代后期至7070年代初期年代初期)50 50年代后期，一些生物学家着手采用电子年代后期，一些生物学家着手采用电子计算机模拟生物的遗传系统，尽管这些工作纯粹计算机模拟生物的遗传系统，尽管这些工作纯粹是研究生物现象，但其中已使用现代遗传算法的是研究生物现象，但其中已使用现代遗传算法的一些标识方式。一些标识方式。1965 1965年，德国的年，德国的L.RechenbergL.Rechenberg等人正式提出等人正式提出进化策略的方法，当时的进化策略只有一个个体，进化策略的方法，当时的进化策略只有一个个体，而且进化操作也只有变异一种。而且进
7、化操作也只有变异一种。1965 1965年，美国的年，美国的L.j.FogelL.j.Fogel正式提出进化规正式提出进化规划，在计算中采用多个个体组成的群体，而且只划，在计算中采用多个个体组成的群体，而且只运用变异操作。运用变异操作。60 60年代期间，美国年代期间，美国J.H.HollandJ.H.Holland在研究自适在研究自适应应(shyng)(shyng)系统时，提出系统本身与外部环境系统时，提出系统本身与外部环境相互协调的遗传算法。相互协调的遗传算法。19681968年，年，J.H.HollandJ.H.Holland教教授又提出模式理论，它成为遗传算法的主要理论授又提出模式理论
8、，它成为遗传算法的主要理论基础。基础。1967 1967年，年，BagleyBagley发表了关于遗传算法应用的发表了关于遗传算法应用的论文，在其论文中首次使用论文，在其论文中首次使用“遗传算法（遗传算法（Genetic AlgorithmGenetic Algorithm）”一词。一词。第六页，共45页。(2)(2)成长期成长期(70(70年代中期至年代中期至8080年代末期年代末期)1975 1975年，年，J.H.HollandJ.H.Holland教授的专著教授的专著Adaptation in Natural and Adaptation in Natural and Artifici
9、al SystemArtificial System正式出版，全面地介绍了遗传算法，人们常常把正式出版，全面地介绍了遗传算法，人们常常把这一事件视作遗传算法问世的标志，这一事件视作遗传算法问世的标志，Holland Holland也被视作遗传算法的创始也被视作遗传算法的创始人。人。1975 1975年，年，De.JongDe.Jong在其博士论文中结合模式定理进行了大量的纯数在其博士论文中结合模式定理进行了大量的纯数值函数值函数(hnsh)(hnsh)优化计算实验，树立了遗传算法的工作框架，得到了一优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。些重要且具有指导意义
10、的结论。1987 1987年，美国年，美国D.LawrenceD.Lawrence总结人们长期从事遗传算法的经验，公总结人们长期从事遗传算法的经验，公开出版开出版Genetic Algorithm and Simulated AnnealingGenetic Algorithm and Simulated Annealing一书，以论一书，以论文集形式用大量实例介绍遗传算法。文集形式用大量实例介绍遗传算法。1985 1985年，作为年，作为HollandHolland的学生，的学生，D.E.GoldbergD.E.Goldberg博士出版专著博士出版专著Genetic Algorithmsin
11、 SearchGenetic Algorithmsin Search，Optimization and Machine Optimization and Machine LearningLearning，全面、系统地介绍遗传算法，使这一技术得到普及与推广。，全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为遗传算法的教科书。该书被人们视为遗传算法的教科书。1985 1985年，在美国举行第一届遗传算法国际学术会议年，在美国举行第一届遗传算法国际学术会议(International Conference on Genetic Algorithms(International Co
12、nference on Genetic Algorithms，简称，简称ICGAICGA），），与会者交流运用遗传算法的经验。随后，每与会者交流运用遗传算法的经验。随后，每2 2年左右都举行一次这种会年左右都举行一次这种会议。议。第七页，共45页。(3)(3)(3)(3)发展发展发展发展(fzhn)(fzhn)(fzhn)(fzhn)期期期期(90(90(90(90年代以后年代以后年代以后年代以后)90 90 90 90年代，遗传算法不断地向广度和深度发展年代，遗传算法不断地向广度和深度发展年代，遗传算法不断地向广度和深度发展年代，遗传算法不断地向广度和深度发展(fzhn)(fzhn)(fzh
13、n)(fzhn)。1991 1991 1991 1991年，年，年，年，D.LawrenceD.LawrenceD.LawrenceD.Lawrence出版出版出版出版Handbook of Genetic AlgorithmsHandbook of Genetic AlgorithmsHandbook of Genetic AlgorithmsHandbook of Genetic Algorithms一一一一书，详尽地介绍遗传算法的工作细节。书，详尽地介绍遗传算法的工作细节。书，详尽地介绍遗传算法的工作细节。书，详尽地介绍遗传算法的工作细节。1996 1996 1996 1996年年年年
14、Z.Michalewicz Z.Michalewicz Z.Michalewicz Z.Michalewicz的专著遗传算法的专著遗传算法的专著遗传算法的专著遗传算法+数据结构数据结构数据结构数据结构=进化程序进化程序进化程序进化程序深入讨论了遗传算法的各种专门问题。同年，深入讨论了遗传算法的各种专门问题。同年，深入讨论了遗传算法的各种专门问题。同年，深入讨论了遗传算法的各种专门问题。同年，T.BackT.BackT.BackT.Back的专著进化的专著进化的专著进化的专著进化算法的理论与实践：进化策略、进化规划、遗传算法深入阐明进化算法的理论与实践：进化策略、进化规划、遗传算法深入阐明进化算
15、法的理论与实践：进化策略、进化规划、遗传算法深入阐明进化算法的理论与实践：进化策略、进化规划、遗传算法深入阐明进化算法的许多理论问题。算法的许多理论问题。算法的许多理论问题。算法的许多理论问题。1992 1992 1992 1992年，年，年，年，KozaKozaKozaKoza出版专著出版专著出版专著出版专著Genetic Programming:on the Genetic Programming:on the Genetic Programming:on the Genetic Programming:on the Programming of Computer by Means of
16、Natural SelectionProgramming of Computer by Means of Natural SelectionProgramming of Computer by Means of Natural SelectionProgramming of Computer by Means of Natural Selection，该书，该书，该书，该书全面介绍了遗传规划的原理及应用实例，表明遗传规划己成为进化算全面介绍了遗传规划的原理及应用实例，表明遗传规划己成为进化算全面介绍了遗传规划的原理及应用实例，表明遗传规划己成为进化算全面介绍了遗传规划的原理及应用实例，表明遗传
17、规划己成为进化算法的一个重要分支。法的一个重要分支。法的一个重要分支。法的一个重要分支。1994 1994 1994 1994年，年，年，年，KozaKozaKozaKoza又出版第二部专著又出版第二部专著又出版第二部专著又出版第二部专著Genetic Programming Genetic Programming Genetic Programming Genetic Programming:Automatic Discovery of Reusable Programs:Automatic Discovery of Reusable Programs:Automatic Discovery
18、 of Reusable Programs:Automatic Discovery of Reusable Programs，提出自动定义函，提出自动定义函，提出自动定义函，提出自动定义函数的新概念，在遗传规划中引入子程序的新技术。同年，数的新概念，在遗传规划中引入子程序的新技术。同年，数的新概念，在遗传规划中引入子程序的新技术。同年，数的新概念，在遗传规划中引入子程序的新技术。同年，K.E.KinnearK.E.KinnearK.E.KinnearK.E.Kinnear主编主编主编主编Advances in Genetic ProgrammingAdvances in Genetic Pro
19、grammingAdvances in Genetic ProgrammingAdvances in Genetic Programming，汇集许多研究工作者有，汇集许多研究工作者有，汇集许多研究工作者有，汇集许多研究工作者有关应用遗传规划的经验和技术。关应用遗传规划的经验和技术。关应用遗传规划的经验和技术。关应用遗传规划的经验和技术。第八页，共45页。1.4 1.4 基本遗传算法（基本遗传算法（SGASGA）1.4.1 1.4.1 基本遗传算法的构成要素基本遗传算法的构成要素(1)(1)染色体编码方法染色体编码方法 基本遗传算法使用固定长度的二进制符基本遗传算法使用固定长度的二进制符号串来
20、表示群体中的个体，其等位基因由二号串来表示群体中的个体，其等位基因由二值符号集值符号集00，11组成。初始群体中各个个体组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：的基因值用均匀分布的随机数来生成。如：100111001000101101100111001000101101，就可表示一个个体，就可表示一个个体，该个体的染色体长度是该个体的染色体长度是1818。(2)(2)个体适应度评价个体适应度评价 基本遗传算法按与个体适应度成正比的基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个
21、代群体中的机会多少。为正确计算这个(zh(zh ge)ge)概率，这里要求所有个体的适应度必须为概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。函数值为负数时的处理方法。第九页，共45页。(3)遗传算子遗传算子 基本遗传算法使用下述三种遗传算子：基本遗传算法使用下述三种遗传算子：选择运算：使用比例选择算子；选择运算：使用比例选择算子；交叉运算：使用单点交叉
22、算子；交叉运算：使用单点交叉算子；变异运算：使用基本位变异算子。变异运算：使用基本位变异算子。(4)基本遗传算法的运行参数基本遗传算法的运行参数 基本遗传算法有下述基本遗传算法有下述4个运行参数需要提前设定：个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取：群体大小，即群体中所含个体的数量，一般取20-100。T：遗传运算的终止：遗传运算的终止(zhngzh)进化代数，一般取进化代数，一般取100-500 pc：交叉概率，一般取：交叉概率，一般取0.4-0.99 pm：变异概率，一般取：变异概率，一般取 0.0001-0.1说明说明:这这4个运行参数对遗传算法的求解结果和求
23、解效率都有一定的影响，但目前尚无合理选择它们个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。取值大小或取值范围。第十页，共45页。1.4.2 基本遗传算法的形式化定义基本遗传算法的形式化定义 基本遗传算法可定义为一个基本遗传算法可定义为一个(y)7元组：元组：GA (M,F,s,c,m,pc,pm)M群体大小；群体大小；F个体适应度评价函数；个体适应度评价函数；s选择操作算子；选择操
24、作算子；c交叉操作算子：交叉操作算子：m变异操作算子；变异操作算子；pc交叉概率；交叉概率；pm变异概率；变异概率；第十一页，共45页。1.4.3 基本遗传算法的实现基本遗传算法的实现（1）编码与解码编码与解码 假设某一参数的取值范围是假设某一参数的取值范围是umin,umax，我们用长度为，我们用长度为的二进制编码的二进制编码符号串来表示该参数，则它总共能够产生符号串来表示该参数，则它总共能够产生 2种不同种不同(b tn)的编码，参数的编码，参数编码时的对应关系如下：编码时的对应关系如下：00000000000000000 umin 00000000000000011 umin+00000
25、000000000102 umin+2 1111111111111111=21 umax 其中，其中，为二进制编码的编码精度为二进制编码的编码精度(jn d)(jn d)，其公，其公式为：式为：=u umaxmax u uminmin2 2 1 1 第十二页，共45页。x=umin+(bi 2i-1)1 1i=lUmax umin2l 1 假设某一个假设某一个(y)(y)体的编码是：体的编码是：x x：bl bl-1 bl-2b2b1 bl bl-1 bl-2b2b1 则对应的解码公式为：则对应的解码公式为：第十三页，共45页。例例 设设 -3.0 x 12.1 ,精度精度(jn d)要求要求
26、=1/10000，由公式：，由公式：Umax umin2l=+11/1000012.1+3.0+1=151001 即：即：217 151001 218 x需要需要(xyo)18位位 0/1 符号表示。符号表示。如：如：010001001011010000 解码：解码：x=umin+(bi 2i-1)1i=lUmax umin2l 1=-0.3+70352=-0.3+70352(12.1+3)/(2(12.1+3)/(21818-1)-1)=1.052426=1.052426 =Umax umin2l 1 得：得：第十四页，共45页。（2 2）个体适应度评价个体适应度评价个体适应度评价个体适应度
27、评价 (1)(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度应度应度应度F(X)F(X)就等于相应就等于相应就等于相应就等于相应(xingyng)(xingyng)的目标函数值的目标函数值的目标函数值的目标函数值f(X)f(X)，即：，即：，即：，即：F(X)F(X)f(X)f(X)(2)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负
28、号就可将对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：其转化为求目标函数最大值的优化问题，即：其转化为求目标函数最大值的优化问题，即：其转化为求目标函数最大值的优化问题，即：min f(X)min f(X)max(-f(X)max(-f(X)但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函但实际优化
29、问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。第十五页，共45页。（3 3）选择算子选择算子选择算子选择算子 作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。作用：从当前代群体中选择出一些比较优良的个
30、体，并将其复制到下一代群体中。作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。比例选择算子：指个体被选中并遗传到下一代群体中的概率比例选择算子：指个体被选中并遗传到下一代群体中的概率比例选择算子：指个体被选中并遗传到下一代群体中的概率比例选择算子：指个体被选中并遗传到下一代群体中的概率(gil)(gil)与该个体的适应与该个体的适应与该个体的适应与该个体的适应度大小成正比。度大小成正比。度大小成正比。度大小成正比。轮盘选择：轮盘法的基本精神是：轮盘选择：轮盘法的基本精神是：轮盘选择：轮盘法的基本精神
31、是：轮盘选择：轮盘法的基本精神是：个体被选中的概率取决于个体的相个体被选中的概率取决于个体的相个体被选中的概率取决于个体的相个体被选中的概率取决于个体的相对适应度，显然，个体适应度愈高，对适应度，显然，个体适应度愈高，对适应度，显然，个体适应度愈高，对适应度，显然，个体适应度愈高，被选中的概率愈大。但是，适应度被选中的概率愈大。但是，适应度被选中的概率愈大。但是，适应度被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便小的个体也有可能被选中，以便小的个体也有可能被选中，以便小的个体也有可能被选中，以便(ybin)(ybin)增加下一代群体的多样性。增加下一代群体的多样性。增加下一代群体
32、的多样性。增加下一代群体的多样性。第十六页，共45页。（4 4）交叉算子交叉算子交叉算子交叉算子 作用：作用：作用：作用：通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。的主要手段。正是有了交换操作，群体的性态才多种多样。的主要手段。正是有了交换操作，群体的性态才多种多样。的主要手段。正是有了交换操作，群体的性态才多种多样。单点交叉算子的具体计算过程如下：单点交
33、叉算子的具体计算过程如下：单点交叉算子的具体计算过程如下：单点交叉算子的具体计算过程如下：.对群体中的个体进行两两随机配对。对群体中的个体进行两两随机配对。对群体中的个体进行两两随机配对。对群体中的个体进行两两随机配对。.每一对相互配对的个体，随机设置某一基因座之后每一对相互配对的个体，随机设置某一基因座之后每一对相互配对的个体，随机设置某一基因座之后每一对相互配对的个体，随机设置某一基因座之后(zhhu)(zhhu)的位置为交的位置为交的位置为交的位置为交叉点。叉点。叉点。叉点。.对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的
34、交叉概率对每一对相互配对的个体，依设定的交叉概率pcpc在其交叉点处相互交换在其交叉点处相互交换在其交叉点处相互交换在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。两个个体的部分染色体，从而产生出两个新的个体。两个个体的部分染色体，从而产生出两个新的个体。两个个体的部分染色体，从而产生出两个新的个体。单点交叉单点交叉A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00第十七页，共45页。（5 5）变异算子）变异算子）变异算子）变异算子 基本位变异算子：最简单和最基本的变异操作算子。基本位变异算子：最简单和最基本的变异操作
35、算子。基本位变异算子：最简单和最基本的变异操作算子。基本位变异算子：最简单和最基本的变异操作算子。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为作的某一基因座上的原有基因值为作的某一基因座上的原有基因值为作的某一基因座上的原有基因值为0 0，则变异操作将该基因值变为，则变异操作将该基因值变为，则变异操作将该基因值变为，则变异操作将该基因值变为1 1，
36、反之，反之，反之，反之，若原有基因值为若原有基因值为若原有基因值为若原有基因值为1 1，则变异操作将其变为，则变异操作将其变为，则变异操作将其变为，则变异操作将其变为0 0。具体执行过程：具体执行过程：具体执行过程：具体执行过程：.对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率pmpm指定其为变异点。指定其为变异点。指定其为变异点。指定其为变异点。.对每一个指定的变异点，对其基因值做取反运算对每一个指定的变异点，对其基因值做取反运算对每一个指定的变异点，对其基因值做取反运算对每一个指定的变异点，对其基因值做取反运
37、算(yn sun)(yn sun)或用其它等位基或用其它等位基或用其它等位基或用其它等位基因值来代替，从而产生出一个新的个体。因值来代替，从而产生出一个新的个体。因值来代替，从而产生出一个新的个体。因值来代替，从而产生出一个新的个体。A A：1010 1 01010 A1010 1 01010 A：1010 0 010101010 0 01010 变异变异(biny)点点基本基本(jbn)位变异位变异第十八页，共45页。开始开始Gen=0编码编码随机产生随机产生M个初始个体个初始个体满足终止条件满足终止条件?计算群体中各个体适应度计算群体中各个体适应度从左至右依次执行遗传算子从左至右依次执行遗
38、传算子j=0j=0j=0根据适应度选择复制个体根据适应度选择复制个体选择两个交叉个体选择两个交叉个体选择个体变异点选择个体变异点执行变异执行变异执行交叉执行交叉执行复制执行复制将复制的个体添入将复制的个体添入新群体中新群体中将交叉后的两个新个体将交叉后的两个新个体添入新群体中添入新群体中将变异后的个体添入将变异后的个体添入新群体中新群体中j=j+1j=j+2j=j+1 j=M?j=pcM?j=pmLM?Gen=Gen+1输出结果输出结果终止终止YNYYYNNNpcpm1.4.4 算法算法(sun f)流流程图程图第十九页，共45页。1.5 1.5 遗传算法的特点遗传算法的特点(tdin)(td
39、in)（1 1）群体搜索，易于并行化处理；）群体搜索，易于并行化处理；（2 2）不是盲目穷举，而是启发式搜索；）不是盲目穷举，而是启发式搜索；（3 3）适应度函数不受连续、可微等条件的约束，适用范围）适应度函数不受连续、可微等条件的约束，适用范围很广。很广。遗传算法的本质：对染色体模式所进行的一系列运算，即遗传算法的本质：对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用中，利用(lyng)(lyng)交叉算子进行模式重组，利用交叉算子进行模式重组，利用(lyng)(lyng)变异算子进行模式突变。通过
40、这些遗传操作，模式逐步向变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。较好的方向进化，最终得到问题的最优解。第二十页，共45页。1.6 1.6 遗传算法的收敛性分析遗传算法的收敛性分析(fnx)(fnx)遗传算法要实现全局收敛，首先要求遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作解，其次算法必须由保优操作(cozu)(cozu)来来防止最优解的遗失。与算法收敛性有关的防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作因素主要包括种群规模、选择操作(co
41、zu)(cozu)、交叉概率和变异概率。、交叉概率和变异概率。第二十一页，共45页。(1)(1)种群种群(zhn qn)(zhn qn)规模对收敛性的影响规模对收敛性的影响 通常，种群太小则不能提供足够的采样点，以致算法性通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算敛的发生，但无疑会增加计算(j sun)(j sun)量，造成收敛时间量，造成收敛时间太长，表现为收敛速度缓慢。太长，表现为收敛速度缓慢。(2)(2)选择操作选择操作(cozu)(cozu)对收敛性的影响
42、对收敛性的影响 选择操作使高适应度个体能够以更大的概率生存，从而提选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率操作，使之直接进入下一代，最终可使遗传算法以概率1 1收敛收敛于全局最优解。于全局最优解。第二十二页，共45页。(3)(3)交叉交叉(jioch)(jioch)概率对收敛性的影响概率对收敛性的影响 交叉操作用于个体对，产生新的个
43、体，实质上是在解空间交叉操作用于个体对，产生新的个体，实质上是在解空间(kngjin)(kngjin)中进行有效搜索。交叉概率太大时，种群中个体更中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。敛。(4)(4)变异概率变异概率(gil)(gil)对收敛性的影响对收敛性的影响 变异操作是对种群模式的扰动，有利于增加种群的多样性变异操作是对种群模式的扰动，有利于增加种群的多样性 。
44、但是，变异概率太小则很难产生新模式，变异概率太大则会。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。使遗传算法成为随机搜索算法。第二十三页，共45页。1.7 1.7 遗传算法研究遗传算法研究(ynji)(ynji)的主要问题的主要问题(1)(1)局部最优局部最优(2)(2)收敛速度问题收敛速度问题(3)(3)正确性问题正确性问题(4)(4)算法的实现性问题算法的实现性问题改进：编码方式、遗传改进：编码方式、遗传(ychun)(ychun)算子、控算子、控制参数。制参数。第二十四页，共45页。1.8 1.8 遗传算法的应用遗传算法的应用 遗传算法提供了一种求解复
45、杂系统优化问遗传算法提供了一种求解复杂系统优化问题题(wnt)(wnt)的通用框架，它不依赖于问题的通用框架，它不依赖于问题(wnt)(wnt)的具体领域，对问题的具体领域，对问题(wnt)(wnt)的种类有很强的鲁的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：法的一些主要应用领域：(1)(1)函数优化函数优化 函数优化是遗传算法的经典应用领域，也函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于一是对遗传算法进行性能评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题些非线性、多模型
46、、多目标的函数优化问题(wnt)(wnt)，用其他优化方法较难求解，用遗传算，用其他优化方法较难求解，用遗传算法可以方便地得到较好的结果。法可以方便地得到较好的结果。(2)(2)组合优化组合优化 随着问题随着问题(wnt)(wnt)规模的增大，组合优化规模的增大，组合优化问题问题(wnt)(wnt)的搜索空间也急剧扩大，有时在目的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题精确最优解。对这类复杂问题(wnt)(wnt)，人们己，人们己意识到应把主要精力放在寻求其满意解上，而遗意识到应把主要精力放在寻求
47、其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的证明，遗传算法对于组合优化中的NPNP完全问题完全问题(wnt)(wnt)非常有效。例如，遗传算法已经在求解非常有效。例如，遗传算法已经在求解旅行商问题旅行商问题(wnt)(wnt)、背包问题、背包问题(wnt)(wnt)、装箱问、装箱问题题(wnt)(wnt)、图形划分问题、图形划分问题(wnt)(wnt)等方面得到成等方面得到成功的应用。功的应用。第二十五页，共45页。(3)(3)生产调度问题生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确生产
48、调度问题在很多情况下所建立起来的数学模型难以精确(jngqu)(jngqu)求解，求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。度、生产规划、任务分配等方面遗传算法
49、都得到了有效的应用。(4)(4)自动控制自动控制 在自动控制领域中很多与优化相关的问题需要求解，遗传算法已在其中得到在自动控制领域中很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗
50、传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。域中应用的可能性。第二十六页，共45页。(5)(5)机器人学机器人学 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、用领域。例如，遗传算法