第8章 遗传算法

1、第八章第八章 遗传算法遗传算法 Beijing University of Posts and Telecommunications.2 遗传算法（遗传算法（Genetic Algorithm，简称，简称GA）作为一种解决复杂问题）作为一种解决复杂问题的优化搜索方法，是由美国密执安大学的的优化搜索方法，是由美国密执安大学的John Holland教授首先提出教授首先提出来的（来的（Holland，1975）。遗传算法是以达尔文的生物进化论为启发）。遗传算法是以达尔文的生物进化论为启发而创建的，是一种基于进化论中优胜劣汰、自然选择、适者生存和物而创建的，是一种基于进化论中优胜劣汰、自然选择、适者

2、生存和物种遗传思想的优化算法。种遗传思想的优化算法。 遗传算法广泛应用于人工智能、机器学习、知识工程、函数优化、遗传算法广泛应用于人工智能、机器学习、知识工程、函数优化、自动控制、模式识别、图像处理、生物工程等众多领域。目前，遗传自动控制、模式识别、图像处理、生物工程等众多领域。目前，遗传算法正在向其它学科和领域渗透，正在形成遗传算法、神经网络和模算法正在向其它学科和领域渗透，正在形成遗传算法、神经网络和模糊控制相结合，从而构成一种新型的智能控制系统整体优化的结构形糊控制相结合，从而构成一种新型的智能控制系统整体优化的结构形式。式。 Beijing University of Posts an

3、d Telecommunications.38.1 遗传算法基本原理遗传算法基本原理 GA的基本思想来源于的基本思想来源于Darwin的进化论和的进化论和Mendel的遗传学说。的遗传学说。Darwin的进化论认为每一物种在不断的发展过程中都是越来越适应环的进化论认为每一物种在不断的发展过程中都是越来越适应环境。物种的每个个体的基本特征被后代所继承，但后代又不完全同于父境。物种的每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来。在某一环境中也是那代，这些新的变化，若适应环境，则被保留下来。在某一环境中也是那些更能适应环境的个体特征能被保留下来，这就

4、是适者生存的原理。些更能适应环境的个体特征能被保留下来，这就是适者生存的原理。 8.1.1 遗传算法的由来遗传算法的由来Beijing University of Posts and Telecommunications.48.1 遗传算法基本原理遗传算法基本原理 遗传算法的出发点是一个简单的群体遗传模型，该模型基于如下假遗传算法的出发点是一个简单的群体遗传模型，该模型基于如下假设：设：(1)染色体（基因型）由一固定长度的字符串组成，其中的每一位具有染色体（基因型）由一固定长度的字符串组成，其中的每一位具有有限数目的等位基因。有限数目的等位基因。(2)群体由有限数目的基因型组成。群体由有限数目

5、的基因型组成。(3)每一基因型有一相应的适应度（每一基因型有一相应的适应度（Fitness），表示该基因型生存与复），表示该基因型生存与复制的能力。适应度为大于零的实数，适应度越大表示生存能力越强。制的能力。适应度为大于零的实数，适应度越大表示生存能力越强。8.1.1 遗传算法的由来遗传算法的由来Beijing University of Posts and Telecommunications.58.1 遗传算法基本原理遗传算法基本原理 8.1.2.1 复制（复制（Reproduction） 复制复制(又称繁殖又称繁殖)，是从一个旧种群，是从一个旧种群( old population)中选择

6、生命力中选择生命力强的个体位串强的个体位串(或称字符串或称字符串)产生新种群的过程。或者说，复制是个体位产生新种群的过程。或者说，复制是个体位串根据其目标函数串根据其目标函数(即适应度函数即适应度函数)拷贝自己的过程。根据位串的适应度拷贝自己的过程。根据位串的适应度值拷贝位串意味着，具有较高适应度值的位串更有可能在下一代中产生值拷贝位串意味着，具有较高适应度值的位串更有可能在下一代中产生一个或多个后代。显然，这个操作是模仿自然选择现象，将达尔文的适一个或多个后代。显然，这个操作是模仿自然选择现象，将达尔文的适者生存理论应用于位串的复制，适应度值是该位串被复制或被淘汰的决者生存理论应用于位串的复

