遗传算法及其在路径规划中的应用演示文稿

遗传算法及其在路径规划中的应用演示文稿第一页，共四十七页。遗传算法及其在路径规划中的应用第二页，共四十七页。参考书目：（1）周德俭，吴斌.智能控制.重庆：重庆大学出版社，2005（2）李少远，王景成.智能控制.北京：机械工业出版社，2005（3）李人厚.智能控制理论和方法.西安：西安电子科技大学出版社，1999（4）王顺晃，舒迪前.智能控制系统及其应用（第二版）.北京：机械工业出版社，2005第三页，共四十七页。20世纪60年代，美、德等国家的一些科学家开始模仿生物和人类进化的方法来求解复杂优化问题，从而形成了模拟进化优化方法（OptimizationMethodbySimulatedEvolution），其代表性方法有遗传算法（GA：GeneticAlgorithms）、进化规划（EP：EvolutionaryProgramming）、进化策略（ES：EvolutionaryStrategies）。本讲将主要对GA进行详细介绍。常规的数学优化技术基于梯度寻优技术，计算速度快，但要求优化问题具有可微性，且通常只能求得局部最优解；而模拟进化方法无可微性要求，适用于任意的优化问题，尤其适用于求解组合优化问题以及目标函数不可微或约束条件复杂的非线性优化问题。由于它们采用随机优化技术，所以会以较大的概率求得全局最优解。其计算费用较高的问题也因计算机软硬件技术的飞速发展而不再成为制约因素。1遗传算法产生的背景第四页，共四十七页。1.1遗传算法的基本概念1.1.1进化的基本理论（1）Darwin生物进化论（2）Mendel自然遗传学说1.1.2遗传算法术语简介（1）个体（染色体）：遗传算法求解实际问题时，首先对待优化问题的参数进行编码（一般采用二进制码串表示），从而得到一个字符串，该字符串被称为一个个体（individual）或一个染色体（chromosome）。（2）种群（群体）：所有个体的集合（population）。（3）种群规模：种群中个体的数量称为种群规模（populationsize）。（4）基因：个体中的每一位称为一个基因（gene）。（5）适应度函数：能够评价个体对环境适应能力的函数（fitnessfunction）。第五页，共四十七页。1.1.3遗传算法应用引例例：求的最大值。解：（1）编码方式的确定采用五位二进制代码表示变量x。表1产生的初始种群标号初始种群x值1011011321100024301000841001119（2）初始种群的产生设种群规模N=4，随机产生初始种群如表1所示。第六页，共四十七页。（3）适应度函数值的计算取适应度函数为f(x)=x2，则4个样本的适应度值分别如下表所示。表2适应度函数计算标号初始种群适应度值f(x)=x210110116921100057630100064410011361总计1170平均值292.5最大值576x值1324819第七页，共四十七页。（4）复制采用赌轮法计算各个个体被复制的次数。表3复制操作过程标号初始种群适应度f(x)=x210110116921100057630100064410011361总计1170平均值292.5最大值576x值1324819复制概率期望的复制数实际得到的复制数0.1440.4920.0550.3091.0000.250.4920.581.970.221.234.001.001.971201412第八页，共四十七页。（5）交叉采用随机交叉配对，一点交叉方式进行交叉。表4交叉操作过程标号复制后匹配池中的个体1011013211000431100014100112总计平均值最大值新种群01000110011110110010f(x)=x235358252918646258413241854463.5841配对对象（随机选取）交叉点（随机选取）x值第九页，共四十七页。（6）变异采用单点随机变异方式进行变异操作。表5变异操作过程标号交叉后的种群101000211001311101410010总计平均值最大值新种群01100110011110110010f(x)=x23///122529181446258413241934483.5841变异点位置x值第十页，共四十七页。1.2遗传算法的基本步骤1.2.1遗传算法的流程确定表示问题解的编码随机生成初始种群确定适应度函数f计算种群中各个体的适应度fi选择高适应度的个体进行复制交叉变异输出最优解是否满足收敛判据？是否图1遗传算法的基本流程图第十一页，共四十七页。1.2.2遗传算法的具体实现（1）编码方式的选取利用遗传算法求解实际问题时，问题的解是用字符串来表示的，遗传算子也是直接对字符串进行操作的。因此，如何用适当的字符串编码来表示问题的解成为了遗传算法应用过程中的首要问题。目前所使用的字符串编码方式主要有：二进制、实数（浮点数）和符号等。（1）采用二进制形式编码，个体的位数多，描述得比较细致，从而加大了搜索范围；但交叉运算的计算量较大，并且由于大量的具体问题本身都是十进制的，所以还需对实际参数进行编码和译码，从而增加了额外的计算时间。（2）采用实数（浮点数）编码，交叉运算的计算量较小，但变异过程难于进行。（3）符号编码方式通常在一些专门的应用场合使用。第十二页，共四十七页。（2）初始种群的产生初始种群对应着问题的初始解，通常有两种方式产生：

