《张砦-遗传算法在多目标优化中的应用培训讲学》由会员分享，可在线阅读，更多相关《张砦-遗传算法在多目标优化中的应用培训讲学（45页珍藏版）》请在金锄头文库上搜索。
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)( (选择、交叉和变异选择、交叉和变异) )对这些个体进行组合，产生新一代对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。的候选解群，重复此过程，直到满足某种收敛指标为止。 第五页，
6、共45页。1.3 1.3 遗传算法的发展遗传算法的发展 (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.Hollan
8、d教教授又提出模式理论，它成为遗传算法的主要理论授又提出模式理论，它成为遗传算法的主要理论基础。基础。 1967 1967年，年，BagleyBagley发表了关于遗传算法应用的发表了关于遗传算法应用的论文，在其论文中首次使用论文，在其论文中首次使用“遗传算法（遗传算法（ Genetic AlgorithmGenetic Algorithm）”一词。一词。第六页，共45页。 (2) (2) 成长期成长期 (70 (70年代中期至年代中期至8080年代末期年代末期) ) 1975 1975年，年，J.H.HollandJ.H.Holland教授的专著教授的专著Adaptation in Natu
9、ral and Adaptation in Natural and Artificial 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.Goldbe
11、rgD.E.Goldberg博士出版专著博士出版专著Genetic Algorithmsin SearchGenetic Algorithmsin Search，Optimization and Machine Optimization and Machine LearningLearning，全面、系统地介绍遗传算法，使这一技术得到普及与推广。，全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为遗传算法的教科书。该书被人们视为遗传算法的教科书。 1985 1985年，在美国举行第一届遗传算法国际学术会议年，在美国举行第一届遗传算法国际学术会议(International Co
12、nference on Genetic Algorithms(International Conference on Genetic Algorithms，简称，简称ICGAICGA），），与会者交流运用遗传算法的经验。随后，每与会者交流运用遗传算法的经验。随后，每2 2年左右都举行一次这种会年左右都举行一次这种会议。议。第七页，共45页。(3) (3) (3) (3) 发展发展发展发展(fzhn)(fzhn)(fzhn)(fzhn)期期期期(90(90(90(90年代以后年代以后年代以后年代以后) ) ) ) 90 90 90 90年代，遗传算法不断地向广度和深度发展年代，遗传算法不断地向广
13、度和深度发展年代，遗传算法不断地向广度和深度发展年代，遗传算法不断地向广度和深度发展(fzhn)(fzhn)(fzhn)(fzhn)。 1991 1991 1991 1991年，年，年，年，D.LawrenceD.LawrenceD.LawrenceD.Lawrence出版出版出版出版Handbook of Genetic AlgorithmsHandbook of Genetic AlgorithmsHandbook of Genetic AlgorithmsHandbook of Genetic Algorithms一一一一书，详尽地介绍遗传算法的工作细节。书，详尽地介绍遗传算法的工作细节
14、。书，详尽地介绍遗传算法的工作细节。书，详尽地介绍遗传算法的工作细节。 1996 1996 1996 1996年年年年 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 Progr
16、amming:on the Genetic Programming:on the Programming of Computer by Means of 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
18、 Reusable Programs:Automatic Discovery of Reusable Programs:Automatic Discovery of Reusable Programs:Automatic Discovery of Reusable Programs，提出自动定义函，提出自动定义函，提出自动定义函，提出自动定义函数的新概念，在遗传规划中引入子程序的新技术。同年，数的新概念，在遗传规划中引入子程序的新技术。同年，数的新概念，在遗传规划中引入子程序的新技术。同年，数的新概念，在遗传规划中引入子程序的新技术。同年，K.E.KinnearK.E.KinnearK.E.K
19、innearK.E.Kinnear主编主编主编主编Advances in Genetic ProgrammingAdvances in Genetic ProgrammingAdvances in Genetic ProgrammingAdvances in Genetic Programming，汇集许多研究工作者有，汇集许多研究工作者有，汇集许多研究工作者有，汇集许多研究工作者有关应用遗传规划的经验和技术。关应用遗传规划的经验和技术。关应用遗传规划的经验和技术。关应用遗传规划的经验和技术。第八页，共45页。1.4 1.4 基本遗传算法（基本遗传算法（SGASGA）1.4.1 1.4.1 基
20、本遗传算法的构成要素基本遗传算法的构成要素(1) (1) 染色体编码方法染色体编码方法 基本遗传算法使用固定长度的二进制符基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二号串来表示群体中的个体，其等位基因由二值符号集值符号集00，11组成。初始群体中各个个体组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：的基因值用均匀分布的随机数来生成。如：100111001000101101100111001000101101，就可表示一个个体，就可表示一个个体，该个体的染色体长度是该个体的染色体长度是1818。(2) (2) 个体适应度评价个体适应度评价 基本遗传算法
21、按与个体适应度成正比的基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个代群体中的机会多少。为正确计算这个(zh (zh ge)ge)概率，这里要求所有个体的适应度必须为概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。函数值为负数时的处理方法。第九页，共45页。(
22、3) 遗传算子遗传算子 基本遗传算法使用下述三种遗传算子：基本遗传算法使用下述三种遗传算子： 选择运算：使用比例选择算子；选择运算：使用比例选择算子； 交叉运算：使用单点交叉算子；交叉运算：使用单点交叉算子； 变异运算：使用基本位变异算子。变异运算：使用基本位变异算子。 (4) 基本遗传算法的运行参数基本遗传算法的运行参数 基本遗传算法有下述基本遗传算法有下述4个运行参数需要提前设定：个运行参数需要提前设定： M：群体大小，即群体中所含个体的数量，一般取：群体大小，即群体中所含个体的数量，一般取20-100。 T：遗传运算的终止：遗传运算的终止(zhngzh)进化代数，一般取进化代数，一般取1
23、00 - 500 pc：交叉概率，一般取：交叉概率，一般取0.4 - 0.99 pm：变异概率，一般取：变异概率，一般取 0.0001 - 0.1说明说明:这这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。取值大小或取值范围。第十页，共45页。1.4.2 基本遗传算法的形式化定义基本遗传算法的形式化定义
24、 基本遗传算法可定义为一个基本遗传算法可定义为一个(y )7元组：元组： GA (M, F, s, c, m, pc, pm ) M群体大小；群体大小； F个体适应度评价函数；个体适应度评价函数； s选择操作算子；选择操作算子； c交叉操作算子：交叉操作算子： m变异操作算子；变异操作算子； pc交叉概率；交叉概率； pm变异概率；变异概率；第十一页，共45页。1.4.3 基本遗传算法的实现基本遗传算法的实现 （1） 编码与解码编码与解码 假设某一参数的取值范围是假设某一参数的取值范围是umin , umax，我们用长度为，我们用长度为的二进制编码的二进制编码符号串来表示该参数，则它总共能够产
25、生符号串来表示该参数，则它总共能够产生 2种不同种不同(b tn)的编码，参数的编码，参数编码时的对应关系如下：编码时的对应关系如下： 00000000000000000 umin 00000000000000011 umin + 00000000000000102 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 um
26、in2l 1 假设某一个假设某一个(y )(y )体的编码是：体的编码是： x x： bl bl-1 bl-2b2b1 bl bl-1 bl-2b2b1 则对应的解码公式为：则对应的解码公式为：第十三页，共45页。例例 设设 -3.0 x 12.1 , 精度精度(jn d)要求要求 =1/10000，由公式：，由公式： Umax umin2l =+ 11/1000012.1 + 3.0+ 1= 151001 即：即： 217 151001 218 x需要需要(xyo)18位位 0/1 符号表示。符号表示。 如：如：010001001011010000 解码：解码： x = umin + ( b
27、i 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） 个体适应度评价个体适应度评价个体适应度评价个体适应度评价 (1) (1) 当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适当优化目标是求函数最大
28、值，并且目标函数总取正值时，可以直接设定个体的适应度应度应度应度F(X)F(X)就等于相应就等于相应就等于相应就等于相应(xingyng)(xingyng)的目标函数值的目标函数值的目标函数值的目标函数值f(X)f(X)，即：，即：，即：，即： F(X) F(X)f(X) f(X) (2) (2) 对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最
29、大值的优化问题，即：其转化为求目标函数最大值的优化问题，即：其转化为求目标函数最大值的优化问题，即：其转化为求目标函数最大值的优化问题，即：min f(X)min f(X)max (-f(X) max (-f(X) 但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。数最小值，显然上面两式保
30、证不了所有情况下个体的适应度都是非负数这个要求。数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。 第十五页，共45页。（3 3） 选择算子选择算子选择算子选择算子 作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。 比例选择算子：指个体被选中并遗传到下一代群体中的概
31、率比例选择算子：指个体被选中并遗传到下一代群体中的概率比例选择算子：指个体被选中并遗传到下一代群体中的概率比例选择算子：指个体被选中并遗传到下一代群体中的概率(gil)(gil)与该个体的适应与该个体的适应与该个体的适应与该个体的适应度大小成正比。度大小成正比。度大小成正比。度大小成正比。轮盘选择：轮盘法的基本精神是：轮盘选择：轮盘法的基本精神是：轮盘选择：轮盘法的基本精神是：轮盘选择：轮盘法的基本精神是：个体被选中的概率取决于个体的相个体被选中的概率取决于个体的相个体被选中的概率取决于个体的相个体被选中的概率取决于个体的相对适应度，显然，个体适应度愈高，对适应度，显然，个体适应度愈高，对适应
32、度，显然，个体适应度愈高，对适应度，显然，个体适应度愈高，被选中的概率愈大。但是，适应度被选中的概率愈大。但是，适应度被选中的概率愈大。但是，适应度被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便小的个体也有可能被选中，以便小的个体也有可能被选中，以便小的个体也有可能被选中，以便(ybin)(ybin)增加下一代群体的多样性。增加下一代群体的多样性。增加下一代群体的多样性。增加下一代群体的多样性。第十六页，共45页。（4 4） 交叉算子交叉算子交叉算子交叉算子 作用：作用：作用：作用： 通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体通过交叉，子代的基因值不同于父代。交换是
33、遗传算法产生新个体通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。的主要手段。正是有了交换操作，群体的性态才多种多样。的主要手段。正是有了交换操作，群体的性态才多种多样。的主要手段。正是有了交换操作，群体的性态才多种多样。 单点交叉算子的具体计算过程如下：单点交叉算子的具体计算过程如下：单点交叉算子的具体计算过程如下：单点交叉算子的具体计算过程如下： . . 对群体中的个体进行两两随机配对。对群体中的个体进行两两随机配对。对群体中的个体进行两两随机配对。对群体中的个体进行两两
34、随机配对。 . . 每一对相互配对的个体，随机设置某一基因座之后每一对相互配对的个体，随机设置某一基因座之后每一对相互配对的个体，随机设置某一基因座之后每一对相互配对的个体，随机设置某一基因座之后(zhhu)(zhhu)的位置为交的位置为交的位置为交的位置为交叉点。叉点。叉点。叉点。 . . 对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率pcpc在其交叉点处相互交在其交叉点处相互交在其交叉点处相互交在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。换两个个体的部分染
35、色体，从而产生出两个新的个体。换两个个体的部分染色体，从而产生出两个新的个体。换两个个体的部分染色体，从而产生出两个新的个体。 单点交叉单点交叉A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00第十七页，共45页。（5 5）变异算子）变异算子）变异算子）变异算子 基本位变异算子：最简单和最基本的变异操作算子。基本位变异算子：最简单和最基本的变异操作算子。基本位变异算子：最简单和最基本的变异操作算子。基本位变异算子：最简单和最基本的变异操作算子。 对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操对于基本遗传算法中用二进制
36、编码符号串所表示的个体，若需要进行变异操对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为作的某一基因座上的原有基因值为作的某一基因座上的原有基因值为作的某一基因座上的原有基因值为0 0，则变异操作将该基因值变为，则变异操作将该基因值变为，则变异操作将该基因值变为，则变异操作将该基因值变为1 1，反之，反之，反之，反之，若原有基因值为若原有基因值为若原有基因值为若原有基因值为1 1，则变异操作将其变为，则变异操作将其变为，则变异操作将其变为，则变异操作将其变为0 0。 具体执行过程：
37、具体执行过程：具体执行过程：具体执行过程： . .对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率pmpm指定其为变异点。指定其为变异点。指定其为变异点。指定其为变异点。 . .对每一个指定的变异点，对其基因值做取反运算对每一个指定的变异点，对其基因值做取反运算对每一个指定的变异点，对其基因值做取反运算对每一个指定的变异点，对其基因值做取反运算(yn sun)(yn sun)或用其它等位基因或用其它等位基因或用其它等位基因或用其它等位基因值来代替，从而产生出一个新的个体。值来代替，从而产生出一个新的个体。值来代替，
38、从而产生出一个新的个体。值来代替，从而产生出一个新的个体。 A A：1010 1 01010 A1010 1 01010 A：1010 0 010101010 0 01010 变异变异(biny)点点基本基本(jbn)位变异位变异第十八页，共45页。开始开始Gen=0编码编码随机产生随机产生M个初始个体个初始个体满足终止条件满足终止条件?计算群体中各个体适应度计算群体中各个体适应度从左至右依次执行遗传算子从左至右依次执行遗传算子j = 0j = 0j = 0根据适应度选择复制个体根据适应度选择复制个体选择两个交叉个体选择两个交叉个体选择个体变异点选择个体变异点执行变异执行变异执行交叉执行交叉执
39、行复制执行复制将复制的个体添入将复制的个体添入新群体中新群体中将交叉后的两个新个体将交叉后的两个新个体添入新群体中添入新群体中将变异后的个体添入将变异后的个体添入新群体中新群体中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) (tdin) （1 1）群体搜索，易于并行化处理；）群体搜索，易于并行化处理； （2 2）不是盲目穷举，而是启发式搜索；）不是盲目穷举，而
40、是启发式搜索；（3 3）适应度函数不受连续、可微等条件的约束，适用范围）适应度函数不受连续、可微等条件的约束，适用范围很广。很广。 遗传算法的本质：对染色体模式所进行的一系列运算，即遗传算法的本质：对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用中，利用(lyng)(lyng)交叉算子进行模式重组，利用交叉算子进行模式重组，利用(lyng)(lyng)变异算子进行模式突变。通过这些遗传操作，模式逐步向变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。较好的方向进化
41、，最终得到问题的最优解。 第二十页，共45页。1.6 1.6 遗传算法的收敛性分析遗传算法的收敛性分析(fnx)(fnx) 遗传算法要实现全局收敛，首先要求遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作解，其次算法必须由保优操作(cozu)(cozu)来来防止最优解的遗失。与算法收敛性有关的防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作因素主要包括种群规模、选择操作(cozu)(cozu)、交叉概率和变异概率。、交叉概率和变异概率。 第二十一页，共45页。(1) (1) 种群种群(zhn q
42、n)(zhn qn)规模对收敛性的影响规模对收敛性的影响 通常，种群太小则不能提供足够的采样点，以致算法性通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算敛的发生，但无疑会增加计算(j sun)(j sun)量，造成收敛时间量，造成收敛时间太长，表现为收敛速度缓慢。太长，表现为收敛速度缓慢。(2)(2)选择操作选择操作(cozu)(cozu)对收敛性的影响对收敛性的影响 选择操作使高适应度个体能够以更大的概率生存，从而提选择操作使高适应度个体能够以更大的概率生存，从而提
43、高了遗传算法的全局收敛性。如果在算法中采用最优保存策高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率操作，使之直接进入下一代，最终可使遗传算法以概率1 1收敛收敛于全局最优解。于全局最优解。第二十二页，共45页。(3)(3)交叉交叉(jioch)(jioch)概率对收敛性的影响概率对收敛性的影响 交叉操作用于个体对，产生新的个体，实质上是在解空间交叉操作用于个体对，产生新的个体，实质上是在解空间(kngjin)(kngjin)中进行有效搜索
44、。交叉概率太大时，种群中个体更中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。敛。 (4)(4)变异概率变异概率(gil)(gil)对收敛性的影响对收敛性的影响 变异操作是对种群模式的扰动，有利于增加种群的多样性变异操作是对种群模式的扰动，有利于增加种群的多样性 。但是，变异概率太小则很难产生新模式，变异概率太大则会。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算
45、法成为随机搜索算法。使遗传算法成为随机搜索算法。 第二十三页，共45页。1.7 1.7 遗传算法研究遗传算法研究(ynji)(ynji)的主要问题的主要问题(1)(1)局部最优局部最优(2)(2)收敛速度问题收敛速度问题(3)(3)正确性问题正确性问题(4)(4)算法的实现性问题算法的实现性问题改进：编码方式、遗传改进：编码方式、遗传(ychun)(ychun)算子、控算子、控制参数。制参数。第二十四页，共45页。1.8 1.8 遗传算法的应用遗传算法的应用 遗传算法提供了一种求解复杂系统优化问遗传算法提供了一种求解复杂系统优化问题题(wnt)(wnt)的通用框架，它不依赖于问题的通用框架，它
46、不依赖于问题(wnt)(wnt)的具体领域，对问题的具体领域，对问题(wnt)(wnt)的种类有很强的鲁的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：法的一些主要应用领域： (1) (1) 函数优化函数优化 函数优化是遗传算法的经典应用领域，也函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于一是对遗传算法进行性能评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题些非线性、多模型、多目标的函数优化问题(wnt)(wnt)，用其他优化方法较难求解，用遗传算，用其他优化方法较难求解，用遗
47、传算法可以方便地得到较好的结果。法可以方便地得到较好的结果。 (2) (2) 组合优化组合优化 随着问题随着问题(wnt)(wnt)规模的增大，组合优化规模的增大，组合优化问题问题(wnt)(wnt)的搜索空间也急剧扩大，有时在目的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题精确最优解。对这类复杂问题(wnt)(wnt)，人们己，人们己意识到应把主要精力放在寻求其满意解上，而遗意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践传算法是寻求这种满意解的最佳工具之一。实践
48、证明，遗传算法对于组合优化中的证明，遗传算法对于组合优化中的NPNP完全问题完全问题(wnt)(wnt)非常有效。例如，遗传算法已经在求解非常有效。例如，遗传算法已经在求解旅行商问题旅行商问题(wnt)(wnt)、背包问题、背包问题(wnt)(wnt)、装箱问、装箱问题题(wnt)(wnt)、图形划分问题、图形划分问题(wnt)(wnt)等方面得到成等方面得到成功的应用。功的应用。第二十五页，共45页。 (3) (3) 生产调度问题生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确生产调度问题在很多情况下所建立起来的数学模型难以精确(jngqu)(jngqu)求解，求解，即使经
49、过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。度、生产规划、任务分配等方面遗传算法都得到了有效的应用。 (4) (4) 自动控制自动控制 在自动控制领域中很多与优化相关的问题需
50、要求解，遗传算法已在其中得到在自动控制领域中很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领进行人工神经
51、网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。域中应用的可能性。第二十六页，共45页。(5) (5) 机器人学机器人学 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结
52、构优化和行为协调等方面得到研究和应用。机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。 (6) (6) 图像处理图像处理 图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武
53、之地，日前已在模式识别、图像恢复、这些图像处理中的优化计算方面找到了用武之地，日前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。图像边缘特征提取等方面得到了应用。(7) (7) 人工生命人工生命 人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造有行为的人造(rnzo)(rnzo)系统。自组织能力和自学习能力是人工生命的两大主要特系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工征。人工生命与遗传算法有着密切的关系，基于
54、遗传算法的进化模型是研究人工生命现象的重要基础理论。生命现象的重要基础理论。第二十七页，共45页。 虽然人工生命的研究尚处于启蒙阶段。但遗传算法已在其进化模型虽然人工生命的研究尚处于启蒙阶段。但遗传算法已在其进化模型(mxng)(mxng)、学习模型、学习模型(mxng)(mxng)、行为模型、行为模型(mxng)(mxng)、自组织模型、自组织模型(mxng)(mxng)等方面显示出了初步的应用能力，并且必将得到更为深入的应等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生
55、命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。发展。 (8) (8) 遗传编程遗传编程 Koza Koza发展了遗传编程的概念，他使用了以发展了遗传编程的概念，他使用了以LISPLISP语言所表示的编码方语言所表示的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。人工智能、机
56、器学习等领域。 (9) (9) 机器学习机器学习 学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；
57、人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。第二十八页，共45页。二、多目标二、多目标(mbio)优化问题优化问题描述描述1、工程问题大多是多目标优化问题；、工程问题大多是多目标优化问题；2、一般没有绝对、一般没有绝对(judu)的最优解，只有可行的最优解，只有可行解；解；3、可行解有多种组合可能；、可行解有多种组合可能；4、多个目标相互制约；、多个目标相互制约；5、求解需要充分了解约束之间的关系。、求解需要充分了解约束之间的关系。第二十九页，共45页。三、
58、实例三、实例1 Rosenbrock函数最值问题函数最值问题 求求 Rosenbrock函数的全局函数的全局(qunj)最最大值计算。大值计算。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 s.t. -2.048 xi 2.048 (xi=1,2)如图所示：如图所示：该函数有两个局部极大点，该函数有两个局部极大点，分别是分别是: f(2.048, -2048)=3897.7342 和和 f(-2.048,-2.0048)=3905.9262其中其中(qzhng)后者为全局最大点。后者为全局最大点。第三十页，共45页。下面介绍求解该问题的遗传算法的构造过程：下
59、面介绍求解该问题的遗传算法的构造过程：下面介绍求解该问题的遗传算法的构造过程：下面介绍求解该问题的遗传算法的构造过程：第一步：确定决策第一步：确定决策第一步：确定决策第一步：确定决策(juc)(juc)变量及其约束条件。变量及其约束条件。变量及其约束条件。变量及其约束条件。 s.t. -2.048 xi 2.048 (xi=1,2) s.t. -2.048 xi 2.048 (xi=1,2)第二步：确定适应度函数。第二步：确定适应度函数。第二步：确定适应度函数。第二步：确定适应度函数。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 max f(x1,x2) =
60、 100 (x12-x22)2 + (1-x1)2第三步：确定编码方法。第三步：确定编码方法。第三步：确定编码方法。第三步：确定编码方法。 用长度为用长度为用长度为用长度为l0l0位的二进制编码串来分别表示二个决策位的二进制编码串来分别表示二个决策位的二进制编码串来分别表示二个决策位的二进制编码串来分别表示二个决策(juc)(juc)变量变量变量变量x1,x2x1,x2。 lO lO位二进制编码串可以表示从位二进制编码串可以表示从位二进制编码串可以表示从位二进制编码串可以表示从0 0到到到到10231023之间的之间的之间的之间的10241024个不同的数，故将个不同的数，故将个不同的数，故将
61、个不同的数，故将x1,x2x1,x2的定义域离散化的定义域离散化的定义域离散化的定义域离散化为为为为10231023个均等的区域，包括两个端点在内共有个均等的区域，包括两个端点在内共有个均等的区域，包括两个端点在内共有个均等的区域，包括两个端点在内共有10241024个不同的离散点。从离散点个不同的离散点。从离散点个不同的离散点。从离散点个不同的离散点。从离散点-2.048-2.048到离到离到离到离散点散点散点散点2.0482.048，依次让它们分别对应于从，依次让它们分别对应于从，依次让它们分别对应于从，依次让它们分别对应于从0000000000(0)0000000000(0)到到到到11
62、11111111(1023)1111111111(1023)之间的二进制编码。之间的二进制编码。之间的二进制编码。之间的二进制编码。再将分别表示再将分别表示再将分别表示再将分别表示x1x1和和和和x2x2的二个的二个的二个的二个1010位长的二进制编码串连接在一起，组成一个位长的二进制编码串连接在一起，组成一个位长的二进制编码串连接在一起，组成一个位长的二进制编码串连接在一起，组成一个2020位长的二进制位长的二进制位长的二进制位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如编码串，它就构成了这个函数优化问题的染色体编码方法。例如编码串，它就构成了这个函数优化问题的染色体编
63、码方法。例如编码串，它就构成了这个函数优化问题的染色体编码方法。例如 X X：0000110111 11011 10001 0000110111 11011 10001 就表示一个个体的基因型。就表示一个个体的基因型。就表示一个个体的基因型。就表示一个个体的基因型。第三十一页，共45页。第四步：确定解码方法。第四步：确定解码方法。 解码时先将解码时先将20位长的二进制编码串切断位长的二进制编码串切断(qi dun)为二个为二个10位长的二进制编码串，位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为然后分别将它们转换为对应的十进制整数代码，分别记为y1和和y2。 依据前述个
64、体编码方法相对定义域的离散化方法可知，将代码依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变量转换为变量xi的解的解码公式为：码公式为：例如，对前述个体例如，对前述个体 X： 0000110111 11011 10001 它由这样的两个它由这样的两个(lin )代码所组成：代码所组成： y1= 55 y2 = 881 经上式的解码处理后，得到：经上式的解码处理后，得到： x1= -1.828 x2= 1.476 xi = 4.096 yi 1023 2.048 ( i = 1,2)第三十二页，共45页。 第五步：确定个体评价方法。第五步：确定个体评价方法。 由式由式 f(x1
65、,x2) = 100 (x12-x22)2 + (1-x1)2 可知，可知， Rosenbrock函数的值域总是函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有：目标函数值，并且不再对它作其他变换处理，即有： F(x) = f(x1,x2)第六步：设计遗传算子。第六步：设计遗传算子。 选择运算使用比例选择算子；选择运算使用比例选择算子； 交叉运算使用单点交叉算子；交叉运算使用单点交叉算子； 变异运算使用基本位变异算子。变异运算使用基本位变
66、异算子。第七步：确定遗传算法的运行参数第七步：确定遗传算法的运行参数(cnsh)。 对于本例，设定基本遗传算法的运行参数对于本例，设定基本遗传算法的运行参数(cnsh)如下：如下： 群体大小群体大小: M80 终止代数终止代数: T200 交叉概率：交叉概率：pc0.6 变异概率：变异概率：pm0.001第三十三页，共45页。 下图为其进化过程示例及运行下图为其进化过程示例及运行(ynxng)(ynxng)结果。结果。 图中两条曲线分别图中两条曲线分别(fnbi)为各代群体中个体适应度的最大值和平均值。为各代群体中个体适应度的最大值和平均值。第三十四页，共45页。(a)下图所示分别为初始群体、
67、第下图所示分别为初始群体、第5代群体、第代群体、第10代群体和第代群体和第100代群体中个体的分布情况代群体中个体的分布情况(qngkung)。 在图在图(a)中各个个体分布得比较均匀。中各个个体分布得比较均匀。第三十五页，共45页。 在图在图(b)中大量的个体分布在最优点中大量的个体分布在最优点(yudin)和次最优点和次最优点(yudin)附近。附近。(b)第三十六页，共45页。从图从图(c) 中可以看出中可以看出(kn ch)，次最优点也被淘汰。，次最优点也被淘汰。(c)第三十七页，共45页。从图从图(d)中可以看出，个体更加中可以看出，个体更加(gnji)集中在最优点附近。集中在最优点
68、附近。(d) 由该组图我们可以看出，随着进化过程的进行，群体由该组图我们可以看出，随着进化过程的进行，群体(qnt)中适应度较低的一些个中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的体被逐渐淘汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的最优点附近，从而最终就可搜索到问题的最优解。最优点附近，从而最终就可搜索到问题的最优解。第三十八页，共45页。四、实例四、实例(shl)2智能组卷智能组卷问题问题问题描述：根据不同约束需求，实现计算机自动试卷。对题库中问题描述：根据不同约束需求，实现计算机自动试卷。对题库中所有试题的选择情况进行
69、遗传编码，形成初始所有试题的选择情况进行遗传编码，形成初始(ch sh)染色体染色体种群，用遗传算法进化，获取满足约束条件要求的染色体（对种群，用遗传算法进化，获取满足约束条件要求的染色体（对应题库中试题的选择与否），进而从试题库中提取满足条件的应题库中试题的选择与否），进而从试题库中提取满足条件的试题组成试卷。试题组成试卷。约束条件：试卷总分、各章节分值、各题型分值、试卷难度、知约束条件：试卷总分、各章节分值、各题型分值、试卷难度、知识点要求、试题的难度系数、试卷形式、能力层次、试题区分识点要求、试题的难度系数、试卷形式、能力层次、试题区分度、答题时间。度、答题时间。第三十九页，共45页。一
70、条一条(y tio)染色体编码染色体编码v010000000000000000000000000000000100000000000010000000000010000000000010001100000000000000110110000000111000000000001100100000000000000000000000000000000000000000000000000000000100001000000000000000000000000000000000000000000000000111000000010000000100000000000000000000000000000
71、00010110100010101010000000000000000000000000000000000000000001000010000000000100001100100000001011011000000001000000000000010000000100011000000000001001100000000000010000010010000000010100000000000000000000000010000000000000000000000000000000000000000000000第四十页，共45页。主要参数的确定主要参数的确定(qudng)种群种群(zhn qn)大小的确定：大小的确定：20选择操作：轮盘选择操作：轮盘不采用交叉操作不采用交叉操作变异操作（单点）：概率为变异操作（单点）：概率为1。适应度函数适应度函数(hnsh)vnum_fix=(133/200)exp(log(20)*num_fix1)+(35/200)exp(log(20)*num_fix2)+(19/200)exp(log(20)*num_fix3)+(13/200)exp(log(20)*num_fix4)第四十一页，共45页。第四十二页，共45页。结果结果(ji gu)第四十三页，共45页。第四十四页，共45页。THE ENDTHE END第四十五页，共45页。
