遗传算法详解.PPT

《遗传算法详解.PPT》由会员分享，可在线阅读，更多相关《遗传算法详解.PPT（50页珍藏版）》请在金锄头文库上搜索。

1、5.遗传算法遗传算法 遗传算法（遗传算法（genetic algorithms,简称简称GA）是人工智能是人工智能的重要分支，是基于达尔文进化论，在微型计算机上模拟的重要分支，是基于达尔文进化论，在微型计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存、生命进化机制而发展起来的一门新学科。它根据适者生存、优胜劣汰等自然进化规则来进行搜索计算和问题求解。对优胜劣汰等自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决或明显失效的非常复杂问题，特许多用传统数学难以解决或明显失效的非常复杂问题，特别是最优化问题，别是最优化问题，GA提供了一个行之有效的新途径。近提供了一个行之有

2、效的新途径。近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业控制工程领域的成功应用，这种算法受到了广泛的关工业控制工程领域的成功应用，这种算法受到了广泛的关注。注。 5.1.1 基本遗传学基础 遗遗传传算算法法是是根根据据生生物物进进化化的的模模型型提提出出的的一一种种优优化化算算法法。自自然然选选择择学学说说是是进进化化论论的的中中心心内内容容，根根据据进进化化论论，生生物物的的发展进化主要由三个原因，即遗传、变异和选择。发展进化主要由三个原因，即遗传、变异和选择。 遗遗传传是是指指子子代代总总是是和和亲亲代代相相似似。遗遗传传性性是

3、是一一切切生生物物所所共共有有的的特特性性，它它使使得得生生物物能能够够把把其其特特性性、性性状状传传给给后后代代。遗传是生物进化的基础。遗传是生物进化的基础。 变异是指子代和亲代有某些不相似的现象，即子代永变异是指子代和亲代有某些不相似的现象，即子代永远不会和亲代完全一样。它是一切生物所具有的共有特性，远不会和亲代完全一样。它是一切生物所具有的共有特性，是生物个体之间相互区别的基础。引起变异的原因主要是是生物个体之间相互区别的基础。引起变异的原因主要是生活环境的影响及杂交等。生物的变异性为生物的进化和生活环境的影响及杂交等。生物的变异性为生物的进化和发展创造了条件。发展创造了条件。 选选择择

4、决决定定生生物物进进化化的的方方向向。在在进进化化过过程程中中，有有的的要要保保留留，有有的的要要被被淘淘汰汰。自自然然选选择择是是指指生生物物在在自自然然界界的的生生存存环环境境中中适适者者生生存存，不不适适者者被被淘淘汰汰的的过过程程。通通过过不不断断的的自自然然选选择择，有有利利于于生生存存的的变变异异就就会会遗遗传传下下去去，积积累累起起来来，使使变变异异越来越大，逐步产生了新的物种。越来越大，逐步产生了新的物种。 生物就是在遗传、变异和选择三种因素的综合作用过生物就是在遗传、变异和选择三种因素的综合作用过程中，不断地向前发展和进化。选择是通过遗传和变异起程中，不断地向前发展和进化。选

5、择是通过遗传和变异起作用的，变异为选择提供资料，遗传巩固与积累选择的资作用的，变异为选择提供资料，遗传巩固与积累选择的资料，而选择则能控制变异与遗传的方向，使变异和遗传向料，而选择则能控制变异与遗传的方向，使变异和遗传向着适应环境的方向发展。遗传算法正是吸取了自然生物系着适应环境的方向发展。遗传算法正是吸取了自然生物系统统“适者生存、优胜劣汰适者生存、优胜劣汰”的进化原理，从而使它能够提的进化原理，从而使它能够提供一个在复杂空间中随机搜索的方法，为解决许多传统的供一个在复杂空间中随机搜索的方法，为解决许多传统的优化方法难以解决的优化问题提供了新的途径。优化方法难以解决的优化问题提供了新的途径。

6、 5.1.2 遗传算法的原理和特点 遗传算法将生物进化原理引入待优化参数形成的编码遗传算法将生物进化原理引入待优化参数形成的编码串群体中，按着一定的适值函数及一系列遗传操作对各个串群体中，按着一定的适值函数及一系列遗传操作对各个体进行筛选，从而使适值高的个体被保留下来，组成新的体进行筛选，从而使适值高的个体被保留下来，组成新的群体，新群体包含上一代的大量信息，并且引入了新的优群体，新群体包含上一代的大量信息，并且引入了新的优于上一代的个体。这样周而复始，群体中各个体适值不断于上一代的个体。这样周而复始，群体中各个体适值不断提高，直至满足一定的极限条件。此时，群体中适值最高提高，直至满足一定的极