7、制，适应度值是该位串被复制或被淘汰的决定因素。定因素。8.1.2 遗传算法的基本操作遗传算法的基本操作Beijing University of Posts and Telecommunications.68.1 遗传算法基本原理遗传算法基本原理8.1.2.2 交叉（交叉（Crossover）交叉是在两个基因型之间进行的，指其中部分内容进行了互换。交叉是在两个基因型之间进行的，指其中部分内容进行了互换。 A = a1a2al 和和 B = b1b2bl若在位置若在位置i交换，则产生两个新的串交换，则产生两个新的串 Aa1albi+1bl 和和 Bb1blai+1al 8.1.2 遗传算法的基本

8、操作遗传算法的基本操作Beijing University of Posts and Telecommunications.78.1 遗传算法基本原理遗传算法基本原理8.1.2.3 变异（变异（Mutation） 若基因型中某个或某几个位置上的等位基因从一种状态跳变到另一种若基因型中某个或某几个位置上的等位基因从一种状态跳变到另一种状态（状态（0变为变为1或或1变为变为0），则称该基因型发生了变异。其中变异的），则称该基因型发生了变异。其中变异的位置也是随机的。位置也是随机的。8.1.2 遗传算法的基本操作遗传算法的基本操作Beijing University of Posts and Tel

9、ecommunications.88.1 遗传算法基本原理遗传算法基本原理8.1.2 遗传算法的基本操作遗传算法的基本操作遗传算法的基本步骤遗传算法的基本步骤 Beijing University of Posts and Telecommunications.98.1 遗传算法基本原理遗传算法基本原理（1）GA是对问题参数的编码（染色体）进行操作，而不是参数本身。是对问题参数的编码（染色体）进行操作，而不是参数本身。（2）GA计算简单，便于计算机编程，功能强。计算简单，便于计算机编程，功能强。（3）GA是从问题解的串集开始搜索，而不是从单个解开始，更有利于是从问题解的串集开始搜索，而不是从单

10、个解开始，更有利于搜索到全局最优解。搜索到全局最优解。（4）GA使用对象函数值（即适应值）这一信息进行搜索，而不需导数使用对象函数值（即适应值）这一信息进行搜索，而不需导数等其它信息。等其它信息。（5）GA的复制、交叉、变异这三个算子都是由概率决定的，而非确定的复制、交叉、变异这三个算子都是由概率决定的，而非确定性的。性的。（6）GA算法具有隐含的并行性，因而可通过大规模并行计算来提高计算法具有隐含的并行性，因而可通过大规模并行计算来提高计算速度。算速度。（7）GA更适合大规模复杂问题的优化，但解决简单问题效率并不高。更适合大规模复杂问题的优化，但解决简单问题效率并不高。8.1.3 遗传算法的

11、特点遗传算法的特点Beijing University of Posts and Telecommunications.108.1 遗传算法基本原理遗传算法基本原理图式：描述种群中在位串的某些确定位置上具有相似性的位串子集的相似图式：描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板。性模板。-H=*11*0*， 0111000 ，1110000 两个串在某些位上相似两个串在某些位上相似-一个长度为一个长度为l 的串，每一位只可取的串，每一位只可取0，1，则有，则有(2+1)l 个图式-在一个在一个N个串的群中最多有个串的群中最多有N*2l 种图式种图式定义定义8.1 图式图式H

12、的长度的长度(H)是指图式第一个确定位置和最后一个确定位置是指图式第一个确定位置和最后一个确定位置之间的距离。如之间的距离。如H*00*1*，则，则(H)=4。定义定义8.2 图式图式H的阶的阶(H)是指图式中固定串位的个数。如是指图式中固定串位的个数。如H*00*1*，则，则(H)=3。 8.1.4 遗传算法的理论基础遗传算法的理论基础Beijing University of Posts and Telecommunications.118.1 遗传算法基本原理遗传算法基本原理 图式定理（图式定理（Schema Theorem）：）： 对于某一种图式，在下一代串中将有多少串与这种图式匹配？