①完全随机方式产生（字符串每一位均随机产生）；

②随机数发生器方式产生（整个字符串用随机数发生器一次产生）。

另外，如果对于寻优问题有某些先验知识，则可先将这些先验知识转变为必须满足的一组约束，然后再在满足这些约束的解中随机地选取个体以组成初始种群。（3）适应度函数的确定适应度函数是遗传算法与实际优化问题之间的接口。在遗传算法中要求适应度函数值是非负的，且任何情况下都希望其值越大越好；而实际优化问题的目标函数并不一定满足这个条件，有的是正的，有的可能为负，甚至可能是复数值。因此，对于任意优化问题，首先应把其数学形式表示为遗传算法适于求解的形式，同时要保证二者在数学优化层面上是等价的。这个过程称为适应度转换。第十三页，共四十七页。适应度转换首先要保证适应度值是非负的，其次要求目标函数的优化方向应与适应度值增大的方向一致。设实际优化问题的目标函数为J(x)，遗传算法的适应度函数为f(x)，则有：

①可以将适应度函数表示为实际优化问题目标函数的线性形式，即有其中，a，b是系数，可根据具体问题的特征及所期望适应度的分散程度来确定。

②对于最小化问题，一般采用如下转换形式：其中，cmax既可以是到目前为止所有进化代中目标函数J(x)的最大值（此时cmax将随着进化而有所变化），也可以根据经验人为设定。当其它第十四页，共四十七页。

③对于最大化问题（如需要），一般采用如下转换形式：其中，cmin既可以是当前代中目标函数J(x)

的最小值，也可以根据经验人为设定。

④采用如下的指数函数形式：在最大化问题时，c一般取1.618或2；而在最小化问题时，c可取为0.618。这样，既保证了适应度值非负，又使适应度值增大方向和目标函数优化方向一致。当其它第十五页，共四十七页。（4）复制（选择）（ReproductionorSelection）复制是基于适者生存理论而提出的，是指种群中每一个体按照适应度函数进入到匹配池中的过程。适应度值高于种群平均适应度的个体在下一代中将有更多的机会繁殖一个或多个后代，而低于平均适应度的个体则有可能被淘汰掉。复制的目的在于保证那些适应度高的优良个体在进化中生存下去，复制不会产生新的个体。常用的复制方法有：①赌轮法②两两竞争法

从种群中随机地选择两个个体，将其中适应度较大的个体作为被复制的个体；若两个体适应度相同，则任意选择一个。③排序法

首先根据目标函数值的大小将个体排序，根据具体问题应用各个体的排序序号分配各自进入匹配池的概率。适应度可以按序号线性变化，也可以按某种非线性关系变化。第十六页，共四十七页。（5）交叉（Crossover）交叉是指对从匹配池中随机选出的两个个体按一定的交叉概率pc部分地交换某些基因的过程。一般分两步实现：第一步是将新复制产生的匹配池中的个体随机两两配对；第二步是进行交叉繁殖，产生一对新的个体。交叉的目的是为了生成新的个体，产生新的基因组合，避免每代种群中个体的重复。①单点交叉（One-PointCrossover）

对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个父代个体的部分染色体，从而产生出两个新的个体，如下图所示。交叉前individual11100111001individual20101000110图2单点交叉交叉后11001001100101011001第十七页，共四十七页。②两点交叉（Two-PointCrossover）

按交叉概率随机设置两个交叉点，然后交换两个父代个体在两个交叉点之间的基因。③均匀交叉（UniformCrossover）其操作过程是：先选出两个父代个体，之后依据交叉概率pc产生一个与父代个体同样长度的二进制串，这里称其为模板（template）。若模板中的某位为0，则两个父代个体对应位不进行交换；反之，模板中的某位为1时，则交换两个父代个体对应位的基因。交叉前individual11101011000individual21010110101图3两点交叉交叉后11101100001001011101第十八页，共四十七页。④算数交叉（ArithmeticCrossover）算数交叉的操作对象一般是由浮点数编码所表示的个体，它通过两个父代个体的线性组合而产生出两个新的个体。