7、限条件。此时，群体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理，使它能够在复杂空间进行全局优化搜索，特色的工作原理，使它能够在复杂空间进行全局优化搜索，并且具有较强的鲁棒性；另外，遗传算法对于搜索空间，并且具有较强的鲁棒性；另外，遗传算法对于搜索空间，基本上不需要什么限制性的假设（如连续、可微及单峰等）基本上不需要什么限制性的假设（如连续、可微及单峰等）。 遗传算法的特点遗传算法的特点同常规优化算法相比，遗传算法有以下特点：同常规优化算法相比，遗传算法有以下特点： 遗遗传传算算法法是是对对参参数数的的编编码码进进行

8、行操操作作，而而非非对对参参数本身。数本身。 遗遗传传算算法法是是从从许许多多点点开开始始并并行行操操作作，并并非非局局限限于于一一点点，从从而而可可有有效效防防止止搜搜索索过过程程收收敛敛于于局局部部最最优解。优解。 遗遗传传算算法法通通过过目目标标函函数数计计算算适适值值，并并不不需需要要其其它推导和附加信息，因而对问题的依赖性较小。它推导和附加信息，因而对问题的依赖性较小。 遗遗传传算算法法的的寻寻优优规规则则是是由由概概率率决决定定的的，而而非非确确定性的。定性的。 遗遗传传算算法法在在解解空空间间进进行行高高效效启启发发式式搜搜索索，而而非非盲目地穷举或完全随机搜索。盲目地穷举或完全

9、随机搜索。 遗遗传传算算法法对对所所求求解解的的优优化化问问题题没没有有太太多多的的数数学学要求。要求。 遗遗传传算算法法具具有有并并行行计计算算的的特特点点，因因而而可可通通过过大大规模并行计算来提高计算速度。规模并行计算来提高计算速度。 5.1.3 遗传算法的基本操作一般的遗传算法都包含三个基本操作：复制一般的遗传算法都包含三个基本操作：复制(reproduction)、交叉交叉(crossover)和变异和变异(mutation)。 1. 复制复制 复制（又称繁殖），是从一个旧种群（复制（又称繁殖），是从一个旧种群（old population）中选择生命力强的字符串（中选择生命力强的字

10、符串（individual string）产生新种群的过程。或者说，复制是个体位串根产生新种群的过程。或者说，复制是个体位串根据其目标函数据其目标函数f（即适值函数）拷贝自己的过程。直观地讲，即适值函数）拷贝自己的过程。直观地讲，可以把目标函数可以把目标函数f看作是期望的最大效益的某种量度。根据看作是期望的最大效益的某种量度。根据位串的适值所进行的拷贝，意味着具有较高适值的位串更位串的适值所进行的拷贝，意味着具有较高适值的位串更有可能在下一代中产生一个或多个子孙。显然，在复制操有可能在下一代中产生一个或多个子孙。显然，在复制操作过程中，目标函数作过程中，目标函数(适值适值)是该位串被复制或被淘

11、汰的决是该位串被复制或被淘汰的决定因素。定因素。 复制操作的初始种群复制操作的初始种群(旧种群旧种群)的生成往往是随机产生的生成往往是随机产生的。例如，通过掷硬币的。例如，通过掷硬币20次产生维数次产生维数n4的初始种群如下的初始种群如下(正面正面=1，背面，背面=0)： 01101110000100010011 显然，该初始种群可以看成是一个长度为五位的无符显然，该初始种群可以看成是一个长度为五位的无符号二进制数，将其编成四个位串，并解码为十进制的数：号二进制数，将其编成四个位串，并解码为十进制的数： 位串位串1 1： 01101 13 位串位串2 2： 11000 24 位串位串3 3：

12、01000 8 位串位串4 4： 10011 19 通过一个通过一个5位无符号二进制数，可以得到一个从位无符号二进制数，可以得到一个从0到到31的数值的数值x，它可以是系统的某个参数。计算目它可以是系统的某个参数。计算目标函数或适值标函数或适值f(x)=x2，其结果如表其结果如表6-1所示。计算种所示。计算种群中所有个体位串的适值之和，同时，计算种群全群中所有个体位串的适值之和，同时，计算种群全体的适值比例，其结果示于表中。体的适值比例，其结果示于表中。 转轮法转轮法转轮法把种群中所有个体位串适值的总和看作一个轮子的圆转轮法把种群中所有个体位串适值的总和看作一个轮子的圆周，而每个个体位串按其适

