遗传算法及其在路径规划中的应用课件.ppt

1、2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系1遗传算法及其在路径规划遗传算法及其在路径规划中的应用中的应用北京科技大学自动化学院控制科学与工程系北京科技大学自动化学院控制科学与工程系2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系2参考书目：参考书目：（1）周德俭，吴斌）周德俭，吴斌.智能控制智能控制.重庆：重庆大学出重庆：重庆大学出版社，版社，2005（2）李少远，王景成）李少远，王景成.智能控制智能控制.北京：机械工业北京：机械工业出版社，出版社，2005（3）李人厚）李人厚.智能控制理论和方法智能控制理论和方法.西安：西安电西安：西安电子科

2、技大学出版社，子科技大学出版社，1999（4）王顺晃，舒迪前）王顺晃，舒迪前.智能控制系统及其应用（第智能控制系统及其应用（第二版）二版）.北京：机械工业出版社，北京：机械工业出版社，20052023年1月26日21时08分北京科技大学自动化学院控制科学与工程系3 20世纪世纪60年代，美、德等国家的一些科学家开始模仿生物年代，美、德等国家的一些科学家开始模仿生物和人类进化的方法来求解复杂优化问题，从而形成了和人类进化的方法来求解复杂优化问题，从而形成了模拟进化模拟进化优化方法优化方法（Optimization Method by Simulated Evolution），），其代表性方法有遗

3、传算法（其代表性方法有遗传算法（GA：Genetic Algorithms）、进化）、进化规划（规划（EP：Evolutionary Programming）、进化策略（）、进化策略（ES：Evolutionary Strategies）。本讲将主要对）。本讲将主要对GA进行详细介绍。进行详细介绍。常规的数学优化技术基于梯度寻优技术，计算速度快，但常规的数学优化技术基于梯度寻优技术，计算速度快，但要求优化问题具有可微性，且通常只能求得局部最优解；而模要求优化问题具有可微性，且通常只能求得局部最优解；而模拟进化方法拟进化方法无可微性要求，适用于任意的优化问题无可微性要求，适用于任意的优化问题，尤

4、其适用，尤其适用于求解组合优化问题以及目标函数不可微或约束条件复杂的非于求解组合优化问题以及目标函数不可微或约束条件复杂的非线性优化问题。由于它们采用随机优化技术，所以会以较大的线性优化问题。由于它们采用随机优化技术，所以会以较大的概率求得全局最优解。其计算费用较高的问题也因计算机软硬概率求得全局最优解。其计算费用较高的问题也因计算机软硬件技术的飞速发展而不再成为制约因素。件技术的飞速发展而不再成为制约因素。1 遗传算法产生的背景遗传算法产生的背景2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系41.1 遗传算法的基本概念遗传算法的基本概念1.1.1 进化的基本理论进化的

5、基本理论（1）Darwin生物进化论生物进化论（2）Mendel自然遗传学说自然遗传学说1.1.2 遗传算法术语简介遗传算法术语简介（1）个体（染色体）：遗传算法求解实际问题时，首先对待）个体（染色体）：遗传算法求解实际问题时，首先对待优化问题的优化问题的参数参数进行编码（一般采用二进制码串表示），从而进行编码（一般采用二进制码串表示），从而得到一个字符串，该字符串被称为一个个体（得到一个字符串，该字符串被称为一个个体（individual）或）或一个染色体（一个染色体（chromosome）。（2）种群（群体）：所有个体的集合（）种群（群体）：所有个体的集合（population）。）。（3

6、）种群规模：种群中个体的数量称为种群规模（）种群规模：种群中个体的数量称为种群规模（population size）。）。（4）基因：个体中的每一位称为一个基因（）基因：个体中的每一位称为一个基因（gene）。）。（5）适应度函数：能够评价个体对环境适应能力的函数）适应度函数：能够评价个体对环境适应能力的函数（fitness function）。）。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系51.1.3 遗传算法应用引例遗传算法应用引例例：求例：求 的最大值。的最大值。2(),0,31f xxx解解：（：（1）编码方式的确定）编码方式的确定 采用五位二进制代码表示变