假设在两个父代个体，之间进行算数交叉，则交叉运算后所产生出的两个新个体是式中为一参数，它若是一个常数，此时所进行的交叉运算称为均匀算数交叉；它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为非均匀算数交叉。交叉前individual10101100110template1001010101图4均匀交叉individual20110010001交叉后01001100110111000100第十九页，共四十七页。（6）变异（Mutation）一般的变异操作只作用于采用二进制编码的某单个个体，它以一定的变异概率pm对个体的某些位进行取反操作。如同自然界很少发生基因突变一样，变异概率pm一般都取得比较小。变异的目的是为了增加种群个体的多样性，防止丢失一些有用的遗传模式。在简单遗传算法中，变异就是将某个体中某一位的值作取反运算。变异前1100110111图5变异操作示意图变异后1100010111第二十页，共四十七页。（7）收敛判据常规的优化方法有数学上比较严格的收敛判据，而遗传算法的收敛判据通常是启发式的。由于遗传算法没有利用梯度信息，因此要从数学上构造比较严格的收敛判据相当困难。常用的收敛判据有：

①根据计算时间和所采用计算机的性能确定收敛判据：一般采用指定最大迭代次数的方法；

②从解的质量方面确定判据：如果连续几代（或几十代）种群中的最优解没有变化，则认为算法收敛；或种群中最优个体的适应度与平均适应度之差和平均适应度的比值小于某一给定值时，也可以认为算法已经收敛。第二十一页，共四十七页。（8）约束条件的处理遗传算法在求解有约束的优化问题时，需对约束条件进行必要的处理。处理方式有：①直接体现在字符串的编码中对于优化问题中变量的上、下限约束，可以让字符串表示的最大值和最小值分别对应于实际约束变量的上、下限值。设待优化变量x的变化范围为[xmin,xmax]，如用l位的二进制字符串y来表示，则x、y之间有如下关系：②判断舍弃法

在遗传算法的运算过程中，检查得到字符串所对应的解是否为可行解。若是，则加入到下一代种群中；否则将其舍弃。③惩罚函数法

如果一个解违反了某个约束，则视其违反程度给予一定的惩罚，使其具有较小的适应度。越限越严重，适应度就越小。第二十二页，共四十七页。1.3遗传算法的特点目前常规的优化方法主要有3种类型：解析法、枚举法和随机法。解析法是优化方法中研究最多的一种，它又分为直接法和间接法。直接法是一种通过沿着梯度信息最陡的方向逐渐运动来寻找局部极值的方法；间接法则是一种通过使目标函数梯度为零，进而通过求解一组非线性方程来寻找局部极值的方法。（1）解析法解析法的主要问题在于：（1）要求目标函数连续光滑且可微；（2）一般只能找到局部极值而非全局极值，故对于存在多峰极值的优化问题有时显得无能为力。第二十三页，共四十七页。随机法能够克服上述两种方法的缺陷，它在搜索空间中随机地漫游并记录下所找到的最优结果，当搜索到一定程度后便终止。当然，它所找到的结果往往也不是最优解。实际上，随机法也是枚举法中的一种。（2）枚举法枚举法能够克服解析法的两点不足，它可以找到全局极值且不要求目标函数连续光滑。但其致命缺点是计算效率太低，对于许多实际问题往往会因为搜索空间太大而不可能将所有的情况一一搜索到。（3）随机法第二十四页，共四十七页。遗传算法是基于自然选择和基因遗传学原理的搜索方法，它将“优胜劣汰、适者生存”的生物进化原理引入到由待优化参数形成的编码串种群中，按照一定的适应度函数及一系列遗传操作对各个个体进行筛选，使适应度值较高的个体被保留下来，从而组成新的种群，新种群中包含了上一代的大量信息，并且引入了新的优于上一代的个体。如此周而复始，种群中各个体的适应度不断提高，直至满足一定的收敛条件。最后，以种群中适应度值最高的个体作为待优化参数的最优解。（4）遗传算法遗传算法也用到了随机搜索技术，但它通过对参数空间的随机编码并用适应度函数作为工具来引导搜索过程向着更有效的方向发展，因而它不同于常规的随机法。第二十五页，共四十七页。与常规优化方法相比，遗传算法的鲁棒性较好，其主要特点在于：

①遗传算法对参数的编码进行操作，而不是对参数本身；

②遗传算法从多个初始点开始操作，而不是从某一个点开始，这在很大程度上避免了搜索过程过早地收敛于局部极值，因此更有可能求得全局极值；

③遗传算法通过目标函数计算适应度，它不需要其它的推导运算和附加信息，因而对问题的依赖性小；

④遗传算法使用概率的操作规则，而不是确定性的规则；

⑤遗传算法在解空间中采用启发式搜索，而不是盲目的枚举或完全随机的搜索，因而搜索的效率高；

⑥遗传算法对于待寻优的问题基本没有限制，既可以是数学解析式所表示的显函数，也可以是映射矩阵或神经网络表示的隐函数，同时也不要求待优化函数连续、可微；第二十六页，共四十七页。

⑦遗传算法所具有的隐含并行性的特点，使其可以通过大规模并行搜索来提高计算速度；