13、值在总和中所占的比例占据轮子周，而每个个体位串按其适值在总和中所占的比例占据轮子的一个扇区。按表的一个扇区。按表5-1可绘制如图的转轮。可绘制如图的转轮。复制时，只要简单地转动这个按权重复制时，只要简单地转动这个按权重划分的转轮划分的转轮4次，从而产生次，从而产生4个下一代个下一代的种群。例如对于表的种群。例如对于表5-1中的位串中的位串1，其适值为其适值为169，为总适值的，为总适值的14.4%。因此，每旋转一次转轮指向该位串因此，每旋转一次转轮指向该位串的概率为的概率为0.144。每当需要下一个后。每当需要下一个后代时，就旋转一下这个按权重划分代时，就旋转一下这个按权重划分的转轮，产生一个

14、复制的候选者。的转轮，产生一个复制的候选者。这样位串的适值越高，在其下代中这样位串的适值越高，在其下代中产生的后代就越多。产生的后代就越多。 图图5 5-1-1 当一个位串被选中时，此位串将被完整地复当一个位串被选中时，此位串将被完整地复制，然后将复制位串送入匹配集（缓冲区）中。制，然后将复制位串送入匹配集（缓冲区）中。旋转旋转4次转轮即产生次转轮即产生4个位串。这个位串。这4个位串是上代种个位串是上代种群的复制，有的位串可能被复制一次或多次，有群的复制，有的位串可能被复制一次或多次，有的可能被淘汰。在本例中，位串的可能被淘汰。在本例中，位串3被淘汰，位串被淘汰，位串4被复制一次。如表被复制一

15、次。如表6-2所示，适值最好的有较多的所示，适值最好的有较多的拷贝，即给予适合于生存环境的优良个体更多繁拷贝，即给予适合于生存环境的优良个体更多繁殖后代的机会，从而使优良特性得以遗传，反之，殖后代的机会，从而使优良特性得以遗传，反之，最差的则被淘汰。最差的则被淘汰。 2. 交叉 简单的交叉分两步实现。第一步是将新复制产生的位简单的交叉分两步实现。第一步是将新复制产生的位串个体随机两两配对；第二步是随机选择交叉点，对匹配串个体随机两两配对；第二步是随机选择交叉点，对匹配的位串进行交叉繁殖，产生一对新的位串。具体过程如下：的位串进行交叉繁殖，产生一对新的位串。具体过程如下：设位串的字符长度为设位串

16、的字符长度为l，在在1，l1的范围内，随机地选取的范围内，随机地选取一个整数值一个整数值k作为交叉点。将两个配对串从第作为交叉点。将两个配对串从第k位右边部分位右边部分的所有字符进行交换，从而生成两个新的位串。例如，在的所有字符进行交换，从而生成两个新的位串。例如，在表表6-2中，已知位串的字符长度中，已知位串的字符长度l=5，随机选取随机选取k=4，对两个对两个初始的位串个体初始的位串个体A1和和A2进行配对，交叉操作的位置用分隔进行配对，交叉操作的位置用分隔符符“|”表示为：表示为：A1=0110 | 1A2=1100 | 0交叉操作后产生了两个新的字符串为：交叉操作后产生了两个新的字符串

17、为： A1=01100 A2=11001 一般的交叉操作过程：一般的交叉操作过程： 遗传算法的有效性主要来自于复制和交叉操作。复制虽然能够从旧种遗传算法的有效性主要来自于复制和交叉操作。复制虽然能够从旧种群中选择出优秀者，但不能创造新的个体；交叉模拟生物进化过程中群中选择出优秀者，但不能创造新的个体；交叉模拟生物进化过程中的繁殖现象，通过两个个体的交换组合，来创造新的优良个体。的繁殖现象，通过两个个体的交换组合，来创造新的优良个体。 表表6-36-3列出了交叉操作之后的结果数据，从中可以看出交叉操作列出了交叉操作之后的结果数据，从中可以看出交叉操作的具体过程。首先，随机配对匹配集中的个体，将位

18、串的具体过程。首先，随机配对匹配集中的个体，将位串1 1、2 2配对，位配对，位串串3 3、4 4配对；然后，随机选取交叉点，设位串配对；然后，随机选取交叉点，设位串1 1、2 2的交叉点为的交叉点为k k=4=4，二者只交换最后一位，从而生成两个新的位串，即二者只交换最后一位，从而生成两个新的位串，即 图图5 5-2 -2 交叉操作交叉操作 位串位串3、4的交叉点为的交叉点为k=2，二者交换后三位，生成两个新二者交换后三位，生成两个新的位串，即的位串，即 单点交叉与多点交叉单点交叉与多点交叉 上述例子中交叉的位置是一个，称单点交叉。即指个上述例子中交叉的位置是一个，称单点交叉。即指个体切断点