7、量采用五位二进制代码表示变量x。表表1 产生的初始种群产生的初始种群标号标号初始种群初始种群x值值1011011321100024301000841001119 （2）初始种群的产生）初始种群的产生设种群规模设种群规模N=4，随机产生初始种群如表，随机产生初始种群如表1所示。所示。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系6（3）适应度函数值的计算）适应度函数值的计算 取适应度函数为取适应度函数为f(x)=x2，则，则4个样本的适应度值分别如下个样本的适应度值分别如下表所示。表所示。表表2 适应度函数计算适应度函数计算标号标号初始种群初始种群适应度值适应度值f(x)

8、=x210110116921100057630100064410011361总总 计计1170平均值平均值292.5最大值最大值576x值值13248192023年1月26日21时08分北京科技大学自动化学院控制科学与工程系7（4）复制）复制 采用赌轮法计算各个个体被复制的次数。采用赌轮法计算各个个体被复制的次数。表表3 复制操作过程复制操作过程标号标号初始种群初始种群适应度适应度f(x)=x210110116921100057630100064410011361总总 计计1170平均值平均值292.5最大值最大值576x值值1324819复制概率复制概率期望的复制期望的复制数数实际得到实际得

9、到的复制数的复制数0.1440.4920.0550.3091.0000.250.4920.581.970.221.234.001.001.971201412iiffiiff2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系8（5）交叉）交叉 采用随机交叉配对，一点交叉方式进行交叉。采用随机交叉配对，一点交叉方式进行交叉。表表4 交叉操作过程交叉操作过程标号标号复制后匹配复制后匹配池中的个体池中的个体1011013211000431100014100112总总 计计平均值平均值最大值最大值新种群新种群01000110011110110010f(x)=x235358252918

10、646258413241854463.5841配对对象配对对象（随机选取（随机选取）交叉点交叉点（随机选取（随机选取）x值值2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系9（6）变异）变异 采用单点随机变异方式进行变异操作采用单点随机变异方式进行变异操作。表表5 变异操作过程变异操作过程标号标号交叉后交叉后的种群的种群101000211001311101410010总总 计计平均值平均值最大值最大值新种群新种群01100110011110110010f(x)=x23/122529181446258413241934483.5841变异点位置变异点位置x值值2023年1月

11、26日21时08分北京科技大学自动化学院控制科学与工程系101.2 遗传算法的基本步骤遗传算法的基本步骤1.2.1 遗传算法的流程遗传算法的流程确定表示问题解的编码确定表示问题解的编码随机生成初始种群随机生成初始种群确定适应度函数确定适应度函数f计算种群中各个体的适应度计算种群中各个体的适应度 fi选择高适应度的个体进行复制选择高适应度的个体进行复制交叉交叉变异变异输出最优解输出最优解是否满足收敛判据？是否满足收敛判据？是是否否图图1 遗传算法的基本流程图遗传算法的基本流程图2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系111.2.2 遗传算法的具体实现遗传算法的具体实

12、现（1）编码方式的选取）编码方式的选取 利用遗传算法求解实际问题时，问题的解是用字符串来表利用遗传算法求解实际问题时，问题的解是用字符串来表示的，示的，遗传算子也是直接对字符串进行操作的遗传算子也是直接对字符串进行操作的。因此，如何用。因此，如何用适当的字符串编码来表示问题的解成为了遗传算法应用过程中适当的字符串编码来表示问题的解成为了遗传算法应用过程中的首要问题。的首要问题。目前所使用的字符串编码方式主要有：目前所使用的字符串编码方式主要有：二进制、实数（浮二进制、实数（浮点数）和符号点数）和符号等。等。（1）采用二进制形式编码，个体的位数多，描述得比较）采用二进制形式编码，个体的位数多，描

13、述得比较细致，从而加大了搜索范围；但交叉运算的计算量较大，并且细致，从而加大了搜索范围；但交叉运算的计算量较大，并且由于大量的具体问题本身都是十进制的，所以还需对实际参数由于大量的具体问题本身都是十进制的，所以还需对实际参数进行编码和译码，从而增加了额外的计算时间。进行编码和译码，从而增加了额外的计算时间。（2）采用实数（浮点数）编码，交叉运算的计算量较小，）采用实数（浮点数）编码，交叉运算的计算量较小，但变异过程难于进行。但变异过程难于进行。（3）符号编码方式通常在一些专门的应用场合使用。）符号编码方式通常在一些专门的应用场合使用。2023年1月26日21时08分北京科技大学自动化学院控制科

