遗传算法及其在路径规划中的应用

2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系1遗传算法及其在路径规划中的应用北京科技大学自动化学院控制科学与工程系2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系2参考书目：（1）周德俭，吴斌.智能控制.重庆：重庆大学出版社，2005（2）李少远，王景成.智能控制.北京：机械工业出版社，2005（3）李人厚.智能控制理论和方法.西安：西安电子科技大学出版社，1999（4）王顺晃，舒迪前.智能控制系统及其应用（第二版）.北京：机械工业出版社，20052020年1月20日10时13分北京科技大学自动化学院控制科学与工程系320世纪60年代，美、德等国家的一些科学家开始模仿生物和人类进化的方法来求解复杂优化问题，从而形成了模拟进化优化方法（OptimizationMethodbySimulatedEvolution），其代表性方法有遗传算法（GA：GeneticAlgorithms）、进化规划（EP：EvolutionaryProgramming）、进化策略（ES：EvolutionaryStrategies）。本讲将主要对GA进行详细介绍。常规的数学优化技术基于梯度寻优技术，计算速度快，但要求优化问题具有可微性，且通常只能求得局部最优解；而模拟进化方法无可微性要求，适用于任意的优化问题，尤其适用于求解组合优化问题以及目标函数不可微或约束条件复杂的非线性优化问题。由于它们采用随机优化技术，所以会以较大的概率求得全局最优解。其计算费用较高的问题也因计算机软硬件技术的飞速发展而不再成为制约因素。1遗传算法产生的背景2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系41.1遗传算法的基本概念1.1.1进化的基本理论（1）Darwin生物进化论（2）Mendel自然遗传学说1.1.2遗传算法术语简介（1）个体（染色体）：遗传算法求解实际问题时，首先对待优化问题的参数进行编码（一般采用二进制码串表示），从而得到一个字符串，该字符串被称为一个个体（individual）或一个染色体（chromosome）。（2）种群（群体）：所有个体的集合（population）。（3）种群规模：种群中个体的数量称为种群规模（populationsize）。（4）基因：个体中的每一位称为一个基因（gene）。（5）适应度函数：能够评价个体对环境适应能力的函数（fitnessfunction）。2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系51.1.3遗传算法应用引例例：求的最大值。2(),[0,31]fxxx解：（1）编码方式的确定采用五位二进制代码表示变量x。表1产生的初始种群标号初始种群x值1011011321100024301000841001119（2）初始种群的产生设种群规模N=4，随机产生初始种群如表1所示。2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系6（3）适应度函数值的计算取适应度函数为f(x)=x2，则4个样本的适应度值分别如下表所示。表2适应度函数计算标号初始种群适应度值f(x)=x210110116921100057630100064410011361总计1170平均值292.5最大值576x值13248192020年1月20日10时13分北京科技大学自动化学院控制科学与工程系7（4）复制采用赌轮法计算各个个体被复制的次数。表3复制操作过程标号初始种群适应度f(x)=x210110116921100057630100064410011361总计1170平均值292.5最大值576x值1324819复制概率期望的复制数实际得到的复制数0.1440.4920.0550.3091.0000.250.4920.581.970.221.234.001.001.971201412iiffiiff2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系8（5）交叉采用随机交叉配对，一点交叉方式进行交叉。表4交叉操作过程标号复制后匹配池中的个体1011013211000431100014100112总计平均值最大值新种群01000110011110110010f(x)=x235358252918646258413241854463.5841配对对象（随机选取）交叉点（随机选取）x值2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系9（6）变异采用单点随机变异方式进行变异操作。表5变异操作过程标号交叉后的种群101000211001311101410010总计平均值最大值新种群01100110011110110010f(x)=x23///122529181446258413241934483.5841变异点位置x值2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系101.2遗传算法的基本步骤1.2.1遗传算法的流程确定表示问题解的编码随机生成初始种群确定适应度函数f计算种群中各个体的适应度fi选择高适应度的个体进行复制交叉变异输出最优解是否满足收敛判据？是否图1遗传算法的基本流程图2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系111.2.2遗传算法的具体实现（1）编码方式的选取利用遗传算法求解实际问题时，问题的解是用字符串来表示的，遗传算子也是直接对字符串进行操作的。因此，如何用适当的字符串编码来表示问题的解成为了遗传算法应用过程中的首要问题。目前所使用的字符串编码方式主要有：二进制、实数（浮点数）和符号等。（1）采用二进制形式编码，个体的位数多，描述得比较细致，从而加大了搜索范围；但交叉运算的计算量较大，并且由于大量的具体问题本身都是十进制的，所以还需对实际参数进行编码和译码，从而增加了额外的计算时间。（2）采用实数（浮点数）编码，交叉运算的计算量较小，但变异过程难于进行。（3）符号编码方式通常在一些专门的应用场合使用。2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系12（2）初始种群的产生初始种群对应着问题的初始解，通常有两种方式产生：①完全随机方式产生（字符串每一位均随机产生）；②随机数发生器方式产生（整个字符串用随机数发生器一次产生）。另外，如果对于寻优问题有某些先验知识，则可先将这些先验知识转变为必须满足的一组约束，然后再在满足这些约束的解中随机地选取个体以组成初始种群。（3）适应度函数的确定适应度函数是遗传算法与实际优化问题之间的接口。在遗传算法中要求适应度函数值是非负的，且任何情况下都希望其值越大越好；而实际优化问题的目标函数并不一定满足这个条件，有的是正的，有的可能为负，甚至可能是复数值。因此，对于任意优化问题，首先应把其数学形式表示为遗传算法适于求解的形式，同时要保证二者在数学优化层面上是等价的。这个过程称为适应度转换。2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系13适应度转换首先要保证适应度值是非负的，其次要求目标函数的优化方向应与适应度值增大的方向一致。设实际优化问题的目标函数为J(x)，遗传算法的适应度函数为f(x)，则有：①可以将适应度函数表示为实际优化问题目标函数的线性形式，即有bxJaxf)()(其中，a，b是系数，可根据具体问题的特征及所期望适应度的分散程度来确定。②对于最小化问题，一般采用如下转换形式：其中，cmax既可以是到目前为止所有进化代中目标函数J(x)的最大值（此时cmax将随着进化而有所变化），也可以根据经验人为设定。maxmax()()()0cJxJxcfx当其它2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系14③对于最大化问题（如需要），一般采用如下转换形式：其中，cmin既可以是当前代中目标函数J(x)的最小值，也可以根据经验人为设定。④采用如下的指数函数形式：在最大化问题时，c一般取1.618或2；而在最小化问题时，c可取为0.618。这样，既保证了适应度值非负，又使适应度值增大方向和目标函数优化方向一致。()()Jxfxcminmin()()0()0JxcJxcfx当其它2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系15（4）复制（选择）（ReproductionorSelection）复制是基于适者生存理论而提出的，是指种群中每一个体按照适应度函数进入到匹配池中的过程。适应度值高于种群平均适应度的个体在下一代中将有更多的机会繁殖一个或多个后代，而低于平均适应度的个体则有可能被淘汰掉。复制的目的在于保证那些适应度高的优良个体在进化中生存下去，复制不会产生新的个体。常用的复制方法有：①赌轮法②两两竞争法从种群中随机地选择两个个体，将其中适应度较大的个体作为被复制的个体；若两个体适应度相同，则任意选择一个。③排序法首先根据目标函数值的大小将个体排序，根据具体问题应用各个体的排序序号分配各自进入匹配池的概率。适应度可以按序号线性变化，也可以按某种非线性关系变化。2020年1月20日10时13分北京科技大学自动化学院控制科学与工程系16（5）交叉（Crossover）交叉是指对从匹配池中随机选出的两个个体按一定的交叉概率pc部分地交换某些基因的过程。一般分两步实现：第一步是将新复制产生的匹配池中的个体随机两两配对；第二步是进行交叉繁殖，产生一对新的个体。交叉的目的是为了生成新的个体，产生新的基因组合，避免每代种群中个体的重复。①单点交叉（One-PointCrossover）对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个父代个体的部分染色体，从而产生出两个新的个体，如下图所示。交叉前individual11100111001individual20101000110图2单点交叉交叉后110010011001010110012020年1月20日10时13分北京科技大学自动化学院控制科学与工程系17②两点交叉（Two-PointCrossover）按交叉概率随机设置两个交叉点，然后交换两个父代个体在两个交叉点之间的基因。③均匀交叉（UniformCrossover）其操作过程是：先选出两个父代个体，之后依据交叉概率pc产生一个与父代个体同样长度的二进制串，这里称其为模板（template）。若模板中的某位为0，则两个父代个体对应位不进行交换；反之，模板中的某位为1时，则交换两个父代个体对应位的基因。交叉前individual11101011000individual21010110101图3两点交叉交叉后111011000010010111012020年1月20日10时13分北京科技大学自动化学院控制科学与工程系18④算数交叉（ArithmeticCrossover）算数交叉的操作对象一般是由浮点数编码所表示的个体，它通过两个父代个体的线性组合而产生出两个新的个体。假设在两个父代个体，之间进行算数交叉，则交叉运算后所产生出的两个新个体是tAXtBX11(1)(1)tttAABtttBBAXXXXXX式中为一参数，它若是一个常数，此时所进行的交叉运算称为均匀算数交叉；它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为非均匀算数交叉。交叉前individual10101100110template1001010101图4均匀交叉individual20110010001交叉后010011001101110001002020年1月20日10时13分北京科技大学自动化学院控制科学与工程系19（6）变异（Mutation）一般的变异操作只作用于采用二进制编码的某单个个体，它以一定的变异概率pm对个体的某些位进行取反操作。如同自然界很少发生基因突变一样，变异概率pm一般都取得比较小。变异的目的是为了增加种群个体的多样性，防止丢失一些有用的遗传模式。在简单遗传算法中，变异就是将某个体中某一位的值作取反运算。变异前1