19、有一处，由于进行个体间的组合替换生成两个新体切断点有一处，由于进行个体间的组合替换生成两个新个体，位串个体长度为个体，位串个体长度为l时，单点交叉可能有时，单点交叉可能有l1个不同的个不同的交叉。交叉。 多点交叉是允许个体的切断点有多个，每个切断点在多点交叉是允许个体的切断点有多个，每个切断点在两个个体间进行个体的交叉，生成两个新个体。两个个体间进行个体的交叉，生成两个新个体。 3. 变异变异 尽管复制和交叉操作很重要，在遗传算法中是第一位的，但不能保证尽管复制和交叉操作很重要，在遗传算法中是第一位的，但不能保证不会遗漏一些重要的遗传信息。在人工遗传系统中，变异用来防止这不会遗漏一些重要的遗传

20、信息。在人工遗传系统中，变异用来防止这种遗漏。在简单遗传算法中，变异就是在某个字符串当中把某一位的种遗漏。在简单遗传算法中，变异就是在某个字符串当中把某一位的值偶然的（概率很小的）随机的改变，即在某些特定位置上简单地把值偶然的（概率很小的）随机的改变，即在某些特定位置上简单地把1变为变为0，或反之。当它有节制地和交叉一起使用时，它就是一种防止，或反之。当它有节制地和交叉一起使用时，它就是一种防止过度成熟而丢失重要过度成熟而丢失重要概念的保险策略。例如，随概念的保险策略。例如，随机产生一个种群，如表所示。在机产生一个种群，如表所示。在该表所列种群中，无论怎样交叉，该表所列种群中，无论怎样交叉，在

21、第在第4位上都不可能得到有位上都不可能得到有1的位串。的位串。若优化的结果要求该位是若优化的结果要求该位是1，显然仅靠交叉是不够的，还需要有变显然仅靠交叉是不够的，还需要有变异，即特定位置上的异，即特定位置上的0和和1之间的转变。之间的转变。 变异在遗传算法中的作用是第二位的，但却是必不可变异在遗传算法中的作用是第二位的，但却是必不可少的。变异运算用来模拟生物在自然界的遗传环境中由于少的。变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机改变各种偶然因素引起的基因突变，它以很小的概率随机改变遗传基因（即位串个体中某一位）的值。通过变异操作，遗传基因（即位

22、串个体中某一位）的值。通过变异操作，可确保种群中遗传基因类型的多样性，以使搜索能在尽可可确保种群中遗传基因类型的多样性，以使搜索能在尽可能大的空间中进行，避免丢失在搜索中有用的遗传信息而能大的空间中进行，避免丢失在搜索中有用的遗传信息而陷入局部解。根据统计，变异的概率为陷入局部解。根据统计，变异的概率为0.001，即变异的频，即变异的频率为每千位传送中只变异一位。在表率为每千位传送中只变异一位。在表6-3的种群中共有的种群中共有20个个字符（每位串的长度为字符（每位串的长度为5个字符）。期望变异的字符串位个字符）。期望变异的字符串位数为数为200.001=0.02（位），所以在此例中无位值的改

23、变。（位），所以在此例中无位值的改变。从表从表6-2和表和表6-3可以看出，虽然仅进行一代遗传操作，但可以看出，虽然仅进行一代遗传操作，但种群适值的平均值和最大值却比初始种群有了很大的提高，种群适值的平均值和最大值却比初始种群有了很大的提高，平均适值由平均适值由293变到变到439，最大值由，最大值由576变到变到729。这说明随。这说明随着遗传运算的进行，种群正向着优化的方向发展。着遗传运算的进行，种群正向着优化的方向发展。 遗传算法在以下几个方面不同于传统优化遗传算法在以下几个方面不同于传统优化方法方法 遗遗传传算算法法只只对对参参数数集集的的编编码码进进行行操操作作，而而不不是是参数集本

24、身。参数集本身。 遗遗传传算算法法的的搜搜索索始始于于解解的的一一个个种种群群，而而不不是是单单个个解解，因因而而可可以以有有效效地地防防止止搜搜索索过过程程收收敛敛于于局局部部最优解。最优解。 遗遗传传算算法法只只使使用用适适值值函函数数，而而不不使使用用导导数数和和其其它附属信息，从而对问题的依赖性小。它附属信息，从而对问题的依赖性小。 遗遗传传算算法法采采用用概概率率的的、而而不不是是确确定定的的状状态态转转移移规则，即具有随机操作算子。规则，即具有随机操作算子。 图图5 5 3 3 遗传算法的工作原理示意图遗传算法的工作原理示意图5.2.1 目标函数值到适值形式的映射 适值是非负的，任

