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

16 04 2020 北京科技大学自动化学院控制科学与工程系 1 遗传算法及其在路径规划中的应用 北京科技大学自动化学院控制科学与工程系 16 04 2020 北京科技大学自动化学院控制科学与工程系 2 参考书目 16 04 2020 北京科技大学自动化学院控制科学与工程系 3 20世纪60年代 美 德等国家的一些科学家开始模仿生物和人类进化的方法来求解复杂优化问题 从而形成了模拟进化优化方法 OptimizationMethodbySimulatedEvolution 其代表性方法有遗传算法 GA GeneticAlgorithms 进化规划 EP EvolutionaryProgramming 进化策略 ES EvolutionaryStrategies 本讲将主要对GA进行详细介绍 常规的数学优化技术基于梯度寻优技术 计算速度快 但要求优化问题具有可微性 且通常只能求得局部最优解 而模拟进化方法无可微性要求 适用于任意的优化问题 尤其适用于求解组合优化问题以及目标函数不可微或约束条件复杂的非线性优化问题 由于它们采用随机优化技术 所以会以较大的概率求得全局最优解 其计算费用较高的问题也因计算机软硬件技术的飞速发展而不再成为制约因素 1遗传算法产生的背景 16 04 2020 北京科技大学自动化学院控制科学与工程系 4 1 1遗传算法的基本概念 1 1 1进化的基本理论 1 Darwin生物进化论 2 Mendel自然遗传学说 1 1 2遗传算法术语简介 1 个体 染色体 遗传算法求解实际问题时 首先对待优化问题的参数进行编码 一般采用二进制码串表示 从而得到一个字符串 该字符串被称为一个个体 individual 或一个染色体 chromosome 2 种群 群体 所有个体的集合 population 3 种群规模 种群中个体的数量称为种群规模 populationsize 4 基因 个体中的每一位称为一个基因 gene 5 适应度函数 能够评价个体对环境适应能力的函数 fitnessfunction 16 04 2020 北京科技大学自动化学院控制科学与工程系 5 1 1 3遗传算法应用引例 例 求的最大值 解 1 编码方式的确定 采用五位二进制代码表示变量x 2 初始种群的产生 设种群规模N 4 随机产生初始种群如表1所示 16 04 2020 北京科技大学自动化学院控制科学与工程系 6 3 适应度函数值的计算 取适应度函数为f x x2 则4个样本的适应度值分别如下表所示 16 04 2020 北京科技大学自动化学院控制科学与工程系 7 4 复制 采用赌轮法计算各个个体被复制的次数 16 04 2020 北京科技大学自动化学院控制科学与工程系 8 5 交叉 采用随机交叉配对 一点交叉方式进行交叉 16 04 2020 北京科技大学自动化学院控制科学与工程系 9 6 变异 采用单点随机变异方式进行变异操作 16 04 2020 北京科技大学自动化学院控制科学与工程系 10 1 2遗传算法的基本步骤 1 2 1遗传算法的流程 16 04 2020 北京科技大学自动化学院控制科学与工程系 11 1 2 2遗传算法的具体实现 1 编码方式的选取 利用遗传算法求解实际问题时 问题的解是用字符串来表示的 遗传算子也是直接对字符串进行操作的 因此 如何用适当的字符串编码来表示问题的解成为了遗传算法应用过程中的首要问题 目前所使用的字符串编码方式主要有 二进制 实数 浮点数 和符号等 1 采用二进制形式编码 个体的位数多 描述得比较细致 从而加大了搜索范围 但交叉运算的计算量较大 并且由于大量的具体问题本身都是十进制的 所以还需对实际参数进行编码和译码 从而增加了额外的计算时间 2 采用实数 浮点数 编码 交叉运算的计算量较小 但变异过程难于进行 3 符号编码方式通常在一些专门的应用场合使用 16 04 2020 北京科技大学自动化学院控制科学与工程系 12 2 初始种群的产生 初始种群对应着问题的初始解 通常有两种方式产生 完全随机方式产生 字符串每一位均随机产生 随机数发生器方式产生 整个字符串用随机数发生器一次产生 另外 如果对于寻优问题有某些先验知识 则可先将这些先验知识转变为必须满足的一组约束 然后再在满足这些约束的解中随机地选取个体以组成初始种群 3 适应度函数的确定 适应度函数是遗传算法与实际优化问题之间的接口 在遗传算法中要求适应度函数值是非负的 且任何情况下都希望其值越大越好 而实际优化问题的目标函数并不一定满足这个条件 有的是正的 有的可能为负 甚至可能是复数值 因此 对于任意优化问题 首先应把其数学形式表示为遗传算法适于求解的形式 同时要保证二者在数学优化层面上是等价的 这个过程称为适应度转换 16 04 2020 北京科技大学自动化学院控制科学与工程系 13 适应度转换首先要保证适应度值是非负的 其次要求目标函数的优化方向应与适应度值增大的方向一致 设实际优化问题的目标函数为J x 遗传算法的适应度函数为f x 则有 可以将适应度函数表示为实际优化问题目标函数的线性形式 即有 其中 a b是系数 可根据具体问题的特征及所期望适应度的分散程度来确定 对于最小化问题 一般采用如下转换形式 其中 cmax既可以是到目前为止所有进化代中目标函数J x 的最大值 此时cmax将随着进化而有所变化 也可以根据经验人为设定 16 04 2020 北京科技大学自动化学院控制科学与工程系 14 对于最大化问题 如需要 一般采用如下转换形式 其中 cmin既可以是当前代中目标函数J x 的最小值 也可以根据经验人为设定 采用如下的指数函数形式 在最大化问题时 c一般取1 618或2 而在最小化问题时 c可取为0 618 这样 既保证了适应度值非负 又使适应度值增大方向和目标函数优化方向一致 16 04 2020 北京科技大学自动化学院控制科学与工程系 15 4 复制 选择 ReproductionorSelection 复制是基于适者生存理论而提出的 是指种群中每一个体按照适应度函数进入到匹配池中的过程 适应度值高于种群平均适应度的个体在下一代中将有更多的机会繁殖一个或多个后代 而低于平均适应度的个体则有可能被淘汰掉 复制的目的在于保证那些适应度高的优良个体在进化中生存下去 复制不会产生新的个体 常用的复制方法有 赌轮法 两两竞争法 从种群中随机地选择两个个体 将其中适应度较大的个体作为被复制的个体 若两个体适应度相同 则任意选择一个 排序法 首先根据目标函数值的大小将个体排序 根据具体问题应用各个体的排序序号分配各自进入匹配池的概率 适应度可以按序号线性变化 也可以按某种非线性关系变化 16 04 2020 北京科技大学自动化学院控制科学与工程系 16 5 交叉 Crossover 交叉是指对从匹配池中随机选出的两个个体按一定的交叉概率pc部分地交换某些基因的过程 一般分两步实现 第一步是将新复制产生的匹配池中的个体随机两两配对 第二步是进行交叉繁殖 产生一对新的个体 交叉的目的是为了生成新的个体 产生新的基因组合 避免每代种群中个体的重复 单点交叉 One PointCrossover 对每一对相互配对的个体 依设定的交叉概率pc在其交叉点处相互交换两个父代个体的部分染色体 从而产生出两个新的个体 如下图所示 16 04 2020 北京科技大学自动化学院控制科学与工程系 17 两点交叉 Two PointCrossover 按交叉概率随机设置两个交叉点 然后交换两个父代个体在两个交叉点之间的基因 均匀交叉 UniformCrossover 其操作过程是 先选出两个父代个体 之后依据交叉概率pc产生一个与父代个体同样长度的二进制串 这里称其为模板 template 若模板中的某位为0 则两个父代个体对应位不进行交换 反之 模板中的某位为1时 则交换两个父代个体对应位的基因 16 04 2020 北京科技大学自动化学院控制科学与工程系 18 算数交叉 ArithmeticCrossover 算数交叉的操作对象一般是由浮点数编码所表示的个体 它通过两个父代个体的线性组合而产生出两个新的个体 假设在两个父代个体 之间进行算数交叉 则交叉运算后所产生出的两个新个体是 式中为一参数 它若是一个常数 此时所进行的交叉运算称为均匀算数交叉 它也可以是一个由进化代数所决定的变量 此时所进行的交叉运算称为非均匀算数交叉 16 04 2020 北京科技大学自动化学院控制科学与工程系 19 6 变异 Mutation 一般的变异操作只作用于采用二进制编码的某单个个体 它以一定的变异概率pm对个体的某些位进行取反操作 如同自然界很少发生基因突变一样 变异概率pm一般都取得比较小 变异的目的是为了增加种群个体的多样性 防止丢失一些有用的遗传模式 在简单遗传算法中 变异就是将某个体中某一位的值作取反运算 16 04 2020 北京科技大学自动化学院控制科学与工程系 20 7 收敛判据 常规的优化方法有数学上比较严格的收敛判据 而遗传算法的收敛判据通常是启发式的 由于遗传算法没有利用梯度信息 因此要从数学上构造比较严格的收敛判据相当困难 常用的收敛判据有 根据计算时间和所采用计算机的性能确定收敛判据 一般采用指定最大迭代次数的方法 从解的质量方面确定判据 如果连续几代 或几十代 种群中的最优解没有变化 则认为算法收敛 或种群中最优个体的适应度与平均适应度之差和平均适应度的比值小于某一给定值时 也可以认为算法已经收敛 16 04 2020 北京科技大学自动化学院控制科学与工程系 21 8 约束条件的处理 遗传算法在求解有约束的优化问题时 需对约束条件进行必要的处理 处理方式有 直接体现在字符串的编码中 对于优化问题中变量的上 下限约束 可以让字符串表示的最大值和最小值分别对应于实际约束变量的上 下限值 设待优化变量x的变化范围为 xmin xmax 如用l位的二进制字符串y来表示 则x y之间有如下关系 判断舍弃法 在遗传算法的运算过程中 检查得到字符串所对应的解是否为可行解 若是 则加入到下一代种群中 否则将其舍弃 惩罚函数法 如果一个解违反了某个约束 则视其违反程度给予一定的惩罚 使其具有较小的适应度 越限越严重 适应度就越小 16 04 2020 北京科技大学自动化学院控制科学与工程系 22 1 3遗传算法的特点 目前常规的优化方法主要有3种类型 解析法 枚举法和随机法 解析法是优化方法中研究最多的一种 它又分为直接法和间接法 直接法是一种通过沿着梯度信息最陡的方向逐渐运动来寻找局部极值的方法 间接法则是一种通过使目标函数梯度为零 进而通过求解一组非线性方程来寻找局部极值的方法 1 解析法 解析法的主要问题在于 1 要求目标函数连续光滑且可微 2 一般只能找到局部极值而非全局极值 故对于存在多峰极值的优化问题有时显得无能为力 16 04 2020 北京科技大学自动化学院控制科学与工程系 23 随机法能够克服上述两种方法的缺陷 它在搜索空间中随机地漫游并记录下所找到的最优结果 当搜索到一定程度后便终止 当然 它所找到的结果往往也不是最优解 实际上 随机法也是枚举法中的一种 2 枚举法 枚举法能够克服解析法的两点不足 它可以找到全局极值且不要求目标函数连续光滑 但其致命缺点是计算效率太低 对于许多实际问题往往会因为搜索空间太大而不可能将所有的情况一一搜索到 3 随机法 16 04 2020 北京科技大学自动化学院控制科学与工程系 24 遗传算法是基于自然选择和基因遗传学原理的搜索方法 它将 优胜劣汰 适者生存 的生物进化原理引入到由待优化参数形成的编码串种群中 按照一定的适应度函数及一系列遗传操作对各个个体进行筛选 使适应度值较高的个体被保留下来 从而组成新的种群 新种群中包含了上一代的大量信息 并且引入了新的优于上一代的个体 如此周而复始 种群中各个体的适应度不断提高 直至满足一定的收敛条件 最后 以种群中适应度值最高的个体作为待优化参数的最优解 4 遗传算法 遗传算法也用到了随机搜索技术 但它通过对参数空间的随机编码并用适应度函数作为工具来引导搜索过程向着更有效的方向发展 因而它不同于常规的随机法 16 04 2020 北京科技大学自动化学院控制科学与工程系 25 与常规优化方法相比 遗传算法的鲁棒性较好 其主要特点在于 遗传算法对参数的编码进行操作 而不是对参数本身 遗传算法从多个初始点开始操作 而不是从某一个点开始 这在很大程度上避免了搜索过程过早地收敛于局部极值 因此更有可能求得全局极值 遗传算法通过目标函数计算适应度 它不需要其它的推导运算和附加信息 因而对问题的依赖性小 遗传算法使用概率的操作规则 而不是确定性的规则 遗传算法在解空间中采用启发式搜索 而不是盲目的枚举或完全随机的搜索 因而搜索的效率高 遗传算法对于待寻优的问题基本没有限制 既可以是数学解析式所表示的显函数 也可以是映射矩阵或神经网络表示的隐函数 同时也不要求待优化函数连续 可微 16 04 2020 北京科技大学自动化学院控制科学与工程系 26 遗传算法所具有的隐含并行性的特点 使其可以通过大规模并行搜索来提高计算速度 遗传算法适合复杂的 高度非线性问题的优化 1 4遗传算法的研究热点 1 编码方式的确定 2 专用遗传算子的设计 3 控制参数的选择 种群规模 N 20 100 交叉概率 pc 0 60 0 95 变异概率 pm 0 001 0 01 李擎 张伟 尹怡欣 王志良 一种新的调节交叉和变异概率的自适应算法 控制与决策 2008年1月第23卷第1期 79 83 16 04 2020 北京科技大学自动化学院控制科学与工程系 27 2遗传算法的应用实例 车载导航系统路径规划算法的设计 2 1问题简介 所谓车载导航系统路径规划 就是在电子地图中找到一条从起点到终点在距离 或时间 上最短的路径 下图为一个路径规划用仿真地图 其上共有15个节点 24条弧 弧下的数据表示路径的长度 单位 公里 弧上的数据则表示该路段车辆行驶的速度 单位 米 秒 在实际电子地图中 节点相当于道路的交叉点 弧相当于实际道路 16 04 2020 北京科技大学自动化学院控制科学与工程系 28 16 04 2020 北京科技大学自动化学院控制科学与工程系 29 2 2遗传算法的具体应用 1 路径的表示方法 这里采用符号编码方式表示实际路网中的路径 对于图6中一条从A点到P点的路径 采用符号编码方式得到的个体为A B E H L O P 16 04 2020 北京科技大学自动化学院控制科学与工程系 30 2 初始路径的产生 传统遗传算法 随机生成初始路径 会产生断路或环路 改进遗传算法 a 克服断路的思路 从起始点出发 随机选取与起始点直接相连的一个点作为下一个节点 如此反复直到找到终点为止 在路径的产生过程中为了避免出现环路 规定在一条路径中当一个路径节点被选中以后 则给该节点一个标记 只有没有标记的节点才能被选作新的路径节点 每条初始路径选择完毕后标记全部刷新 b 克服环路的思路 16 04 2020 北京科技大学自动化学院控制科学与工程系 31 3 适应度函数的确定 距离最短优化原则下的适应度函数 时间最优优化原则下的适应度函数 其中 为第i个染色体 路径 为第i条路径第j段的路径长度 其中 仍为第i条路径第j段的路径长度 为第i条路径第j段的行驶速度 16 04 2020 北京科技大学自动化学院控制科学与工程系 32 不能象传统遗传算法那样随机进行一点 两点或多点交叉操作 因为这样很容易产生断路或环路 这里只允许使用在重复节点位置交叉且只进行一点交叉的操作方式 具体实现步骤如下 5 交叉操作 4 复制 选择 操作 采用赌轮法进行复制操作 随机选取两个个体作为待交叉个体 找出两个待交叉个体的共同节点 起点和终点除外 的集合 从共同节点的集合中随机选择一个节点作为交叉节点 检查两个待交叉个体在交叉节点之前或之后的内容是否相同 如相同 则取消本次交叉操作 否则 两者交换交叉点之前 或之后 的内容形成两个新个体 16 04 2020 北京科技大学自动化学院控制科学与工程系 33 下面将结合仿真地图举例说明交叉操作是如何实现的 设选取的两个待交叉样本为A B E I L O P和A C E H L N P 两者重复节点的集合为 E L 随机选择E作为交叉节点 检查发现两者待交叉样本在E点之前和之后的内容均不相同 因此可以进行此次交叉操作 交叉后的新个体为 A B E H L N P A C E I L O P 和 16 04 2020 北京科技大学自动化学院控制科学与工程系 34 16 04 2020 北京科技大学自动化学院控制科学与工程系 35 6 变异操作 不能采用传统遗传算法中随机选择变异点的做法 因为这样同样容易产生断路或环路 这里采用的变异操作 其基本步骤如下 随机选取一个个体作为待变异个体 在待变异个体中随机选择一个节点 起点和终点除外 作为待变异节点 找到和该待变异节点直接相连的节点集合 该集合中不包括起点 终点以及待变异个体中的节点 从节点集合中随机选取一个节点作为变异后节点 检查待变异节点之前和之后的节点是否与变异后节点直接相连 若直接相连 则用变异后节点替代待变异节点完成变异过程 否则 放弃此次操作 回到第 步 直至将节点集合中的所有节点全部选遍 16 04 2020 北京科技大学自动化学院控制科学与工程系 36 现结合仿真地图举例说明变异操作的具体实现方法 选择待变异个体为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 16 04 2020 北京科技大学自动化学院控制科学与工程系 37 16 04 2020 北京科技大学自动化学院控制科学与工程系 38 7 删除操作 删除操作的具体步骤如下 随机选择一个个体 检查该个体中任意两个不相邻节点 包括起点和终点 之间是否直接相连 如果直接相连 则删除两个节点之间的所有节点 结束此次删除操作 否则 取消本次删除操作 下面也结合仿真地图举例说明删除操作的具体实现方法 设随机选择的个体为A C E F I L O P 检查发现E I直接相连 则删除两者之间的节点F 从而得到新个体 A C E I L O P