14、学与工程系12（2）初始种群的产生）初始种群的产生 初始种群对应着问题的初始解，通常有两种方式产生：初始种群对应着问题的初始解，通常有两种方式产生：完全随机方式产生（字符串每一位均随机产生）；完全随机方式产生（字符串每一位均随机产生）；随机数发生器方式产生（整个字符串用随机数发生器一随机数发生器方式产生（整个字符串用随机数发生器一次产生）。次产生）。另外，如果对于寻优问题有某些先验知识，则可先将这些另外，如果对于寻优问题有某些先验知识，则可先将这些先验知识转变为必须满足的一组先验知识转变为必须满足的一组约束约束，然后再在满足这些，然后再在满足这些约束约束的解中随机地选取个体以组成初始种群。的解

15、中随机地选取个体以组成初始种群。（3）适应度函数的确定）适应度函数的确定 适应度函数是遗传算法与实际优化问题之间的接口。在遗适应度函数是遗传算法与实际优化问题之间的接口。在遗传算法中传算法中要求适应度函数值是非负的，且任何情况下都希望其要求适应度函数值是非负的，且任何情况下都希望其值越大越好值越大越好；而实际优化问题的目标函数并不一定满足这个条；而实际优化问题的目标函数并不一定满足这个条件，有的是正的，有的可能为负，甚至可能是复数值。因此，件，有的是正的，有的可能为负，甚至可能是复数值。因此，对于任意优化问题，首先应把其数学形式表示为遗传算法适于对于任意优化问题，首先应把其数学形式表示为遗传算

16、法适于求解的形式，同时要保证二者在数学优化层面上是等价的。这求解的形式，同时要保证二者在数学优化层面上是等价的。这个过程称为适应度转换。个过程称为适应度转换。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系13 适应度转换首先要保证适应度值是非负的，其次要求目标适应度转换首先要保证适应度值是非负的，其次要求目标函数的优化方向应与适应度值增大的方向一致。设实际优化问函数的优化方向应与适应度值增大的方向一致。设实际优化问题的目标函数为题的目标函数为J(x)，遗传算法的适应度函数为，遗传算法的适应度函数为f(x)，则有：，则有：可以将适应度函数表示为实际优化问题目标函数的线性可