25、何情况下总希望越大越好；而目标适值是非负的，任何情况下总希望越大越好；而目标函数有正、有负、甚至可能是复数值；且目标函数和适值函数有正、有负、甚至可能是复数值；且目标函数和适值间的关系也多种多样。如求最大值对应点时，目标函数和间的关系也多种多样。如求最大值对应点时，目标函数和适值变化方向相同；求最小值对应点时，变化方向恰好相适值变化方向相同；求最小值对应点时，变化方向恰好相反；目标函数值越小的点，适值越大。因此，存在目标函反；目标函数值越小的点，适值越大。因此，存在目标函数值向适值映射的问题。数值向适值映射的问题。 5.2 遗传算法应用中的一些基本问题 首先应保证映射后的适值是非负的，其次目首

26、先应保证映射后的适值是非负的，其次目标函数的优化方向应对应于适值增大的方向。标函数的优化方向应对应于适值增大的方向。 对对最最小小化化问问题题，一一般般采采用用如如下下适适值值函函数数f(x)和和目目标标函数函数g(x)的映射关系：的映射关系： (5-6)其其中中：cmax可可以以是是一一个个输输入入参参数数，或或是是理理论论上上的的最最大大值值，或或是是到到目目前前所所有有代代（或或最最近近的的k代代）之之中中见见到的到的g(x)的最大值，此时的最大值，此时cmax随着代数会有所变化。随着代数会有所变化。对最大化问题，一般采用下述方法：对最大化问题，一般采用下述方法： (5-7)式式中中:

27、cmin既既可可以以是是输输入入值值也也可可以以是是当当前前最最小小值值或或最近的最近的k代中的最小值。代中的最小值。对指数函数问题，一般采用下述方法：对指数函数问题，一般采用下述方法：其其中中：c一一般般取取1.618或或2（最最大大化化），0.618（最最小小化化）。这这样样，既既保保证证了了f(x)0又又使使f(x)的的增增大大方方向向与优化方向一致。与优化方向一致。5.2.2 适值的调整 为了使遗传算法有效地工作，必须保持种群内位串的多样性和位为了使遗传算法有效地工作，必须保持种群内位串的多样性和位串之间的竞争机制。现将遗传算法的运行分为开始、中间和结束三个串之间的竞争机制。现将遗传算

28、法的运行分为开始、中间和结束三个阶段来考虑：在开始阶段，若一个规模不太大的种群内有少数非凡的阶段来考虑：在开始阶段，若一个规模不太大的种群内有少数非凡的个体（适值很高的位串），按通常的选择方法（选择复制的概率为个体（适值很高的位串），按通常的选择方法（选择复制的概率为fi/fi，期望的复制数为期望的复制数为fi/），），这些个体会被大量地复制，在种群中占这些个体会被大量地复制，在种群中占有大的比重，这样就会减少种群的多样性，导致过早收敛，从而可能有大的比重，这样就会减少种群的多样性，导致过早收敛，从而可能丢失一些有意义的搜索点或最优点，而进入局部最优；在结束阶段，丢失一些有意义的搜索点或最优点

29、，而进入局部最优；在结束阶段，即使种群内保持了很大的多样性，但若所有或大多数个体都有很高的即使种群内保持了很大的多样性，但若所有或大多数个体都有很高的适值，从而种群平均适值和最大适值相差无几，则平均适值附近的个适值，从而种群平均适值和最大适值相差无几，则平均适值附近的个体和具有最高适值的个体，被选中的机会相同，这样选择就成了一个体和具有最高适值的个体，被选中的机会相同，这样选择就成了一个近乎随机的步骤，适值的作用就会消失，从而使搜索性能得不到明显近乎随机的步骤，适值的作用就会消失，从而使搜索性能得不到明显改进。因此，有必要对种群内各位串的适值进行有效调整，既不能相改进。因此，有必要对种群内各位

30、串的适值进行有效调整，既不能相差太大，又要拉开档次，强化位串之间的竞争性。差太大，又要拉开档次，强化位串之间的竞争性。5.2.3 编码原则 遗传算法参数编码原则有两种：深层意义上的建筑块遗传算法参数编码原则有两种：深层意义上的建筑块原则和最小符号表原则。而后者是一种应用广泛的实用原原则和最小符号表原则。而后者是一种应用广泛的实用原则。则。 最小符号表原则要求选择一个使问题得以自然表达的最小符号表原则要求选择一个使问题得以自然表达的最小符号编码表。在前面讨论中使用的都是二进制符号编最小符号编码表。在前面讨论中使用的都是二进制符号编码表码表0, 1，任何一个长度为，任何一个长度为l的位串都包含在的

