基于改进遗传算法的智能小车路径规划方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN114995413A(43)申请公布日2022.09.02(21)申请号202210588765.6(22)申请日2022.05.26(71)申请人南京航空航天大学地址210016江苏省南京市秦淮区御道街29号(72)发明人陈聪金智林戴丽萍吴文利(74)专利代理机构江苏圣典律师事务所32237专利代理师刘辉(51)Int.Cl.G05D1/02(2020.01)权利要求书2页说明书6页附图3页(54)发明名称基于改进遗传算法的智能小车路径规划方法(57)摘要本发明公开了一种基于改进遗传算法的智能小车路径规划方法，针对传统遗传算法具有收敛速度较慢、局部搜索能力差等缺点和容易在路径规划领域中目标不可达和易陷入局部最小值点等缺陷，改进了传统遗传算法的交叉、变异算子和适应度函数，将不同权重占比的智能小车总路径长度和智能小车行驶路径平滑度加入适应度函数并且利用轮盘赌法确定改进后的交叉算子，大幅提高了智能小车行驶路径的平滑性。加快了算法的收敛速度，降低算法达到全局最优解时的迭代次数，大大提高算法的效率。CN114995413ACN114995413A权利要求书1/2页1.基于改进遗传算法的智能小车路径规划方法，其特征在于，包括以下步骤：步骤1)，构建栅格地图，以地图左下角第一个栅格为原点建立坐标系；步骤2)，初始化种群，并初始化遗传算法的以下参数：种群数量NP、最大迭代次数max_gen；步骤3)，产生初始化可行路径：步骤3.1)，先按顺序在每一行随机选取一个无障碍栅格，形成一条包含M个栅格的间断的路径，M为路径中栅格的个数，并令i＝1；步骤3.2)，根据以下公式计算第i个栅格和i+1个栅格之间的D值：D＝max{abs(xi+1‑xi),abs(yi+1‑yi+1)}式中，(xi，yi)是第i个栅格的坐标，(xi+1，yi+1)是第i+1个栅格的坐标；步骤3.3)，判断D值是否等于1：步骤3.3.1)，若D＝1，第i个栅格和i+1个栅格为连续栅格，令i＝i+1，判断i和M的大小；步骤3.3.1.1)，若i≥M‑1，此时的路径即为初始化后可行路径，跳转执行步骤4)；步骤3.3.1.2)，若i＜M‑1，跳转执行步骤3.2)；步骤3.3.2)，若D不等于1，第i个栅格和i+1个栅格之间不连续，则根据以下公式计算第i个栅格和i+1个栅格之间中点栅格的坐标(xc，yc)：步骤3.3.2.1)，若中点栅格上无障碍，则将该中点栅格插入第i个栅格和i+1个栅格之间，使得该中点栅格变成新的第i+1个栅格，令M＝M+1，更新路径并跳转执行步骤3.2)；步骤3.3.2.2)，若中点栅格上存在障碍，则依次判断中点栅格的上、下、左、右的栅格上是否存在障碍，若均存在障碍，跳转执行步骤3.1)；若存在其上无障碍的栅格，则选择第一个无障碍的栅格作为新的中点栅格，再将该新的中点栅格插入第i个栅格和i+1个栅格之间，使得该新的中点栅格变成新的第i+1个栅格，令M＝M+1，更新路径并跳转到步骤3.2)；步骤4)，构造适应度函数fitness，考虑规划路径的长度和平滑程度加入到适应度函数fitness中；步骤4.1)，规划路径总长度d等于相邻两个栅格之间距离之和，具体公式如下：步骤4.2)，路径越平滑，相邻三点形成的角度越大，角度越大相邻三点之间的距离越大，因此计算路径中所有相邻三点的距离作为适应度函数的第二部分，考虑到智能小车行驶过程中的运动学和动力学约束，规定规划路径的转角ph的计算公式如下：步骤4.3)，根据对路径长度和路径平滑度的要求选用不同的权重构造相应的适应度函数；2CN114995413A权利要求书2/2页步骤5)，选择操作：根据适应度函数计算得出每一个个体的适应度值，再计算每一个个体的适应度值占全部个体适应度之和的比例；根据每一个个体的概率比例，使用基于概率的轮盘赌方法选择出下一代个体；步骤6)，交叉操作：步骤6.1)，首先从第一个个体开始比较两个相邻个体的适应度值大小，然后保留其中适应度值较大的个体记录其适应度值为f′，然后根据交叉概率公式计算此次交叉操作中的具体交叉概率Pc，再随机选取0‑1之间的一个数作为交叉比较概率Pcc，j＝1；步骤6.2)，从第j个种群开始比较第j个种群的交叉概率Pc和Pcc的大小，若j种群的交叉概率小于Pcc，则在j和j+1种群所包含的相同栅格中随机选取一个栅格，交换此相同栅格后面的全部路径；然后令j＝j+1，判断j是否小于种群数量，若j值小于种群数量，则重复步骤6.2)继续循环，反之则结束交叉操作；交叉概率Pc公式具体如下：其中fmax为整个迭代循环过程中的最大适应度值，是整个迭代循环过程中的平均适应度值，f′为此次交叉操作中的较大适应度值；步骤7)，变异操作：步骤