13、对于某一种图式，在下一代串中将有多少串与这种图式匹配？ m(H,t)t代群体中存在图式代群体中存在图式H的串的个数；的串的个数；f(H)t代群体中包含图式代群体中包含图式H的串的平均适应值；的串的平均适应值；ft代群体中所有串的平均适应值；代群体中所有串的平均适应值；l串的长度串的长度Pc交换概率交换概率Pm变异概率变异概率8.1.4 遗传算法的理论基础遗传算法的理论基础)(1)(1 ()(),() 1,(mcPHOlHPfHftHmtHmBeijing University of Posts and Telecommunications.128.1 遗传算法基本原理遗传算法基本原理 图式定理

14、（图式定理（Schema Theorem）：）： 对于某一种图式，在下一代串中将有多少串与这种图式匹配？对于某一种图式，在下一代串中将有多少串与这种图式匹配？ 图式定理是图式定理是GA算法的理论基础，它说明高适应值、长度短、阶数低的图算法的理论基础，它说明高适应值、长度短、阶数低的图式在后代中至少以指数增长包含该图式式在后代中至少以指数增长包含该图式H的串的数目。原因在于再生使高的串的数目。原因在于再生使高适应值的图式复制更多的后代，而简单的交换操作不易破坏长度短、阶数适应值的图式复制更多的后代，而简单的交换操作不易破坏长度短、阶数低的图式，而变异概率很小，一般不会影响这些重要图式。低的图式，

15、而变异概率很小，一般不会影响这些重要图式。8.1.4 遗传算法的理论基础遗传算法的理论基础)(1)(1 ()(),() 1,(mcPHOlHPfHftHmtHmBeijing University of Posts and Telecommunications.138.1 遗传算法基本原理遗传算法基本原理l图式定理是图式定理是GA算法的理论基础，它说明高适应值、长度短、阶数低的算法的理论基础，它说明高适应值、长度短、阶数低的图式在后代中至少以指数增长包含该图式图式在后代中至少以指数增长包含该图式H的串的数目。原因在于再生使的串的数目。原因在于再生使高适应值的图式复制更多的后代，而简单的交换操作

16、不易破坏长度短、阶高适应值的图式复制更多的后代，而简单的交换操作不易破坏长度短、阶数低的图式，而变异概率很小，一般不会影响这些重要图式。数低的图式，而变异概率很小，一般不会影响这些重要图式。l遗传算法是从父代最好的部分解中构造出越来越好的串，而不是去试验遗传算法是从父代最好的部分解中构造出越来越好的串，而不是去试验每一个可能的组合。长度短的、低阶的、高适应值的图式通过遗传操作复每一个可能的组合。长度短的、低阶的、高适应值的图式通过遗传操作复制、交叉、变异，再复制、再交叉、再变异的逐渐变化，形成潜在的适应制、交叉、变异，再复制、再交叉、再变异的逐渐变化，形成潜在的适应性较高的串。性较高的串。8.

17、1.4 遗传算法的理论基础遗传算法的理论基础Beijing University of Posts and Telecommunications.148.1 遗传算法基本原理遗传算法基本原理应用应用GA的几个要点的几个要点 ：（1）问题编码）问题编码 问题编码就是如何将优化问题描述成串的形式，需要考虑编码方法问题编码就是如何将优化问题描述成串的形式，需要考虑编码方法和串长等。和串长等。 （2）对象函数的确定。）对象函数的确定。 对象函数用于评价各串的性能。函数优化问题可直接将函数本身作对象函数用于评价各串的性能。函数优化问题可直接将函数本身作为对象函数。为对象函数。 （3）GA算法本身参数的确

18、定。算法本身参数的确定。 种群数目、交换概率、变异概率种群数目、交换概率、变异概率 等。等。8.1.4 遗传算法的理论基础遗传算法的理论基础Beijing University of Posts and Telecommunications.158.1 遗传算法基本原理遗传算法基本原理一类非线性优化问题的遗传算法：一类非线性优化问题的遗传算法：问题：问题：(1)找到有效且通用的编码方法，将问题的可能解编码成有限位的字符串。找到有效且通用的编码方法，将问题的可能解编码成有限位的字符串。根据编码方法定义一个适应度函数，用以测量和评价各解的性能。确定遗根据编码方法定义一个适应度函数，用以测量和评价各

19、解的性能。确定遗传算法的各个参数。传算法的各个参数。(2)由遗传算法寻找最佳串由遗传算法寻找最佳串(3)根据最佳串，给出实际问题的最优解根据最佳串，给出实际问题的最优解 8.1.5 用于优化问题的遗传算法用于优化问题的遗传算法ribxatsxxfiiir, 2 , 1. .),(max1Beijing University of Posts and Telecommunications.168.1 遗传算法基本原理遗传算法基本原理(2)由遗传算法寻找最佳串由遗传算法寻找最佳串-t=0,随机产生几个串，构成初始群体；随机产生几个串，构成初始群体；-计算各串的适应度；计算各串的适应度；-根据适应度

20、对群体进行复制操作，以概率对群体进行交叉操作，以概率根据适应度对群体进行复制操作，以概率对群体进行交叉操作，以概率对群体进行变异操作，产生新的群体；对群体进行变异操作，产生新的群体；-t=t+1,计算各串的适应度；计算各串的适应度；-判断终止条件是否满足，若不满足，返回第三步；判断终止条件是否满足，若不满足，返回第三步；-找出最佳串；找出最佳串；8.1.5 用于优化问题的遗传算法用于优化问题的遗传算法Beijing University of Posts and Telecommunications.178.1 遗传算法基本原理遗传算法基本原理算法解析：算法解析：（1）问题编码）问题编码对于每

21、个对于每个Xi，将其取值与一长为，将其取值与一长为p位的由位的由0和和1组成的字条串组成的字条串str(i)做如下对做如下对应：应：8.1.5 用于优化问题的遗传算法用于优化问题的遗传算法ririipiip，x，xxabibinrepax长度为级联而成对应字符串其对应字符串由每个对于),(12)(1Beijing University of Posts and Telecommunications.188.1 遗传算法基本原理遗传算法基本原理算法解析：算法解析：（2）适应度函数）适应度函数对适应度作一个浮动，避免相对变化范围不大时，算法收敛过慢对适应度作一个浮动，避免相对变化范围不大时，算法收

22、敛过慢8.1.5 用于优化问题的遗传算法用于优化问题的遗传算法niiniiiiFFFFFFnFFF1max1minminmaxminmaxmin)(1其中Beijing University of Posts and Telecommunications.198.1 遗传算法基本原理遗传算法基本原理算法解析：算法解析：（3）初始群体与群体规模）初始群体与群体规模-群体规模选得过小，容易造成成熟前收敛，选得过大，则每一代的运算群体规模选得过小，容易造成成熟前收敛，选得过大，则每一代的运算量很大，收敛速度慢；量很大，收敛速度慢；-经过实际运算比较发现，群体规模为编码长度的经过实际运算比较发现，群体

23、规模为编码长度的2倍时较好；倍时较好；-初始群体的选取，考虑到对于同一问题的交互过程，各次计算变化不大，初始群体的选取，考虑到对于同一问题的交互过程，各次计算变化不大，因此上次的计算结果可作为先验带入下次的初始群体中，经过实际比较，因此上次的计算结果可作为先验带入下次的初始群体中，经过实际比较，保留上次适应值较大的保留上次适应值较大的20%，再随机产生，再随机产生80%的初始群体效果较好；的初始群体效果较好；8.1.5 用于优化问题的遗传算法用于优化问题的遗传算法Beijing University of Posts and Telecommunications.208.1 遗传算法基本原理遗

24、传算法基本原理算法解析：算法解析：（4）复制操作）复制操作-为了防止已经搜寻到的最优结果的丢失，通常把上一代群体中适应度最为了防止已经搜寻到的最优结果的丢失，通常把上一代群体中适应度最大的大的10%,直接带入到下一代群体，另外的直接带入到下一代群体，另外的90%通过复制、交叉、变异三通过复制、交叉、变异三种操作产生；种操作产生；-每一个体的复制比例如下：每一个体的复制比例如下：8.1.5 用于优化问题的遗传算法用于优化问题的遗传算法9 . 01niiiFFBeijing University of Posts and Telecommunications.218.1 遗传算法基本原理遗传算法基

25、本原理算法解析：算法解析：（5）交叉操作与交叉概率）交叉操作与交叉概率交叉只对由复制产生的交叉只对由复制产生的0.9n个个体进行，交叉概率越大，产生新个体的机个个体进行，交叉概率越大，产生新个体的机会越大，搜索效率越高，但过大的话，则搜索的较好的个体将会丢失，一会越大，搜索效率越高，但过大的话，则搜索的较好的个体将会丢失，一般取般取0.85为佳，由于采取了为佳，由于采取了10%个体直接进入下一代，故取个体直接进入下一代，故取0.95较好。较好。（6）变异操作与变异概率）变异操作与变异概率变异操作保证了算法能搜索到问题解空间的每一点，使算法具有全局收剑变异操作保证了算法能搜索到问题解空间的每一点

26、，使算法具有全局收剑性，一般取性，一般取0.03为佳。为佳。（7）停止条件）停止条件停止条件为停止条件为N代内最佳适应度值无显著提高。代内最佳适应度值无显著提高。N太大则收敛时间太长，太太大则收敛时间太长，太小则所求结果与最优值误差太大，可参看群体规模来确定小则所求结果与最优值误差太大，可参看群体规模来确定N，当群体规模，当群体规模n=2pr时，可选时，可选N为为308.1.5 用于优化问题的遗传算法用于优化问题的遗传算法Beijing University of Posts and Telecommunications.22约束最优化的遗传算法约束最优化的遗传算法（2）带有不等式约束的非线性

27、优化问题）带有不等式约束的非线性优化问题8.1 遗传算法基本原理遗传算法基本原理ribxatsxxgtsxxfiiirr, 2 , 12 . .0),(1 . .),(max118.1.5 用于优化问题的遗传算法用于优化问题的遗传算法Beijing University of Posts and Telecommunications.23约束最优化的遗传算法约束最优化的遗传算法（1）带有不等式约束的非线性优化问题）带有不等式约束的非线性优化问题定义适应度：设第定义适应度：设第t代规模为代规模为n的群体对应的目标值为的群体对应的目标值为Fi,取修正取修正8.1 遗传算法基本原理遗传算法基本原理8

28、.1.5 用于优化问题的遗传算法用于优化问题的遗传算法否则个个体满足第再次修正其中01 . .maxmin)(11max1minminmaxmint siFFiiFFFFFFnFFFniiniiiiBeijing University of Posts and Telecommunications.24约束最优化的遗传算法约束最优化的遗传算法（2）对等式约束的非线性优化问题）对等式约束的非线性优化问题8.1 遗传算法基本原理遗传算法基本原理ribxatsxxgtsxxfiiirr, 2 , 12 . .0),(1 . .),(max118.1.5 用于优化问题的遗传算法用于优化问题的遗传算法B

29、eijing University of Posts and Telecommunications.25约束最优化的遗传算法约束最优化的遗传算法（2）对等式约束的非线性优化问题）对等式约束的非线性优化问题加法形式加法形式式中，式中，P()为单调减函数，如为单调减函数，如P(y)=-cy2 c08.1 遗传算法基本原理遗传算法基本原理ribxatsxxgPxxfiiirr, 2 , 12 . .),(),(max2118.1.5 用于优化问题的遗传算法用于优化问题的遗传算法Beijing University of Posts and Telecommunications.268.2 基于遗传算

30、法的参数辨识基于遗传算法的参数辨识 利用遗传算法建模，可同时确定模型结构及参数。对于线性模型，可利用遗传算法建模，可同时确定模型结构及参数。对于线性模型，可同时获得系统的阶、时滞及参数值。只要将相关参数组合成相应的基因型，同时获得系统的阶、时滞及参数值。只要将相关参数组合成相应的基因型，并定义好相应的适应度函数即可，实现起来方便。并定义好相应的适应度函数即可，实现起来方便。 这里，将模型结构及参数组成染色体串，将拟合误差转换成相应的适这里，将模型结构及参数组成染色体串，将拟合误差转换成相应的适应度，于是系统建模问题就转化为利用遗传算法搜索最佳基因型结构问题。应度，于是系统建模问题就转化为利用遗传算法搜索最佳基因型结构问题。 Beijing University of Posts and Telecommunicati