31、位串都包含在0,1l中。中。根据遗传算法的模式理论，遗传算法能有效工作的根本原根据遗传算法的模式理论，遗传算法能有效工作的根本原因，在于其能有效的处理种群中的大量模式，尤其是那些因，在于其能有效的处理种群中的大量模式，尤其是那些定义长度短、确定位数少、适值高的模式（即建筑块）。定义长度短、确定位数少、适值高的模式（即建筑块）。因此，编码应使确定规模的种群中包含尽可能多的模式。因此，编码应使确定规模的种群中包含尽可能多的模式。 表表6-5给给出出了了一一个个参参数数的的二二进进制制编编码码和和非非二二进进制制编编码码的的对对比比情情况况，即即将将0,31上上的的二二进进制制整整数数一一一一对对应

32、应地地映映射射到到一一个个有有32个个字字母母的的符符号号表表中中，这这个个符符号号表表包包含含26个个英英文文字字母母（AZ）和和6个个数数字字（16）。在在二二进进制制编编码码中中，通通过过代代码码表表中中小小部部分分关关键键代代码码可可以以找找到到重重要要的的相相似似性性而而在在非非二二进进制制编编码码中中，只只能能看看到到单单一一代代码码的的符符号表，看不出代码中的相似性。号表，看不出代码中的相似性。为为了了进进一一步步了了解解二二进进制制编编码码的的数数学学意意义义，假假设设有有一一个个非非二二进进制制的的包包含含k个个字字母母编编码码的的符符号号表表V及及二进制编码的符号表二进制编

33、码的符号表V，即即V=a1,a2,akV=0,15.3.1 复制方法的改进1稳态复制法稳态复制法 该方法保证种群中最优秀的个体在进化过程中该方法保证种群中最优秀的个体在进化过程中不被删除，这在很大程度上减少了有效基因的丢不被删除，这在很大程度上减少了有效基因的丢失。在经过交叉、变异产生的新种群中，只有一失。在经过交叉、变异产生的新种群中，只有一个或两个优秀个体被选进下一代种群，替代原有个或两个优秀个体被选进下一代种群，替代原有种群中的最差个体。种群中的最差个体。 2选择种子法选择种子法 该法也称最优串复制法，它保证了最优的个该法也称最优串复制法，它保证了最优的个体被选进下一代进化种群。其执行过

34、程如下：体被选进下一代进化种群。其执行过程如下： 随机初始化种群随机初始化种群N(0)，种群大小为种群大小为n。 计算种群中所有个体适值。计算种群中所有个体适值。 对对以以后后的的种种群群N(t)进进行行如如下下操操作作，直直至至满满足足条条件件或或达达到到进进化化代代数数。根根据据个个体体适适值值大大小小随随机机选选出出n个个个个体体组组成成种种群群N0(t)，并并复复制制一一份份为为N1(t)，对对种种群群N0(t)实实施施交交叉叉操操作作，对对种种群群N1(t)实实施施基基因因突突变变，用以防止有效基因丢失。用以防止有效基因丢失。 计计算算种种群群N0(t)、N1(t)和和N(t)的的个

35、个体体适适值值，从从中中选选出出最最好好的的n个个个个体体构构成成下下一一代代种种群群N (t1)，转转至至。 3确定性复制法确定性复制法 在确定性复制法中，复制的概率按常规计算为：在确定性复制法中，复制的概率按常规计算为：Pifi/fi。对个体对个体Ai，其期望的后代数目其期望的后代数目ei，计算为：计算为：einPi。每一位串个体按每一位串个体按ei的整数部分分配后代数，种群的其余部的整数部分分配后代数，种群的其余部分按顺序表由高到低来填充。分按顺序表由高到低来填充。 4置换式余数随机复制法置换式余数随机复制法 这方法开始与上述确定性复制法一样，期望的个体数这方法开始与上述确定性复制法一样

36、，期望的个体数如前分配为如前分配为ei的整数部分；但的整数部分；但ei的余数部分用来计算转轮法的余数部分用来计算转轮法中的权值，以补充种群总数。中的权值，以补充种群总数。5非置换式余数随机复制法非置换式余数随机复制法 这方法开始也与上述确定性复制法一样，而这方法开始也与上述确定性复制法一样，而ei的余数的余数部分按概率来处理。换句话说，个体至少复制一个与部分按概率来处理。换句话说，个体至少复制一个与ei整整数部分相等的后代，然后以数部分相等的后代，然后以ei的余数部分为概率来复制其的余数部分为概率来复制其余的后代，直至种群的总数达到余的后代，直至种群的总数达到n。例如一个具有期望复例如一个具有