⑧遗传算法适合复杂的、高度非线性问题的优化。1.4遗传算法的研究热点（1）编码方式的确定；（2）专用遗传算子的设计；（3）控制参数的选择；①种群规模：N=20~100；②交叉概率：pc=0.60~0.95；③变异概率：pm=0.001~0.01。李擎、张伟、尹怡欣、王志良．一种新的调节交叉和变异概率的自适应算法．控制与决策，2008年1月第23卷第1期：79～83第二十七页，共四十七页。2遗传算法的应用实例——车载导航系统路径规划算法的设计2.1问题简介所谓车载导航系统路径规划，就是在电子地图中找到一条从起点到终点在距离（或时间）上最短的路径。下图为一个路径规划用仿真地图，其上共有15个节点，24条弧。弧下的数据表示路径的长度（单位：公里），弧上的数据则表示该路段车辆行驶的速度（单位：米/秒）。在实际电子地图中，节点相当于道路的交叉点，弧相当于实际道路。第二十八页，共四十七页。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路径规划用仿真地图第二十九页，共四十七页。2.2遗传算法的具体应用（1）路径的表示方法这里采用符号编码方式表示实际路网中的路径。对于图6中一条从A点到P点的路径，采用符号编码方式得到的个体为A、B、E、H、L、O、P。图7仿真地图中的一条路径ABEHLOP第三十页，共四十七页。（2）初始路径的产生①传统遗传算法

随机生成初始路径，会产生断路或环路。②改进遗传算法（a）克服断路的思路从起始点出发，随机选取与起始点直接相连的一个点作为下一个节点，如此反复直到找到终点为止。在路径的产生过程中为了避免出现环路，规定在一条路径中当一个路径节点被选中以后，则给该节点一个标记，只有没有标记的节点才能被选作新的路径节点，每条初始路径选择完毕后标记全部刷新。

（b）克服环路的思路第三十一页，共四十七页。（3）适应度函数的确定①距离最短优化原则下的适应度函数②时间最优优化原则下的适应度函数其中，为第i个染色体（路径）；为第i条路径第j段的路径长度。其中，仍为第i条路径第j段的路径长度；为第i条路径第j段的行驶速度。第三十二页，共四十七页。不能象传统遗传算法那样随机进行一点、两点或多点交叉操作，因为这样很容易产生断路或环路。这里只允许使用在重复节点位置交叉且只进行一点交叉的操作方式，具体实现步骤如下：（5）交叉操作（4）复制（选择）操作采用赌轮法进行复制操作。①随机选取两个个体作为待交叉个体；②找出两个待交叉个体的共同节点（起点和终点除外）的集合；③从共同节点的集合中随机选择一个节点作为交叉节点；④检查两个待交叉个体在交叉节点之前或之后的内容是否相同。如相同，则取消本次交叉操作；否则，两者交换交叉点之前（或之后）的内容形成两个新个体。第三十三页，共四十七页。下面将结合仿真地图举例说明交叉操作是如何实现的。

①设选取的两个待交叉样本为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和第三十四页，共四十七页。图8交叉操作示意图PLOCBHIAEN第三十五页，共四十七页。（6）变异操作不能采用传统遗传算法中随机选择变异点的做法，因为这样同样容易产生断路或环路。这里采用的变异操作，其基本步骤如下：①随机选取一个个体作为待变异个体；②在待变异个体中随机选择一个节点（起点和终点除外）作为待变异节点；③找到和该待变异节点直接相连的节点集合（该集合中不包括起点、终点以及待变异个体中的节点）；④从节点集合中随机选取一个节点作为变异后节点；⑤检查待变异节点之前和之后的节点是否与变异后节点直接相连。若直接相连，则用变异后节点替代待变异节点完成变异过程；否则，放弃此次操作，回到第④步，直至将节点集合中的所有节点全部选遍。第三十六页，共四十七页。现结合仿真地图举例说明变异操作的具体实现方法。①选择待变异个体为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、P第三十七页，共四十七页。PLOFCBHIAE图9变异操作示意图第三十八页，共四十七页。（7）删除操作删除操作的具体步骤如下：

①随机选择一个个体；

②检查该个体中任意两个不相邻节点（包括起点和终点）之间是否直接相连。如果直接相连，则删除两个节点之间的所有节点，结束此次删除操作；否则，取消本次删除操作。

下面也结合仿真地图举例说明删除操作的具体实现方法。①设随机选择的个体为A、C、E、F、I、L、O、P；②检查发现E、I直接相连，则删除两者之间的节点F，从而得到新个体A、C、E、I、L、O、P第三十九页，共四十七页。PLOFCIAE图10删除操作示意图第四十页，共四十七页。（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