17、以将适应度函数表示为实际优化问题目标函数的线性形式，即有形式，即有bxJaxf)()(其中，其中，a，b是系数，可根据具体问题的特征及所期望适应度的是系数，可根据具体问题的特征及所期望适应度的分散程度来确定。分散程度来确定。对于最小化问题，一般采用如下转换形式：对于最小化问题，一般采用如下转换形式：其中，其中，cmax既可以是到目前为止所有进化代中目标函数既可以是到目前为止所有进化代中目标函数 J(x)的的最大值（此时最大值（此时cmax将随着进化而有所变化），也可以根据经验将随着进化而有所变化），也可以根据经验人为设定。人为设定。maxmax()()()0cJ xJ xcf x当当其它其它2

18、023年1月26日21时08分北京科技大学自动化学院控制科学与工程系14 对于最大化问题（如需要），一般采用如下转换形式：对于最大化问题（如需要），一般采用如下转换形式：其中，其中，cmin既可以是当前代中目标函数既可以是当前代中目标函数 J(x)的最小值，也可以根的最小值，也可以根据经验人为设定。据经验人为设定。采用如下的指数函数形式：采用如下的指数函数形式：在最大化问题时，在最大化问题时，c一般取一般取1.618或或2；而在最小化问题时，；而在最小化问题时，c可取为可取为0.618。这样，既保证了适应度值非负，又使适应度值。这样，既保证了适应度值非负，又使适应度值增大方向和目标函数优化方向

19、一致。增大方向和目标函数优化方向一致。()()J xf xcminmin()()0()0J xcJ xcf x当当其它其它2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系15（4）复制（选择）（）复制（选择）（Reproduction or Selection）复制是基于适者生存理论而提出的，是指种群中每一个体复制是基于适者生存理论而提出的，是指种群中每一个体按照适应度函数进入到匹配池中的过程。适应度值高于种群平按照适应度函数进入到匹配池中的过程。适应度值高于种群平均适应度的个体在下一代中将有更多的机会繁殖一个或多个后均适应度的个体在下一代中将有更多的机会繁殖一个或多个后

20、代，而低于平均适应度的个体则有可能被淘汰掉。复制的目的代，而低于平均适应度的个体则有可能被淘汰掉。复制的目的在于保证那些适应度高的优良个体在进化中生存下去，在于保证那些适应度高的优良个体在进化中生存下去，复制不复制不会产生新的个体会产生新的个体。常用的复制方法有：。常用的复制方法有：赌轮法赌轮法两两竞争法两两竞争法 从种群中随机地选择两个个体，将其中适应度较大的个体从种群中随机地选择两个个体，将其中适应度较大的个体作为被复制的个体；作为被复制的个体；若若两个体适应度相同，两个体适应度相同，则则任意任意选择选择一个。一个。排序法排序法 首先根据目标函数值的大小将个体排序，根据具体问题应首先根据目

21、标函数值的大小将个体排序，根据具体问题应用各个体的排序序号分配各自进入匹配池的概率。适应度可以用各个体的排序序号分配各自进入匹配池的概率。适应度可以按序号线性变化，也可以按某种非线性关系变化。按序号线性变化，也可以按某种非线性关系变化。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系16（5）交叉（）交叉（Crossover）交叉是指对从匹配池中随机选出的两个个体按一定的交叉交叉是指对从匹配池中随机选出的两个个体按一定的交叉概率概率 pc 部分地交换某些基因的过程。一般分两步实现：第一步部分地交换某些基因的过程。一般分两步实现：第一步是将新复制产生的匹配池中的个体随机两两

22、配对；第二步是进是将新复制产生的匹配池中的个体随机两两配对；第二步是进行交叉繁殖，产生一对新的个体。行交叉繁殖，产生一对新的个体。交叉的目的是为了生成新的交叉的目的是为了生成新的个体个体，产生新的基因组合，避免每代种群中个体的重复。，产生新的基因组合，避免每代种群中个体的重复。单点交叉（单点交叉（One-Point Crossover）对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率p pc c在其交叉在其交叉点处相互交换两个父代个体的部分染色体，从而产生出两个新点处相互交换两个父代个体的部分染色体，从而产生出两个新的个体，如下图所示。的个体，如下图所示。交叉前

23、交叉前individual 111001 11001individual 201010 00110图图2 单点交叉单点交叉交叉后交叉后11001 0011001010 110012023年1月26日21时08分北京科技大学自动化学院控制科学与工程系17两点交叉（两点交叉（Two-Point Crossover）按交叉概率随机设置两个交叉点，然后交换两个父代个体按交叉概率随机设置两个交叉点，然后交换两个父代个体在两个交叉点之间的在两个交叉点之间的基因基因。均匀交叉（均匀交叉（Uniform Crossover）其操作过程是：先选出两个父代个体，之后依据交叉概率其操作过程是：先选出两个父代个体，之

24、后依据交叉概率 pc 产生一个与父代个体同样长度的二进制串，这里称其为产生一个与父代个体同样长度的二进制串，这里称其为模板模板（template）。若模板中的某位为）。若模板中的某位为0，则两个父代个体对应位不，则两个父代个体对应位不进行交换；反之，模板中的某位为进行交换；反之，模板中的某位为1时，则交换两个父代个体时，则交换两个父代个体对应位的基因。对应位的基因。交叉前交叉前individual 111 01011 000individual 210 10110 101图图3 两点交叉两点交叉交叉后交叉后11 10110 00010 01011 1012023年1月26日21时08分北京科技

25、大学自动化学院控制科学与工程系18算数交叉（算数交叉（Arithmetic Crossover）算数交叉的操作对象一般是由算数交叉的操作对象一般是由浮点数编码浮点数编码所表示的个体，所表示的个体，它通过两个父代个体的线性组合而产生出两个新的个体。它通过两个父代个体的线性组合而产生出两个新的个体。假设在两个父代个体假设在两个父代个体 ，之间进行算数交叉，则交叉运之间进行算数交叉，则交叉运算后所产生出的两个新个体是算后所产生出的两个新个体是tAXtBX11(1)(1)tttAABtttBBAXXXXXX式中式中 为一参数，它若是一个常数，此时所进行的交叉运算称为一参数，它若是一个常数，此时所进行的

26、交叉运算称为为均匀算数交叉均匀算数交叉；它也可以是一个由进化代数所决定的变量，；它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为此时所进行的交叉运算称为非均匀算数交叉非均匀算数交叉。交叉前交叉前individual 10101100110template1001010101图图4 均匀交叉均匀交叉individual 20110010001交叉后交叉后010011001101110001002023年1月26日21时08分北京科技大学自动化学院控制科学与工程系19（6）变异（）变异（Mutation）一般的变异操作只作用于采用二进制编码的某单个个体，一般的变异操作只作用于采用二进

27、制编码的某单个个体，它以一定的变异概率它以一定的变异概率pm对个体的某些位进行取反操作。如同自对个体的某些位进行取反操作。如同自然界很少发生基因突变一样，变异概率然界很少发生基因突变一样，变异概率pm一般都取得比较小。一般都取得比较小。变异的目的是为了增加种群个体的多样性，防止丢失一些有用变异的目的是为了增加种群个体的多样性，防止丢失一些有用的遗传模式。的遗传模式。在简单遗传算法中，变异就是将某个体中某一位的值作取在简单遗传算法中，变异就是将某个体中某一位的值作取反运算。反运算。变异前变异前1100110111图图5 变异操作示意图变异操作示意图变异后变异后11000101112023年1月2

28、6日21时08分北京科技大学自动化学院控制科学与工程系20（7）收敛判据）收敛判据 常规的优化方法有数学上比较严格的收敛判据，而遗传算常规的优化方法有数学上比较严格的收敛判据，而遗传算法的收敛判据通常是启发式的。由于遗传算法没有利用梯度信法的收敛判据通常是启发式的。由于遗传算法没有利用梯度信息，因此要从数学上构造比较严格的收敛判据相当困难。常用息，因此要从数学上构造比较严格的收敛判据相当困难。常用的收敛判据有：的收敛判据有：根据计算时间和所采用计算机的根据计算时间和所采用计算机的性能性能确定确定收敛收敛判据判据：一：一般采用般采用指定指定最大最大迭代次数的迭代次数的方法方法；从解的质量方面确定

29、判据：如果连续几代从解的质量方面确定判据：如果连续几代（或几十代）（或几十代）种群中的最优解没有变化，则认为算法收敛；或种群中最优个种群中的最优解没有变化，则认为算法收敛；或种群中最优个体的适应度与平均适应度之差和平均适应度的比值小于某一给体的适应度与平均适应度之差和平均适应度的比值小于某一给定值时，也可以认为算法已经收敛。定值时，也可以认为算法已经收敛。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系21（8）约束条件的处理）约束条件的处理 遗传算法在求解有约束的优化问题时，需对约束条件进行遗传算法在求解有约束的优化问题时，需对约束条件进行必要的处理。处理方式有：必要的

30、处理。处理方式有：直接体现在字符串的编码中直接体现在字符串的编码中 对于优化问题中变量的上、下限约束，可以让字符串表示对于优化问题中变量的上、下限约束，可以让字符串表示的最大值和最小值分别对应于实际约束变量的上、下限值。设的最大值和最小值分别对应于实际约束变量的上、下限值。设待优化变量待优化变量x的变化范围为的变化范围为xmin,xmax，如用，如用l 位的二进制字符位的二进制字符串串y来表示，则来表示，则 x、y之间有如下关系：之间有如下关系：)(12minmaxminxxyxxl判断舍弃法判断舍弃法 在遗传算法的运算过程中，检查得到字符串所对应的解是在遗传算法的运算过程中，检查得到字符串所

31、对应的解是否为可行解。若是，则加入到下一代种群中；否则将其舍弃。否为可行解。若是，则加入到下一代种群中；否则将其舍弃。惩罚惩罚函数法函数法 如果一个解违反了某个约束，则视其违反程度给予一定的如果一个解违反了某个约束，则视其违反程度给予一定的惩罚，使其具有较小的适应度。越限越严重，适应度就越小。惩罚，使其具有较小的适应度。越限越严重，适应度就越小。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系221.3 遗传算法的特点遗传算法的特点 目前常规的优化方法主要有目前常规的优化方法主要有3种类型：解析法、枚举法和种类型：解析法、枚举法和随机法。随机法。解析法是优化方法中研究最多

32、的一种，它又分为直接法和解析法是优化方法中研究最多的一种，它又分为直接法和间接法。间接法。直接法直接法是一种通过沿着梯度信息最陡的方向逐渐运动是一种通过沿着梯度信息最陡的方向逐渐运动来寻找局部极值的方法；来寻找局部极值的方法；间接法间接法则是一种通过使目标函数梯度则是一种通过使目标函数梯度为零，进而通过求解一组非线性方程来寻找局部极值的方法。为零，进而通过求解一组非线性方程来寻找局部极值的方法。（1）解析法）解析法 解析法的主要问题在于：解析法的主要问题在于：（1）要求目标函数连续光滑且可微；）要求目标函数连续光滑且可微；（2）一般只能找到局部极值而非全局极值，故对于存在）一般只能找到局部极值

33、而非全局极值，故对于存在多峰极值的优化问题有时显得无能为力。多峰极值的优化问题有时显得无能为力。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系23 随机法能够克服上述两种方法的缺陷，它在搜索空间中随随机法能够克服上述两种方法的缺陷，它在搜索空间中随机地漫游并记录下所找到的最优结果，当搜索到一定程度后便机地漫游并记录下所找到的最优结果，当搜索到一定程度后便终止。当然，它所找到的结果往往也不是最优解。实际上，随终止。当然，它所找到的结果往往也不是最优解。实际上，随机法也是枚举法中的一种。机法也是枚举法中的一种。（2）枚举法）枚举法 枚举法能够克服解析法的两点不足，它可以找到

34、全局极值枚举法能够克服解析法的两点不足，它可以找到全局极值且不要求目标函数连续光滑。但其致命缺点是计算效率太低，且不要求目标函数连续光滑。但其致命缺点是计算效率太低，对于许多实际问题往往会因为搜索空间太大而不可能将所有的对于许多实际问题往往会因为搜索空间太大而不可能将所有的情况一一搜索到。情况一一搜索到。（3）随机法）随机法2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系24 遗传算法是基于自然选择和基因遗传学原理的搜索方法，遗传算法是基于自然选择和基因遗传学原理的搜索方法，它将它将“优胜劣汰、适者生存优胜劣汰、适者生存”的生物进化原理引入到由待优化的生物进化原理引入到由

35、待优化参数形成的编码串种群中，按照一定的适应度函数及一系列遗参数形成的编码串种群中，按照一定的适应度函数及一系列遗传操作对各个个体进行筛选，使适应度值较高的个体被保留下传操作对各个个体进行筛选，使适应度值较高的个体被保留下来，从而组成新的种群，新种群中包含了上一代的大量信息，来，从而组成新的种群，新种群中包含了上一代的大量信息，并且引入了新的优于上一代的个体。如此周而复始，种群中各并且引入了新的优于上一代的个体。如此周而复始，种群中各个体的适应度不断提高，直至满足一定的收敛条件。最后，以个体的适应度不断提高，直至满足一定的收敛条件。最后，以种群中适应度值最高的个体作为待优化参数的最优解。种群中

36、适应度值最高的个体作为待优化参数的最优解。（4）遗传算法）遗传算法 遗传算法也用到了随机搜索技术，但它通过对参数空间的遗传算法也用到了随机搜索技术，但它通过对参数空间的随机编码并用适应度函数作为工具来引导搜索过程向着更有效随机编码并用适应度函数作为工具来引导搜索过程向着更有效的方向发展，因而它不同于常规的随机法。的方向发展，因而它不同于常规的随机法。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系25 与常规优化方法相比，遗传算法的鲁棒性较好，其主要与常规优化方法相比，遗传算法的鲁棒性较好，其主要特点在于：特点在于：遗传算法对参数的编码进行操作，而不是对参数本身；遗传算法

37、对参数的编码进行操作，而不是对参数本身；遗传算法从多个初始点开始操作，而不是从某一个点开遗传算法从多个初始点开始操作，而不是从某一个点开始，这在很大程度上避免了搜索过程过早地收敛于局部极值，始，这在很大程度上避免了搜索过程过早地收敛于局部极值，因此更有可能求得全局极值；因此更有可能求得全局极值；遗传算法通过目标函数计算适应度，它不需要其它的推遗传算法通过目标函数计算适应度，它不需要其它的推导运算和附加信息，因而对问题的依赖性小；导运算和附加信息，因而对问题的依赖性小；遗传算法使用概率的操作规则，而不是确定性的规则；遗传算法使用概率的操作规则，而不是确定性的规则；遗传算法在解空间中采用启发式搜索

38、，而不是盲目的枚遗传算法在解空间中采用启发式搜索，而不是盲目的枚举或完全随机的搜索，因而搜索的效率高；举或完全随机的搜索，因而搜索的效率高；遗传算法对于待寻优的问题基本没有限制，既可以是数遗传算法对于待寻优的问题基本没有限制，既可以是数学解析式所表示的显函数，也可以是映射矩阵或神经网络表示学解析式所表示的显函数，也可以是映射矩阵或神经网络表示的隐函数，同时也不要求待优化函数连续、可微；的隐函数，同时也不要求待优化函数连续、可微；2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系26 遗传算法所具有的隐含并行性的特点，使其可以通过遗传算法所具有的隐含并行性的特点，使其可以通过

39、大规模并行搜索来提高计算速度；大规模并行搜索来提高计算速度；遗传算法适合复杂的、高度非线性问题的优化。遗传算法适合复杂的、高度非线性问题的优化。1.4 遗传算法的研究热点遗传算法的研究热点（1）编码方式的确定；）编码方式的确定；（2）专用遗传算子的设计）专用遗传算子的设计；（3）控制参数的选择）控制参数的选择；种群规模：种群规模：N=20100；交叉概率：交叉概率：pc=0.600.95；变异概率：变异概率：pm=0.0010.01。李擎李擎、张伟、尹怡欣、王志良一种新的调节交叉和变异概率、张伟、尹怡欣、王志良一种新的调节交叉和变异概率的自适应算法的自适应算法控制与决策，控制与决策，2008年

40、年1月第月第23卷第卷第1期：期：7983 2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系272 遗传算法的应用实例遗传算法的应用实例车载导航系统路径规划算法的设计车载导航系统路径规划算法的设计2.1 问题简介问题简介 所谓车载导航系统路径规划，就是在电子地图中找到一条所谓车载导航系统路径规划，就是在电子地图中找到一条从起点到终点在距离（或时间）上最短的路径。从起点到终点在距离（或时间）上最短的路径。下图为一个路径规划用仿真地图，其上共有下图为一个路径规划用仿真地图，其上共有15个节点，个节点，24条弧。弧下的数据表示路径的长度（单位：公里），弧上的数条弧。弧下的数据表

41、示路径的长度（单位：公里），弧上的数据则表示该路段车辆行驶的速度（单位：米据则表示该路段车辆行驶的速度（单位：米/秒）。秒）。在实际电子地图中，节点相当于道路的交叉点，弧相当于在实际电子地图中，节点相当于道路的交叉点，弧相当于实际道路。实际道路。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系281.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

42、.02.93.03.04.22.24.05.05.63.54.14.23.4DPNLOMFCBGKHIJAE图图6 路径规划用仿真地图路径规划用仿真地图2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系292.2 遗传算法的具体应用遗传算法的具体应用（1）路径的表示方法）路径的表示方法 这里采用这里采用符号编码方式符号编码方式表示实际路网中的路径。表示实际路网中的路径。对于图对于图6中一条从中一条从A点到点到P点的路径，采用符号编码方式得点的路径，采用符号编码方式得到的个体为到的个体为A、B、E、H、L、O、P。图图7 仿真地图中的一条路径仿真地图中的一条路径ABEHLOP

43、2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系30（2）初始路径的产生）初始路径的产生传统遗传算法传统遗传算法 随机生成初始路径，会产生断路或环路。随机生成初始路径，会产生断路或环路。改进遗传算法改进遗传算法（a）克服断路的思路）克服断路的思路 从起始点出发，随机选取与起始点直接相连的一个点作为从起始点出发，随机选取与起始点直接相连的一个点作为下一个节点，如此反复直到找到终点为止。下一个节点，如此反复直到找到终点为止。在路径的产生过程中为了避免出现环路，规定在一条路径在路径的产生过程中为了避免出现环路，规定在一条路径中当一个路径节点被选中以后，则给该节点一个标记，只有没

44、中当一个路径节点被选中以后，则给该节点一个标记，只有没有标记的节点才能被选作新的路径节点，每条初始路径选择完有标记的节点才能被选作新的路径节点，每条初始路径选择完毕后标记全部刷新。毕后标记全部刷新。（b）克服环路的思路）克服环路的思路2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系31（3）适应度函数的确定）适应度函数的确定距离最短优化原则下的适应度函数距离最短优化原则下的适应度函数时间最优优化原则下的适应度函数时间最优优化原则下的适应度函数1()iijF xx1()iijijF xxvix其中，其中，为第为第i个染色体（路径）；个染色体（路径）；为第为第i条路径第条路径

45、第j段的路径段的路径长度。长度。ijxijv其中，其中，仍为第仍为第i条路径第条路径第j段的路径长度；段的路径长度；为第为第i条路径第条路径第j段的行驶速度。段的行驶速度。ijx2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系32 不能象传统遗传算法那样随机进行一点、两点或多点交叉不能象传统遗传算法那样随机进行一点、两点或多点交叉操作，因为这样很容易产生断路或环路。操作，因为这样很容易产生断路或环路。这里只允许使用在重复节点位置交叉且只进行一点交叉的这里只允许使用在重复节点位置交叉且只进行一点交叉的操作方式，具体实现步骤如下：操作方式，具体实现步骤如下：（5）交叉操作）交

46、叉操作（4）复制（选择）操作）复制（选择）操作 采用赌轮法进行复制操作。采用赌轮法进行复制操作。随机选取两个个体作为待交叉个体；随机选取两个个体作为待交叉个体；找出两个待交叉个体的共同节点（起点和终点除外）的找出两个待交叉个体的共同节点（起点和终点除外）的集合；集合；从共同节点的集合中随机选择一个节点作为交叉节点；从共同节点的集合中随机选择一个节点作为交叉节点；检查两个待交叉个体在交叉节点之前或之后的内容是否检查两个待交叉个体在交叉节点之前或之后的内容是否相同相同。如相同如相同，则，则取消本次交叉操作；否则，两者交换交叉点取消本次交叉操作；否则，两者交换交叉点之前（或之后）的内容形成两个新个体

47、。之前（或之后）的内容形成两个新个体。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系33 下面将结合仿真地图举例说明交叉操作是如何实现的。下面将结合仿真地图举例说明交叉操作是如何实现的。设选取的两个待交叉样本为设选取的两个待交叉样本为A、B、E、I、L、O、P和和A、C、E、H、L、N、P；两者重复节点的集合为两者重复节点的集合为 E、L；随机选择随机选择E作为交叉节点；作为交叉节点；检查发现两者待交叉样本在检查发现两者待交叉样本在E点之前和之后的内容均不点之前和之后的内容均不相同，因此可以进行此次交叉操作，交叉后的新个体为：相同，因此可以进行此次交叉操作，交叉后的新个

48、体为：A、B、E、H、L、N、PA、C、E、I、L、O、P和和2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系34图8 交叉操作示意图PLOCBHIAEN2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系35（6）变异操作）变异操作 不能采用传统遗传算法中随机选择变异点的做法，因为这不能采用传统遗传算法中随机选择变异点的做法，因为这样同样容易产生断路或环路。样同样容易产生断路或环路。这里采用的变异操作，其基本步骤如下：这里采用的变异操作，其基本步骤如下：随机选取一个个体作为待变异个体；随机选取一个个体作为待变异个体；在待变异个体中随机选择一个节点（起点

49、和终点除外）在待变异个体中随机选择一个节点（起点和终点除外）作为待变异节点；作为待变异节点；找到和该待变异节点直接相连的节点集合（该集合中不找到和该待变异节点直接相连的节点集合（该集合中不包括起点、终点以及待变异个体中的节点）；包括起点、终点以及待变异个体中的节点）；从节点集合中随机选取一个节点作为变异后节点；从节点集合中随机选取一个节点作为变异后节点；检查待变异节点之前和之后的节点是否与变异后节点直检查待变异节点之前和之后的节点是否与变异后节点直接相连。若直接相连，则用变异后节点替代待变异节点完成变接相连。若直接相连，则用变异后节点替代待变异节点完成变异过程；否则，放弃此次操作，回到第异过程

50、；否则，放弃此次操作，回到第步，直至将节点集合步，直至将节点集合中的所有节点全部选遍。中的所有节点全部选遍。2023年1月26日21时08分北京科技大学自动化学院控制科学与工程系36 现结合仿真地图举例说明变异操作的具体实现方法。现结合仿真地图举例说明变异操作的具体实现方法。选择待变异个体为选择待变异个体为A、C、E、I、L、O、P；经过检查发现经过检查发现C和和B不直接相连，所以取消此次变异操不直接相连，所以取消此次变异操作；接着选取作；接着选取F作为变异后节点，检查发现作为变异后节点，检查发现C和和F、F和和I直接相直接相连，故可进行此次变异操作，变异后的新个体为连，故可进行此次变异操作，