37、期望复制值为制值为1.5的个体，它可以复制产生一个后代，并以的个体，它可以复制产生一个后代，并以0.5概概率产生另一个后代。试验表明，这种方法优于其它复制方率产生另一个后代。试验表明，这种方法优于其它复制方法。法。5.3.2 高级GA算法 为改善为改善SGA的鲁棒性，在复制、交叉和变异运算的基的鲁棒性，在复制、交叉和变异运算的基础上，再考虑两种类型的基因运算，即为微运算和宏运算。础上，再考虑两种类型的基因运算，即为微运算和宏运算。多点交叉微运算是在个体级别上的运算，重组宏运算是在多点交叉微运算是在个体级别上的运算，重组宏运算是在种群级别上的运算。种群级别上的运算。 5.4 基于遗传算法的系统在

38、线辨识 5.4.1 遗传算法在参数辨识中的应用 5.4.2 遗传算法参数辨识仿真示例 5.4.1 遗传算法在参数辨识中的应用1离散系统参数估计离散系统参数估计 设线性离散系统的数学模型为：设线性离散系统的数学模型为： (5-18)式中：式中：d为滞后时间，为滞后时间，(k)为零均值的噪声序列（方差为为零均值的噪声序列（方差为2），），z-1为后移算子。为后移算子。 假定假定A(z-1)、B(z-1)和和C(z-1)未知，则待辨识参数未知，则待辨识参数向量包含向量包含na+ nb+ nc+1个参数，即个参数，即 (5-19)真参数为：真参数为： (5-20) 要应用遗传算法对参数向量要应用遗传算

39、法对参数向量进行在线优化的进行在线优化的参数辨识，必须解决两个问题，一个是确定多参参数辨识，必须解决两个问题，一个是确定多参数编码映射方法，另一个是如何根据目标函数确数编码映射方法，另一个是如何根据目标函数确定适值。定适值。 2. 参数级联定点映射编码参数级联定点映射编码 采用多参数级联定点映射编码原则进行编码，可采用多参数级联定点映射编码原则进行编码，可根据辨识精度确定每个参数的二进制编码长度。根据辨识精度确定每个参数的二进制编码长度。假如每个参数线性映射在假如每个参数线性映射在-2l-1,+2l-1范围内，且要范围内，且要求辨识精度求辨识精度2-m，则每个参数需要则每个参数需要m+l位；若

40、已知位；若已知时滞时滞d2n，则时滞可用则时滞可用n位编码，则各参数编码组位编码，则各参数编码组成一个整体位串的长为成一个整体位串的长为(na+ nb+ nc)(l+m)+n，这这个整体位串就是系统待辨识参数的一个解。个整体位串就是系统待辨识参数的一个解。 设整体位串构成的种群数为设整体位串构成的种群数为N，第第p代的第代的第j个个（1jN）位串所对应的参数为：位串所对应的参数为： (5-21)根据辨识结果，有预测输出和预测输出误差，它根据辨识结果，有预测输出和预测输出误差，它们分别满足：们分别满足： (5-22) (5-23)3. 目标函数到适值形式的映射目标函数到适值形式的映射 为为保保证

41、证映映射射后后的的适适值值是是非非负负的的，选选择择目目标标函函数数的的优优化化方方向向应应对对应应于于适适值值的的增增大大方方向向。由由式式(5-6)的的映映射射关关系系，可可选选择择适值函数为：适值函数为： (5-24) 求和求和m+1步的意义在于能进一步考察辨识参数与真参步的意义在于能进一步考察辨识参数与真参数的拟合情况。在遗传算法操作过程中，可能存在这样的数的拟合情况。在遗传算法操作过程中，可能存在这样的参数，它离真值很远，但经线性组合后某步预测输出与实参数，它离真值很远，但经线性组合后某步预测输出与实际输出相差不大，求和可以避免这样的参数集取得高适值际输出相差不大，求和可以避免这样的

42、参数集取得高适值以致出现错误的收敛。以致出现错误的收敛。m的值越大，适值函数的可信度就的值越大，适值函数的可信度就越高，越高，m的上限可取为的上限可取为k值，值，cmax值是一足够大的正数，它值是一足够大的正数，它与问题的解有关。与问题的解有关。 在计算出种群中每个个体的适值后，需要对它们规范在计算出种群中每个个体的适值后，需要对它们规范化，先求出其平均适值为：化，先求出其平均适值为： (5-25)规范化适值为：规范化适值为： (5-26) 用用种种群群规规范范化化适适值值与与平平均均适适值值的的偏偏差差的的平平方方和和来来定定义义收敛域，即收敛域，即 (5-27)其中：其中：是一个定义的收敛

