遗传算法及其在路径规划遗传算法及其在路径规划中的应用中的应用7/26/20241参考书目：参考书目：（1）周德俭，吴斌）周德俭，吴斌. 智能控制智能控制. 重庆：重庆大学出重庆：重庆大学出版社，版社，2005（2）李少远，王景成）李少远，王景成. 智能控制智能控制. 北京：机械工业北京：机械工业出版社，出版社，2005（3）李人厚）李人厚. 智能控制理论和方法智能控制理论和方法. 西安：西安电西安：西安电子科技大学出版社，子科技大学出版社，1999（4）王顺晃，舒迪前）王顺晃，舒迪前. 智能控制系统及其应用（第智能控制系统及其应用（第二版）二版）. 北京：机械工业出版社，北京：机械工业出版社，20057/26/20242北京科技大学自动化学院控制科学与工程系 20世纪世纪60年代，美、德等国家的一些科学家开始模仿生物年代，美、德等国家的一些科学家开始模仿生物和人类进化的方法来求解复杂优化问题，从而形成了和人类进化的方法来求解复杂优化问题，从而形成了模拟进化模拟进化优化方法优化方法（Optimization Method by Simulated Evolution），），其代表性方法有遗传算法（其代表性方法有遗传算法（GA：Genetic Algorithms）、进化）、进化规划（规划（EP：Evolutionary Programming）、进化策略（）、进化策略（ES：Evolutionary Strategies）。本讲将主要对）。本讲将主要对GA进行详细介绍。进行详细介绍。 常规的数学优化技术基于梯度寻优技术，计算速度快，但常规的数学优化技术基于梯度寻优技术，计算速度快，但要求优化问题具有可微性，且通常只能求得局部最优解；而模要求优化问题具有可微性，且通常只能求得局部最优解；而模拟进化方法拟进化方法无可微性要求，适用于任意的优化问题无可微性要求，适用于任意的优化问题，尤其适用，尤其适用于求解组合优化问题以及目标函数不可微或约束条件复杂的非于求解组合优化问题以及目标函数不可微或约束条件复杂的非线性优化问题。由于它们采用随机优化技术，所以会以较大的线性优化问题。由于它们采用随机优化技术，所以会以较大的概率求得全局最优解。其计算费用较高的问题也因计算机软硬概率求得全局最优解。其计算费用较高的问题也因计算机软硬件技术的飞速发展而不再成为制约因素。件技术的飞速发展而不再成为制约因素。1 遗传算法产生的背景遗传算法产生的背景7/26/20243北京科技大学自动化学院控制科学与工程系1.1 遗传算法的基本概念遗传算法的基本概念1.1.1 进化的基本理论进化的基本理论（1）Darwin生物进化论生物进化论（2）Mendel自然遗传学说自然遗传学说1.1.2 遗传算法术语简介遗传算法术语简介（1）个体（染色体）：遗传算法求解实际问题时，首先对待）个体（染色体）：遗传算法求解实际问题时，首先对待优化问题的优化问题的参数参数进行编码（一般采用二进制码串表示），从而进行编码（一般采用二进制码串表示），从而得到一个字符串，该字符串被称为一个个体（得到一个字符串，该字符串被称为一个个体（individual ）或）或一个染色体（一个染色体（chromosome）。）。（2）种群（群体）：所有个体的集合（）种群（群体）：所有个体的集合（population）。）。（3）种群规模：种群中个体的数量称为种群规模（）种群规模：种群中个体的数量称为种群规模（population size）。）。（4）基因：个体中的每一位称为一个基因（）基因：个体中的每一位称为一个基因（gene）。）。（5）适应度函数：能够评价个体对环境适应能力的函数）适应度函数：能够评价个体对环境适应能力的函数（fitness function）。）。7/26/20244北京科技大学自动化学院控制科学与工程系1.1.3 遗传算法应用引例遗传算法应用引例例：求例：求 的最大值。的最大值。解解：（：（1）编码方式的确定）编码方式的确定 采用五位二进制代码表示变量采用五位二进制代码表示变量x。表表1 产生的初始种群产生的初始种群标号标号初始种群初始种群x值值1011011321100024301000841001119 （2）初始种群的产生）初始种群的产生设种群规模设种群规模N=4，随机产生初始种群如表，随机产生初始种群如表1所示。所示。7/26/20245北京科技大学自动化学院控制科学与工程系（3）适应度函数值的计算）适应度函数值的计算 取适应度函数为取适应度函数为f (x)=x2，则，则4个样本的适应度值分别如下个样本的适应度值分别如下表所示。表所示。表表2 适应度函数计算适应度函数计算标号标号初始种群初始种群适应度值适应度值f (x)=x210110116921100057630100064410011361总总 计计1170平均值平均值292.5最大值最大值576x值值13248197/26/20246北京科技大学自动化学院控制科学与工程系（4）复制）复制 采用赌轮法计算各个个体被复制的次数。采用赌轮法计算各个个体被复制的次数。表表3 复制操作过程复制操作过程标号标号初始种群初始种群适应度适应度f (x)=x210110116921100057630100064410011361总总 计计1170平均值平均值292.5最大值最大值576x值值1324819复制概率复制概率期望的复制数期望的复制数实际得到实际得到的复制数的复制数0.1440.4920.0550.3091.0000.250.4920.581.970.221.234.001.001.9712014127/26/20247北京科技大学自动化学院控制科学与工程系（5）交叉）交叉 采用随机交叉配对，一点交叉方式进行交叉。采用随机交叉配对，一点交叉方式进行交叉。表表4 交叉操作过程交叉操作过程标号标号复制后匹配复制后匹配池中的个体池中的个体1011013211000431100014100112总总 计计平均值平均值最大值最大值新种群新种群01000110011110110010f (x)=x235358252918646258413241854463.5841配对对象配对对象（随机选取）（随机选取）交叉点交叉点（随机选取）（随机选取）x值值7/26/20248北京科技大学自动化学院控制科学与工程系（6）变异）变异 采用单点随机变异方式进行变异操作。采用单点随机变异方式进行变异操作。表表5 变异操作过程变异操作过程标号标号交叉后交叉后的的种群种群101000211001311101410010总总 计计平均值平均值最大值最大值新种群新种群01100110011110110010f (x)=x23/122529181446258413241934483.5841变异点位置变异点位置x值值7/26/20249北京科技大学自动化学院控制科学与工程系1.2 遗传算法的基本步骤遗传算法的基本步骤1.2.1 遗传算法的流程遗传算法的流程确定表示问题解的编码确定表示问题解的编码随机生成初始种群随机生成初始种群确定适应度函数确定适应度函数f计算种群中各个体的适应度计算种群中各个体的适应度 fi选择高适应度的个体进行复制选择高适应度的个体进行复制交叉交叉变异变异输出最优解输出最优解是否满足收敛判据？是否满足收敛判据？是是否否图图1 遗传算法的基本流程图遗传算法的基本流程图7/26/202410北京科技大学自动化学院控制科学与工程系1.2.2 遗传算法的具体实现遗传算法的具体实现（1）编码方式的选取）编码方式的选取 利用遗传算法求解实际问题时，问题的解是用字符串来表利用遗传算法求解实际问题时，问题的解是用字符串来表示的，示的，遗传算子也是直接对字符串进行操作的遗传算子也是直接对字符串进行操作的。因此，如何用。因此，如何用适当的字符串编码来表示问题的解成为了遗传算法应用过程中适当的字符串编码来表示问题的解成为了遗传算法应用过程中的首要问题。的首要问题。 目前所使用的字符串编码方式主要有：目前所使用的字符串编码方式主要有：二进制、实数（浮二进制、实数（浮点数）和符号点数）和符号等。等。 （1）采用二进制形式编码，个体的位数多，描述得比较）采用二进制形式编码，个体的位数多，描述得比较细致，从而加大了搜索范围；但交叉运算的计算量较大，并且细致，从而加大了搜索范围；但交叉运算的计算量较大，并且由于大量的具体问题本身都是十进制的，所以还需对实际参数由于大量的具体问题本身都是十进制的，所以还需对实际参数进行编码和译码，从而增加了额外的计算时间。进行编码和译码，从而增加了额外的计算时间。 （2）采用实数（浮点数）编码，交叉运算的计算量较小，）采用实数（浮点数）编码，交叉运算的计算量较小，但变异过程难于进行。但变异过程难于进行。 （3）符号编码方式通常在一些专门的应用场合使用。）符号编码方式通常在一些专门的应用场合使用。7/26/202411北京科技大学自动化学院控制科学与工程系（2）初始种群的产生）初始种群的产生 初始种群对应着问题的初始解，通常有两种方式产生：初始种群对应着问题的初始解，通常有两种方式产生： 完全随机方式产生（字符串每一位均随机产生）；完全随机方式产生（字符串每一位均随机产生）； 随机数发生器方式产生（整个字符串用随机数发生器一随机数发生器方式产生（整个字符串用随机数发生器一次产生）。次产生）。 另外，如果对于寻优问题有某些先验知识，则可先将这些另外，如果对于寻优问题有某些先验知识，则可先将这些先验知识转变为必须满足的一组约束，然后再在满足这些约束先验知识转变为必须满足的一组约束，然后再在满足这些约束的解中随机地选取个体以组成初始种群。的解中随机地选取个体以组成初始种群。（3）适应度函数的确定）适应度函数的确定 适应度函数是遗传算法与实际优化问题之间的接口。在遗适应度函数是遗传算法与实际优化问题之间的接口。在遗传算法中传算法中要求适应度函数值是非负的，且任何情况下都希望其要求适应度函数值是非负的，且任何情况下都希望其值越大越好值越大越好；而实际优化问题的目标函数并不一定满足这个条；而实际优化问题的目标函数并不一定满足这个条件，有的是正的，有的可能为负，甚至可能是复数值。因此，件，有的是正的，有的可能为负，甚至可能是复数值。因此，对于任意优化问题，首先应把其数学形式表示为遗传算法适于对于任意优化问题，首先应把其数学形式表示为遗传算法适于求解的形式，同时要保证二者在数学优化层面上是等价的。这求解的形式，同时要保证二者在数学优化层面上是等价的。这个过程称为适应度转换。个过程称为适应度转换。7/26/202412北京科技大学自动化学院控制科学与工程系 适应度转换首先要保证适应度值是非负的，其次要求目标适应度转换首先要保证适应度值是非负的，其次要求目标函数的优化方向应与适应度值增大的方向一致。设实际优化问函数的优化方向应与适应度值增大的方向一致。设实际优化问题的目标函数为题的目标函数为J(x)，遗传算法的适应度函数为，遗传算法的适应度函数为f(x)，则有：，则有： 可以将适应度函数表示为实际优化问题目标函数的线性可以将适应度函数表示为实际优化问题目标函数的线性形式，即有形式，即有其中，其中，a，b是系数，可根据具体问题的特征及所期望适应度的是系数，可根据具体问题的特征及所期望适应度的分散程度来确定。分散程度来确定。 对于最小化问题，一般采用如下转换形式：对于最小化问题，一般采用如下转换形式：其中，其中，cmax既可以是到目前为止所有进化代中目标函数既可以是到目前为止所有进化代中目标函数 J(x) 的的最大值（此时最大值（此时cmax将随着进化而有所变化），也可以根据经验将随着进化而有所变化），也可以根据经验人为设定。人为设定。当当其它其它7/26/202413北京科技大学自动化学院控制科学与工程系 对于最大化问题（如需要），一般采用如下转换形式：对于最大化问题（如需要），一般采用如下转换形式：其中，其中，cmin既可以是当前代中目标函数既可以是当前代中目标函数 J(x) 的最小值，也可以根的最小值，也可以根据经验人为设定。据经验人为设定。 采用如下的指数函数形式：采用如下的指数函数形式： 在最大化问题时，在最大化问题时，c一般取一般取1.618或或2；而在最小化问题时，；而在最小化问题时，c可取为可取为0.618。这样，既保证了适应度值非负，又使适应度值。这样，既保证了适应度值非负，又使适应度值增大方向和目标函数优化方向一致。增大方向和目标函数优化方向一致。当当其它其它7/26/202414北京科技大学自动化学院控制科学与工程系（4）复制（选择）（）复制（选择）（Reproduction or Selection） 复制是基于适者生存理论而提出的，是指种群中每一个体复制是基于适者生存理论而提出的，是指种群中每一个体按照适应度函数进入到匹配池中的过程。适应度值高于种群平按照适应度函数进入到匹配池中的过程。适应度值高于种群平均适应度的个体在下一代中将有更多的机会繁殖一个或多个后均适应度的个体在下一代中将有更多的机会繁殖一个或多个后代，而低于平均适应度的个体则有可能被淘汰掉。复制的目的代，而低于平均适应度的个体则有可能被淘汰掉。复制的目的在于保证那些适应度高的优良个体在进化中生存下去，在于保证那些适应度高的优良个体在进化中生存下去，复制不复制不会产生新的个体会产生新的个体。常用的复制方法有：。常用的复制方法有：赌轮法赌轮法两两两竞争法两竞争法 从种群中随机地选择两个个体，将其中适应度较大的个体从种群中随机地选择两个个体，将其中适应度较大的个体作为被复制的个体；若两个体适应度相同，则任意选择一个。作为被复制的个体；若两个体适应度相同，则任意选择一个。排序法排序法 首先根据目标函数值的大小将个体排序，根据具体问题应首先根据目标函数值的大小将个体排序，根据具体问题应用各个体的排序序号分配各自进入匹配池的概率。适应度可以用各个体的排序序号分配各自进入匹配池的概率。适应度可以按序号线性变化，也可以按某种非线性关系变化。按序号线性变化，也可以按某种非线性关系变化。7/26/202415北京科技大学自动化学院控制科学与工程系（5）交叉（）交叉（Crossover） 交叉是指对从匹配池中随机选出的两个个体按一定的交叉交叉是指对从匹配池中随机选出的两个个体按一定的交叉概率概率 pc 部分地交换某些基因的过程。一般分两步实现：第一步部分地交换某些基因的过程。一般分两步实现：第一步是将新复制产生的匹配池中的个体随机两两配对；第二步是进是将新复制产生的匹配池中的个体随机两两配对；第二步是进行交叉繁殖，产生一对新的个体。行交叉繁殖，产生一对新的个体。交叉的目的是为了生成新的交叉的目的是为了生成新的个体个体，产生新的基因组合，避免每代种群中个体的重复。，产生新的基因组合，避免每代种群中个体的重复。单点交叉（单点交叉（One-Point Crossover） 对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率p pc c在其交叉在其交叉点处相互交换两个父代个体的部分染色体，从而产生出两个新点处相互交换两个父代个体的部分染色体，从而产生出两个新的个体，如下图所示。的个体，如下图所示。交叉前交叉前individual 111001 11001individual 201010 00110图图2 单点交叉单点交叉交叉后交叉后11001 0011001010 110017/26/202416北京科技大学自动化学院控制科学与工程系两点交叉（两点交叉（Two-Point Crossover） 按交叉概率随机设置两个交叉点，然后交换两个父代个体按交叉概率随机设置两个交叉点，然后交换两个父代个体在两个交叉点之间的基因。在两个交叉点之间的基因。均匀交叉（均匀交叉（Uniform Crossover） 其操作过程是：先选出两个父代个体，之后依据交叉概率其操作过程是：先选出两个父代个体，之后依据交叉概率 pc 产生一个与父代个体同样长度的二进制串，这里称其为产生一个与父代个体同样长度的二进制串，这里称其为模板模板（template）。若模板中的某位为）。若模板中的某位为0，则两个父代个体对应位不，则两个父代个体对应位不进行交换；反之，模板中的某位为进行交换；反之，模板中的某位为1时，则交换两个父代个体时，则交换两个父代个体对应位的基因。对应位的基因。交叉前交叉前individual 111 01011 000individual 210 10110 101图图3 两点交叉两点交叉交叉后交叉后11 10110 00010 01011 1017/26/202417北京科技大学自动化学院控制科学与工程系算数交叉（算数交叉（Arithmetic Crossover） 算数交叉的操作对象一般是由算数交叉的操作对象一般是由浮点数编码浮点数编码所表示的个体，所表示的个体，它通过两个父代个体的线性组合而产生出两个新的个体。它通过两个父代个体的线性组合而产生出两个新的个体。 假设在两个父代个体假设在两个父代个体 ， 之间进行算数交叉，则交叉运之间进行算数交叉，则交叉运算后所产生出的两个新个体是算后所产生出的两个新个体是式中式中 为一参数，它若是一个常数，此时所进行的交叉运算称为一参数，它若是一个常数，此时所进行的交叉运算称为为均匀算数交叉均匀算数交叉；它也可以是一个由进化代数所决定的变量，；它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为此时所进行的交叉运算称为非均匀算数交叉非均匀算数交叉。交叉前交叉前individual 10101100110template1001010101图图4 均匀交叉均匀交叉individual 20110010001交叉后交叉后010011001101110001007/26/202418北京科技大学自动化学院控制科学与工程系（6）变异（）变异（Mutation） 一般的变异操作只作用于采用二进制编码的某单个个体，一般的变异操作只作用于采用二进制编码的某单个个体，它以一定的变异概率它以一定的变异概率pm对个体的某些位进行取反操作。如同自对个体的某些位进行取反操作。如同自然界很少发生基因突变一样，变异概率然界很少发生基因突变一样，变异概率pm一般都取得比较小。一般都取得比较小。变异的目的是为了增加种群个体的多样性，防止丢失一些有用变异的目的是为了增加种群个体的多样性，防止丢失一些有用的遗传模式。的遗传模式。 在简单遗传算法中，变异就是将某个体中某一位的值作取在简单遗传算法中，变异就是将某个体中某一位的值作取反运算。反运算。变异前变异前1100110111图图5 变异操作示意图变异操作示意图变异后变异后11000101117/26/202419北京科技大学自动化学院控制科学与工程系（7）收敛判据）收敛判据 常规的优化方法有数学上比较严格的收敛判据，而遗传算常规的优化方法有数学上比较严格的收敛判据，而遗传算法的收敛判据通常是启发式的。由于遗传算法没有利用梯度信法的收敛判据通常是启发式的。由于遗传算法没有利用梯度信息，因此要从数学上构造比较严格的收敛判据相当困难。常用息，因此要从数学上构造比较严格的收敛判据相当困难。常用的收敛判据有：的收敛判据有： 根据计算时间和所采用计算机的性能确定收敛判据：一根据计算时间和所采用计算机的性能确定收敛判据：一般采用指定最大迭代次数的方法；般采用指定最大迭代次数的方法； 从解的质量方面确定判据：如果连续几代（或几十代）从解的质量方面确定判据：如果连续几代（或几十代）种群中的最优解没有变化，则认为算法收敛；或种群中最优个种群中的最优解没有变化，则认为算法收敛；或种群中最优个体的适应度与平均适应度之差和平均适应度的比值小于某一给体的适应度与平均适应度之差和平均适应度的比值小于某一给定值时，也可以认为算法已经收敛。定值时，也可以认为算法已经收敛。7/26/202420北京科技大学自动化学院控制科学与工程系（8）约束条件的处理）约束条件的处理 遗传算法在求解有约束的优化问题时，需对约束条件进行遗传算法在求解有约束的优化问题时，需对约束条件进行必要的处理。处理方式有：必要的处理。处理方式有：直接体现在字符串的编码中直接体现在字符串的编码中 对于优化问题中变量的上、下限约束，可以让字符串表示对于优化问题中变量的上、下限约束，可以让字符串表示的最大值和最小值分别对应于实际约束变量的上、下限值。设的最大值和最小值分别对应于实际约束变量的上、下限值。设待优化变量待优化变量x的变化范围为的变化范围为xmin, xmax，如用，如用l 位的二进制字符位的二进制字符串串y来表示，则来表示，则 x、y之间有如下关系：之间有如下关系：判断舍弃法判断舍弃法 在遗传算法的运算过程中，检查得到字符串所对应的解是在遗传算法的运算过程中，检查得到字符串所对应的解是否为可行解。若是，则加入到下一代种群中；否则将其舍弃。否为可行解。若是，则加入到下一代种群中；否则将其舍弃。惩罚函数法惩罚函数法 如果一个解违反了某个约束，则视其违反程度给予一定的如果一个解违反了某个约束，则视其违反程度给予一定的惩罚，使其具有较小的适应度。越限越严重，适应度就越小。惩罚，使其具有较小的适应度。越限越严重，适应度就越小。7/26/202421北京科技大学自动化学院控制科学与工程系1.3 遗传算法的特点遗传算法的特点 目前常规的优化方法主要有目前常规的优化方法主要有3种类型：解析法、枚举法和种类型：解析法、枚举法和随机法。随机法。 解析法是优化方法中研究最多的一种，它又分为直接法和解析法是优化方法中研究最多的一种，它又分为直接法和间接法。间接法。直接法直接法是一种通过沿着梯度信息最陡的方向逐渐运动是一种通过沿着梯度信息最陡的方向逐渐运动来寻找局部极值的方法；来寻找局部极值的方法；间接法间接法则是一种通过使目标函数梯度则是一种通过使目标函数梯度为零，进而通过求解一组非线性方程来寻找局部极值的方法。为零，进而通过求解一组非线性方程来寻找局部极值的方法。（1）解析法）解析法 解析法的主要问题在于：解析法的主要问题在于： （1）要求目标函数连续光滑且可微；）要求目标函数连续光滑且可微； （2）一般只能找到局部极值而非全局极值，故对于存在）一般只能找到局部极值而非全局极值，故对于存在多峰极值的优化问题有时显得无能为力。多峰极值的优化问题有时显得无能为力。7/26/202422北京科技大学自动化学院控制科学与工程系 随机法能够克服上述两种方法的缺陷，它在搜索空间中随随机法能够克服上述两种方法的缺陷，它在搜索空间中随机地漫游并记录下所找到的最优结果，当搜索到一定程度后便机地漫游并记录下所找到的最优结果，当搜索到一定程度后便终止。当然，它所找到的结果往往也不是最优解。实际上，随终止。当然，它所找到的结果往往也不是最优解。实际上，随机法也是枚举法中的一种。机法也是枚举法中的一种。（2）枚举法）枚举法 枚举法能够克服解析法的两点不足，它可以找到全局极值枚举法能够克服解析法的两点不足，它可以找到全局极值且不要求目标函数连续光滑。但其致命缺点是计算效率太低，且不要求目标函数连续光滑。但其致命缺点是计算效率太低，对于许多实际问题往往会因为搜索空间太大而不可能将所有的对于许多实际问题往往会因为搜索空间太大而不可能将所有的情况一一搜索到。情况一一搜索到。（3）随机法）随机法7/26/202423北京科技大学自动化学院控制科学与工程系 遗传算法是基于自然选择和基因遗传学原理的搜索方法，遗传算法是基于自然选择和基因遗传学原理的搜索方法，它将它将“优胜劣汰、适者生存优胜劣汰、适者生存”的生物进化原理引入到由待优化参的生物进化原理引入到由待优化参数形成的编码串种群中，按照一定的适应度函数及一系列遗传数形成的编码串种群中，按照一定的适应度函数及一系列遗传操作对各个个体进行筛选，使适应度值较高的个体被保留下来，操作对各个个体进行筛选，使适应度值较高的个体被保留下来，从而组成新的种群，新种群中包含了上一代的大量信息，并且从而组成新的种群，新种群中包含了上一代的大量信息，并且引入了新的优于上一代的个体。如此周而复始，种群中各个体引入了新的优于上一代的个体。如此周而复始，种群中各个体的适应度不断提高，直至满足一定的收敛条件。最后，以种群的适应度不断提高，直至满足一定的收敛条件。最后，以种群中适应度值最高的个体作为待优化参数的最优解。中适应度值最高的个体作为待优化参数的最优解。（4）遗传算法）遗传算法 遗传算法也用到了随机搜索技术，但它通过对参数空间的遗传算法也用到了随机搜索技术，但它通过对参数空间的随机编码并用适应度函数作为工具来引导搜索过程向着更有效随机编码并用适应度函数作为工具来引导搜索过程向着更有效的方向发展，因而它不同于常规的随机法。的方向发展，因而它不同于常规的随机法。7/26/202424北京科技大学自动化学院控制科学与工程系 与常规优化方法相比，遗传算法的鲁棒性较好，其主要与常规优化方法相比，遗传算法的鲁棒性较好，其主要特点在于：特点在于： 遗传算法对参数的编码进行操作，而不是对参数本身；遗传算法对参数的编码进行操作，而不是对参数本身； 遗传算法从多个初始点开始操作，而不是从某一个点开遗传算法从多个初始点开始操作，而不是从某一个点开始，这在很大程度上避免了搜索过程过早地收敛于局部极值，始，这在很大程度上避免了搜索过程过早地收敛于局部极值，因此更有可能求得全局极值；因此更有可能求得全局极值； 遗传算法通过目标函数计算适应度，它不需要其它的推遗传算法通过目标函数计算适应度，它不需要其它的推导运算和附加信息，因而对问题的依赖性小；导运算和附加信息，因而对问题的依赖性小； 遗传算法使用概率的操作规则，而不是确定性的规则；遗传算法使用概率的操作规则，而不是确定性的规则； 遗传算法在解空间中采用启发式搜索，而不是盲目的枚遗传算法在解空间中采用启发式搜索，而不是盲目的枚举或完全随机的搜索，因而搜索的效率高；举或完全随机的搜索，因而搜索的效率高； 遗传算法对于待寻优的问题基本没有限制，既可以是数遗传算法对于待寻优的问题基本没有限制，既可以是数学解析式所表示的显函数，也可以是映射矩阵或神经网络表示学解析式所表示的显函数，也可以是映射矩阵或神经网络表示的隐函数，同时也不要求待优化函数连续、可微；的隐函数，同时也不要求待优化函数连续、可微；7/26/202425北京科技大学自动化学院控制科学与工程系 遗传算法所具有的隐含并行性的特点，使其可以通过遗传算法所具有的隐含并行性的特点，使其可以通过大规模并行搜索来提高计算速度；大规模并行搜索来提高计算速度； 遗传算法适合复杂的、高度非线性问题的优化。遗传算法适合复杂的、高度非线性问题的优化。1.4 遗传算法的研究热点遗传算法的研究热点（1）编码方式的确定；）编码方式的确定；（2）专用遗传算子的设计；）专用遗传算子的设计；（3）控制参数的选择；）控制参数的选择；种群规模：种群规模：N = 20100；交叉概率：交叉概率：pc = 0.600.95；变异概率：变异概率：pm = 0.0010.01。李擎李擎、张伟、尹怡欣、王志良一种新的调节交叉和变异概率、张伟、尹怡欣、王志良一种新的调节交叉和变异概率的自适应算法的自适应算法控制与决策，控制与决策，2008年年1月第月第23卷第卷第1期：期：7983 7/26/202426北京科技大学自动化学院控制科学与工程系2 遗传算法的应用实例遗传算法的应用实例车载导航系统路径规划算法的设计车载导航系统路径规划算法的设计2.1 问题简介问题简介 所谓车载导航系统路径规划，就是在电子地图中找到一条所谓车载导航系统路径规划，就是在电子地图中找到一条从起点到终点在距离（或时间）上最短的路径。从起点到终点在距离（或时间）上最短的路径。 下图为一个路径规划用仿真地图，其上共有下图为一个路径规划用仿真地图，其上共有15个节点，个节点，24条弧。弧下的数据表示路径的长度（单位：公里），弧上的数条弧。弧下的数据表示路径的长度（单位：公里），弧上的数据则表示该路段车辆行驶的速度（单位：米据则表示该路段车辆行驶的速度（单位：米/秒）。秒）。 在实际电子地图中，节点相当于道路的交叉点，弧相当于在实际电子地图中，节点相当于道路的交叉点，弧相当于实际道路。实际道路。7/26/202427北京科技大学自动化学院控制科学与工程系1.505.21.090.860.750.801.7112.006.001.332.402.001.330.750.920.801.201.503.001.091.714.001.203.001.501.333.4YX2.82.24.22.24.53.23.22.93.54.42.02.93.03.04.22.24.05.05.63.54.14.23.4DPNLOMFCBGKHIJAE图图6 路径规划用仿真地图路径规划用仿真地图7/26/202428北京科技大学自动化学院控制科学与工程系2.2 遗传算法的具体应用遗传算法的具体应用（1）路径的表示方法）路径的表示方法 这里采用这里采用符号编码方式符号编码方式表示实际路网中的路径。表示实际路网中的路径。 对于图对于图6中一条从中一条从A点到点到P点的路径，采用符号编码方式得点的路径，采用符号编码方式得到的个体为到的个体为A、B、E、H、L、O、P。图图7 仿真地图中的一条路径仿真地图中的一条路径ABEHLOP7/26/202429北京科技大学自动化学院控制科学与工程系（2）初始路径的产生）初始路径的产生传统遗传算法传统遗传算法 随机生成初始路径，会产生断路或环路。随机生成初始路径，会产生断路或环路。改进遗传算法改进遗传算法（a）克服断路的思路）克服断路的思路 从起始点出发，随机选取与起始点直接相连的一个点作为从起始点出发，随机选取与起始点直接相连的一个点作为下一个节点，如此反复直到找到终点为止。下一个节点，如此反复直到找到终点为止。 在路径的产生过程中为了避免出现环路，规定在一条路径在路径的产生过程中为了避免出现环路，规定在一条路径中当一个路径节点被选中以后，则给该节点一个标记，只有没中当一个路径节点被选中以后，则给该节点一个标记，只有没有标记的节点才能被选作新的路径节点，每条初始路径选择完有标记的节点才能被选作新的路径节点，每条初始路径选择完毕后标记全部刷新。毕后标记全部刷新。 （b）克服环路的思路）克服环路的思路7/26/202430北京科技大学自动化学院控制科学与工程系（3）适应度函数的确定）适应度函数的确定距离最短优化原则下的适应度函数距离最短优化原则下的适应度函数时间最优优化原则下的适应度函数时间最优优化原则下的适应度函数其中，其中， 为第为第i个染色体（路径）；个染色体（路径）； 为第为第i条路径第条路径第j段的路径段的路径长度。长度。其中，其中， 仍为第仍为第i条路径第条路径第j段的路径长度；段的路径长度； 为第为第i条路径第条路径第j段的行驶速度。段的行驶速度。7/26/202431北京科技大学自动化学院控制科学与工程系 不能象传统遗传算法那样随机进行一点、两点或多点交叉不能象传统遗传算法那样随机进行一点、两点或多点交叉操作，因为这样很容易产生断路或环路。操作，因为这样很容易产生断路或环路。 这里只允许使用在重复节点位置交叉且只进行一点交叉的这里只允许使用在重复节点位置交叉且只进行一点交叉的操作方式，具体实现步骤如下：操作方式，具体实现步骤如下：（5）交叉操作）交叉操作（4）复制（选择）操作）复制（选择）操作 采用赌轮法进行复制操作。采用赌轮法进行复制操作。 随机选取两个个体作为待交叉个体；随机选取两个个体作为待交叉个体； 找出两个待交叉个体的共同节点（起点和终点除外）的找出两个待交叉个体的共同节点（起点和终点除外）的集合；集合； 从共同节点的集合中随机选择一个节点作为交叉节点；从共同节点的集合中随机选择一个节点作为交叉节点； 检查两个待交叉个体在交叉节点之前或之后的内容是否检查两个待交叉个体在交叉节点之前或之后的内容是否相同。如相同，则取消本次交叉操作；否则，两者交换交叉点相同。如相同，则取消本次交叉操作；否则，两者交换交叉点之前（或之后）的内容形成两个新个体。之前（或之后）的内容形成两个新个体。7/26/202432北京科技大学自动化学院控制科学与工程系 下面将结合仿真地图举例说明交叉操作是如何实现的。下面将结合仿真地图举例说明交叉操作是如何实现的。 设选取的两个待交叉样本为设选取的两个待交叉样本为A、B、E、I、L、O、P和和A、C、E、H、L、N、P； 两者重复节点的集合为两者重复节点的集合为 E、L ； 随机选择随机选择E作为交叉节点；作为交叉节点； 检查发现两者待交叉样本在检查发现两者待交叉样本在E点之前和之后的内容均不点之前和之后的内容均不相同，因此可以进行此次交叉操作，交叉后的新个体为：相同，因此可以进行此次交叉操作，交叉后的新个体为：A、B、E、 H、L、N、PA、C、E、 I、L、O、P和和7/26/202433北京科技大学自动化学院控制科学与工程系图8 交叉操作示意图PLOCBHIAEN7/26/202434北京科技大学自动化学院控制科学与工程系（6）变异操作）变异操作 不能采用传统遗传算法中随机选择变异点的做法，因为这不能采用传统遗传算法中随机选择变异点的做法，因为这样同样容易产生断路或环路。样同样容易产生断路或环路。 这里采用的变异操作，其基本步骤如下：这里采用的变异操作，其基本步骤如下： 随机选取一个个体作为待变异个体；随机选取一个个体作为待变异个体； 在待变异个体中随机选择一个节点（起点和终点除外）在待变异个体中随机选择一个节点（起点和终点除外）作为待变异节点；作为待变异节点； 找到和该待变异节点直接相连的节点集合（该集合中不找到和该待变异节点直接相连的节点集合（该集合中不包括起点、终点以及待变异个体中的节点）；包括起点、终点以及待变异个体中的节点）； 从节点集合中随机选取一个节点作为变异后节点；从节点集合中随机选取一个节点作为变异后节点； 检查待变异节点之前和之后的节点是否与变异后节点直检查待变异节点之前和之后的节点是否与变异后节点直接相连。若直接相连，则用变异后节点替代待变异节点完成变接相连。若直接相连，则用变异后节点替代待变异节点完成变异过程；否则，放弃此次操作，回到第异过程；否则，放弃此次操作，回到第步，直至将节点集合步，直至将节点集合中的所有节点全部选遍。中的所有节点全部选遍。7/26/202435北京科技大学自动化学院控制科学与工程系 现结合仿真地图举例说明变异操作的具体实现方法。现结合仿真地图举例说明变异操作的具体实现方法。 选择待变异个体为选择待变异个体为A、C、E、I、L、O、P； 经过检查发现经过检查发现C和和B不直接相连，所以取消此次变异操作；不直接相连，所以取消此次变异操作；接着选取接着选取F作为变异后节点，检查发现作为变异后节点，检查发现C和和F、F和和I直接相连，直接相连，故可进行此次变异操作，变异后的新个体为故可进行此次变异操作，变异后的新个体为 随机选取随机选取E作为待变异节点；作为待变异节点； 与与E直接相连的节点集合为直接相连的节点集合为B、F、H； 随机选取随机选取B作为变异后节点；作为变异后节点；A、C、F、I、L、O、P7/26/202436北京科技大学自动化学院控制科学与工程系PLOFCBHIAE图图9 变异操作示意图变异操作示意图7/26/202437北京科技大学自动化学院控制科学与工程系（7）删除操作）删除操作 删除操作的具体步骤如下：删除操作的具体步骤如下： 随机选择一个个体；随机选择一个个体； 检查该个体中任意两个不相邻节点（包括起点和终点）检查该个体中任意两个不相邻节点（包括起点和终点）之间是否直接相连。如果直接相连，则删除两个节点之间的所之间是否直接相连。如果直接相连，则删除两个节点之间的所有节点，结束此次删除操作；否则，取消本次删除操作。有节点，结束此次删除操作；否则，取消本次删除操作。 下面也结合仿真地图举例说明删除操作的具体实现方法。下面也结合仿真地图举例说明删除操作的具体实现方法。 设随机选择的个体为设随机选择的个体为A、C、E、F、I、L、O、P； 检查发现检查发现E、I直接相连，则删除两者之间的节点直接相连，则删除两者之间的节点F，从，从而得到新个体而得到新个体A、C、E、I、L、O、P7/26/202438北京科技大学自动化学院控制科学与工程系PLOFCIAE图图10 删除操作示意图删除操作示意图7/26/202439北京科技大学自动化学院控制科学与工程系（8）仿真结果）仿真结果初始种群初始种群33.5A、B、D、H、E、I、F、J、M、O、P1021.3A、C、F、I、M、O、P919.2A、B、E、I、L、N、P820.6A、B、E、I、L、O、P721.5A、C、E、H、K、N、P630.6A、C、F、J、M、I、E、H、L、N、P521.3A、C、F、I、L、O、P419.9A、C、E、I、L、N、P321.9A、B、D、H、L、O、P222.0A、B、D、G、K、N、P1距离距离个体个体标号标号表表6 初始种群及其距离初始种群及其距离7/26/202440北京科技大学自动化学院控制科学与工程系基于距离最短原则的优化结果基于距离最短原则的优化结果19.9A、C、F、I、L、N、P1020.8A、C、E、H、L、O、P919.9A、B、E、I、L、N、P818.7A、B、E、H、L、N、P719.4A、C、E、H、L、N、P618.3A、C、F、J、M、O、P520.5A、B、D、H、L、N、P420.6A、B、E、I、M、O、P320.1A、B、E、H、L、O、P220.8A、B、E、H、K、N、P1距离距离个体个体标号标号表表7 基于距离最短原则的优化结果基于距离最短原则的优化结果7/26/202441北京科技大学自动化学院控制科学与工程系基于时间最短原则的优化结果基于时间最短原则的优化结果23.81A、B、E、I、L、O、P1026.74A、B、D、H、L、O、P933.37A、B、F、E、I、L、O、P828.85A、B、D、H、K、N、P738.54A、C、E、H、L、O、P628.30A、B、D、H、L、N、P525.37A、B、E、I、L、N、P435.10A、C、F、I、L、O、P321.55A、B、E、H、L、O、P223.66A、B、E、H、K、N、P1时间时间个体个体标号标号表表8 基于时间最短原则的优化结果基于时间最短原则的优化结果7/26/202442北京科技大学自动化学院控制科学与工程系3 遗传算法的应用实例遗传算法的应用实例移动机器人路径规划算法的设计移动机器人路径规划算法的设计3.1 问题简介问题简介 所谓移动机器人路径规划，就是在规划空间中找到一条从所谓移动机器人路径规划，就是在规划空间中找到一条从起点到终点，满足某一性能指标（如距离最短、时间最短、能起点到终点，满足某一性能指标（如距离最短、时间最短、能量消耗最小、转弯次数最少等）且和障碍物无碰的路径。量消耗最小、转弯次数最少等）且和障碍物无碰的路径。 根据规划空间中的障碍物信息是否全部已知，移动机器人根据规划空间中的障碍物信息是否全部已知，移动机器人路径规划可以分为路径规划可以分为全局（离线）规划全局（离线）规划和和局部（在线）规划局部（在线）规划两种两种情况；按照规划空间中障碍物的运动形式不同，移动机器人路情况；按照规划空间中障碍物的运动形式不同，移动机器人路径规划又可以分为径规划又可以分为静态规划静态规划和和动态规划动态规划两种情形。两种情形。 图图11所示为一种简单的静态规划环境，图所示为一种简单的静态规划环境，图12为一种为一种简单的简单的动态规划环境。实际规划问题经常是动、静态障碍物并存。动态规划环境。实际规划问题经常是动、静态障碍物并存。7/26/202443北京科技大学自动化学院控制科学与工程系图图11 移动机器人静态仿真环境移动机器人静态仿真环境7/26/202444北京科技大学自动化学院控制科学与工程系图图12 移动机器人动态仿真环境移动机器人动态仿真环境7/26/202445北京科技大学自动化学院控制科学与工程系图图13 移动机器人动、静态混合环境下的路径规划移动机器人动、静态混合环境下的路径规划7/26/202446北京科技大学自动化学院控制科学与工程系图图14 动、静混合环境移动机器人的转角和速度动、静混合环境移动机器人的转角和速度 7/26/202447北京科技大学自动化学院控制科学与工程系4 其它群智能优化理论的路径规划算法其它群智能优化理论的路径规划算法（1）粒子群算法）粒子群算法（2）蚁群算法）蚁群算法（3）鱼群算法）鱼群算法（4）蜂群算法）蜂群算法（5）4.1 单一算法简介单一算法简介4.3相关研究成果相关研究成果4.2 算法之间的结合算法之间的结合（1）算法的切换）算法的切换（2）算法的融合）算法的融合7/26/202448北京科技大学自动化学院控制科学与工程系