43、域，例如若设是一个定义的收敛域，例如若设0.0001，则可认则可认为种群已经收敛，这时种群中适值最大的个体就是当前收为种群已经收敛，这时种群中适值最大的个体就是当前收敛条件下的最优者。敛条件下的最优者。 5.4.2 遗传算法参数辨识仿真示例设线性离散系统的数学模型如式（设线性离散系统的数学模型如式（513）所示，其中）所示，其中 d=2采用伪随机二进制序列（采用伪随机二进制序列（PRBS）输入，辨识系统参数为输入，辨识系统参数为 及时滞。设参数的范围是及时滞。设参数的范围是-2,+2，要求辨，要求辨识精度识精度0.02，则每个参数需要用，则每个参数需要用8位的位串表示，若时滞位的位串表示，若时

44、滞d不大于不大于4，则时滞可用，则时滞可用2位的位串表示，所以参数集位串长位的位串表示，所以参数集位串长度为度为48+2=34位。位。 取种群规模取种群规模N=50，交叉概率交叉概率Pc=0.90；变异概率变异概率Pm=0.001。 适值函数中的适值函数中的cmax值分段选取。在操作初期，主要值分段选取。在操作初期，主要强调个体之间的多样性，可将强调个体之间的多样性，可将cmax值稍微取大些，值稍微取大些，cmax=1.85m；操作后期，强调竞争性，操作后期，强调竞争性，cmax值取值取小些，小些，cmax=1.6m。兼顾计算速度和适值可信度，兼顾计算速度和适值可信度，取取10m30。 在操作

45、初期，在每一代适值规范化之后，要保持在操作初期，在每一代适值规范化之后，要保持种群个体中的无子女个体占种群的百分比为一定种群个体中的无子女个体占种群的百分比为一定值，若超过该值，则认为是非成熟收敛。一般将值，若超过该值，则认为是非成熟收敛。一般将这个临界值定义在这个临界值定义在20%左右。定义辨识收敛域，左右。定义辨识收敛域，135s时，控制效果变差。其时，控制效果变差。其主要原因是由于在寻优过程中，种群个体没有对系统输出在不同区域、主要原因是由于在寻优过程中，种群个体没有对系统输出在不同区域、不同变化速率的情况都进行目标函数估价。采用变期望输入的方法使不同变化速率的情况都进行目标函数估价。采

46、用变期望输入的方法使控制器在寻优过程中能够对系统绝大部分状态变化做出响应。此时，控制器在寻优过程中能够对系统绝大部分状态变化做出响应。此时，期望输入按下式选取：期望输入按下式选取： ( (5 5-33)-33)图图5 5-18-18图图5 5-17-17基于函数归一化适值调整法和稳态复制法寻优得到的模糊规则基于函数归一化适值调整法和稳态复制法寻优得到的模糊规则表、系统输出响应分别如表表、系统输出响应分别如表6-8和图和图518所示。从图所示。从图618中可中可以看出当以看出当yd=1时，系统输出很好地跟踪了期望输入，其过渡过时，系统输出很好地跟踪了期望输入，其过渡过程短、稳态误差小，对其它的期

47、望输入都有较好的输出响应。程短、稳态误差小，对其它的期望输入都有较好的输出响应。4. 仿真研究仿真研究 以以著著名名的的7575城城市市TSPTSP为为例例，取取群群体体规规模模为为100100，交交叉叉概概率率在在0.50.850.50.85，变变异异概概率率在在0.20.20.010.01，个个体体接接种种疫疫苗苗概概率率在在0.20.20.30.3，更更新新疫疫苗苗概概率率在在0.50.50.80.8之间随进化过程自行调整；之间随进化过程自行调整；M和和分别取分别取1010和和0.040.04，退温函数为，退温函数为 ，T0=100100，其中其中k为进化代数。在基本参数保持不变的为进化

48、代数。在基本参数保持不变的 前前题题下下，对对通通用用遗遗传传算算法法和和免免疫疫算算法法进进行行比比较较，若若群群体体的的最最佳佳适适值值在在连连续续100100次次迭迭代代中中保保持持不不变变则则认认为为搜搜索索结结束束。同同时时，计计算算过过程程中中每每隔隔1010代代记记录录一一次次进进化化结结果果。图图5 5-21-21显显示示了了免免疫疫遗遗传传算算法法优优化化7575城城市市TSP问问题题的的免免疫疫疫疫苗苗和和优优化结果。化结果。 仿仿真真结结果果表表明明，免免疫疫遗遗传传算算法法经经940940代代首首次次出出现现后后来来被被认认定定的的最最佳佳个个体体，而而通通用用遗遗传传算算法法经经35503550代代才才出出现现该该最最佳佳个个体体，同同时时发发现现免免疫疫遗遗传传算算法法对对提提高高搜搜索索效效率率，消消除除通通用用遗遗传传算算法法在在后后期期的的振振荡荡现现象象具具有有明明显显的效果。的效果。 图图5 5-21 -21 优化优化7575城市城市TSPTSP问题问题的免疫疫苗和的免疫疫苗和优化结果优化结果