CN114995413A - 基于改进遗传算法的智能小车路径规划方法 - Google Patents

Abstract

本发明公开了一种基于改进遗传算法的智能小车路径规划方法，针对传统遗传算法具有收敛速度较慢、局部搜索能力差等缺点和容易在路径规划领域中目标不可达和易陷入局部最小值点等缺陷，改进了传统遗传算法的交叉、变异算子和适应度函数，将不同权重占比的智能小车总路径长度和智能小车行驶路径平滑度加入适应度函数并且利用轮盘赌法确定改进后的交叉算子，大幅提高了智能小车行驶路径的平滑性。加快了算法的收敛速度，降低算法达到全局最优解时的迭代次数，大大提高算法的效率。

Description

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

技术领域

本发明涉及智能小车路径规划领域，尤其涉及一种基于改进遗传算法的智能小车路径规划方法。

背景技术

路径规划技术是移动智能小车研究领域的一个重要组成部分，主要目的是在有障碍物的环境中，根据一定的准则(如路径最短，位置拐点最少，用时最短等)，寻求一条从起始位置节点到目标位置节点之间的最优或次优安全无碰路径。

遗传算法(Genetic Algorithm，GA)属于进化算法(Evolutionary Algorithms)的一种，它通过模仿自然界的选择与遗传的机理来寻找最优解。遗传算法有三个基本算子：选择、交叉和变异。相比较其他优化算法，遗传算法具备与问题领域无关切快速随机的搜索能力、搜索使用评价函数启发，过程简单、具有可扩展性，容易与其他算法结合等优点。但同时，遗传算法的缺点也十分明显，如算法对初始种群的选择有一定的依赖性、要求对问题进行合理编码、三个算字的若干参数的选择等。针对这些不足，国内外诸多学者都尝试着对传统的遗传算法进行改进，李东东等人提出了一种遗传算法(CN113917925A)，将蚁群算法和遗传算法的结合，从而提高算法的收敛速度；中国人民公安大学的金晋等人(CN105988468A)提出一种改进的和栅格法结合起来的遗传算法，有效提高了算法的收敛速度。

但是传统遗传算法的交叉、变异算子仍是主要影响遗传算法的收敛速度、迭代次数和最优解的精确度的重要因素。

发明内容

本发明所要解决的技术问题是针对背景技术中所涉及到的缺陷，提供一种基于改进遗传算法的智能小车路径规划方法，能够克服传统遗传算法初代解质量低、收敛速度慢等不足，不仅提高了获得智能小车路径规划的全局最优解，而且提高了收敛的速度。

本发明为解决上述技术问题采用以下技术方案：

一种改进遗传算法的智能小车路径规划方法，包括以下步骤：

步骤1)，构建栅格地图，以地图左下角第一个栅格为原点建立坐标系；

步骤2)，初始化种群，并初始化遗传算法的以下参数：种群数量NP、最大迭代次数max_gen；

步骤3)，产生初始化可行路径：

步骤3.1)，先按顺序在每一行随机选取一个无障碍栅格，形成一条包含M个栅格的间断的路径，M为路径中栅格的个数，并令i＝1；

步骤3.2)，根据以下公式计算第i个栅格和i+1个栅格之间的D值：

D＝max{abs(x_i+1-x_i),abs(y_i+1-y_i+1)}

式中，(x_i，y_i)是第i个栅格的坐标，(x_i+1，y_i+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个栅格之间中点栅格的坐标(x_c，y_c)：

步骤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)，根据对路径长度和路径平滑度的要求选用不同的权重构造相应的适应度函数；

步骤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公式具体如下：

其中f_max为整个迭代循环过程中的最大适应度值，

是整个迭代循环过程中的平均适应度值，f′为此次交叉操作中的较大适应度值；

步骤7)，变异操作：

步骤7.1)，首先从第一个个体开始比较两个相邻个体的适应度值大小，然后保留其中适应度值较大的个体记录其适应度值为f′，然后根据交叉概率公式计算此次变异操作中的具体变异概率Pm，再随机选取0-1之间的一个数作为交叉比较概率Pmm，k＝1；

步骤7.2)，从第k个种群开始比较第k个种群的交叉概率Pm，若j种群的变异概率小于k+1，则在k和k+1种群所包含的相同栅格中随机选取一个栅格，交换此相同栅格后面的全部路径；然后令k＝k+1，判断k是否小于种群数量，若k值小于种群数量，则重复步骤7.2)变异概率Pm公式具体如下：

步骤8)，重复步骤5)至步骤7)max_gen次，得到迭代平均路径长度和最优路径长度，输出遗传算法的收敛曲线图。

作为本发明一种改进遗传算法的智能小车路径规划方法进一步的优化方案，所述种群数量NP＝200，最大迭代次max_gen＝100。

本发明采用以上技术方案与现有技术相比，具有以下技术效果：

1.本发明在传统遗传算法的基础上使用了具有自适应性质的交叉、变异算子，有效解决了传统遗传算法固定交叉、变异算子造成的收敛速度慢和“早熟”等问题；

2.本发明在传统遗传算法的基础上使用的具有自适应性质的交叉、变异算子有效提高了传统遗传算法的最优解质量；

3.本发明在传统遗传算法的基础上使用的具有自适应性质的交叉、变异算子能与其他算法结合形成混合遗传算法，应用前景广阔。

附图说明

图1为本发明的改进传统遗传算法的智能小车路径规划方法的控制流程图；

图2为改进遗传算法运行结果图；

图3为改进遗传算法收敛曲线图；

图4为传统遗传算法运行结果图；

图5为传统遗传算法收敛曲线图。

具体实施方式

下面结合附图对本发明的技术方案做进一步的详细说明：

本发明可以以许多不同的形式实现，而不应当认为限于这里所述的实施例。相反，提供这些实施例以便使本公开透彻且完整，并且将向本领域技术人员充分表达本发明的范围。在附图中，为了清楚起见放大了组件。

如图1所示，本发明公开了一种改进遗传算法的智能小车路径规划方法，包括以下步骤：

步骤1)，构建栅格地图，以地图左下角第一个栅格为原点建立坐标系；

步骤2)，初始化种群，并初始化遗传算法的以下参数：种群数量NP、最大迭代次数max_gen；

步骤3)，产生初始化可行路径：

步骤3.1)，先按顺序在每一行随机选取一个无障碍栅格，形成一条包含M个栅格的间断的路径，M为路径中栅格的个数，并令i＝1；

步骤3.2)，根据以下公式计算第i个栅格和i+1个栅格之间的D值：

D＝max{abs(x_i+1-x_i),abs(y_i+1-y_i+1)}

式中，(x_i，y_i)是第i个栅格的坐标，(x_i+1，y_i+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个栅格之间中点栅格的坐标(x_c，y_c)：

步骤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)，根据对路径长度和路径平滑度的要求选用不同的权重构造相应的适应度函数；

步骤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公式具体如下：

其中f_max为整个迭代循环过程中的最大适应度值，

是整个迭代循环过程中的平均适应度值，f′为此次交叉操作中的较大适应度值；

步骤7)，变异操作：

步骤7.1)，首先从第一个个体开始比较两个相邻个体的适应度值大小，然后保留其中适应度值较大的个体记录其适应度值为f′，然后根据交叉概率公式计算此次变异操作中的具体变异概率Pm，再随机选取0-1之间的一个数作为交叉比较概率Pmm，k＝1；

步骤7.2)，从第k个种群开始比较第k个种群的交叉概率Pm，若j种群的变异概率小于k+1，则在k和k+1种群所包含的相同栅格中随机选取一个栅格，交换此相同栅格后面的全部路径；然后令k＝k+1，判断k是否小于种群数量，若k值小于种群数量，则重复步骤7.2)变异概率Pm公式具体如下：

步骤8)，重复步骤5)至步骤7)max_gen次，得到迭代平均路径长度和最优路径长度，输出遗传算法的收敛曲线图。

种群数量NP优先取200，最大迭代次max_gen优先取100。

具体算法运行结果如图2、图3、图4、图5所示，根据MATLAB仿真可得出，图5所示的传统遗传算法的迭代次数达到80次方才得到最优解，而图3所示的改进遗传算法的迭代次数仅为40次便可获得最优解，且改进遗传算法所得到的的最优路径值略小于传统遗传算法。综上可得出改进遗传算法能够有效降低迭代次数，提高收敛速度的同时还能获取更佳的最优解。

针对传统遗传算法固定交叉、变异算子所导致的收敛速度慢等问题，本发明提供了一种改进的自适应交叉、变异算子计算方法。通过将交叉、变异算子的具体计算方法和每次交叉、变异操作过程中个体的适应度值联系起来，以保证适应度值大的个体尽可能保留下来的同时避免算法提前收敛，出现“早熟”现象，保证个体总是向着好的方向变异，有效提高了算法的收敛速度，降低了迭代次数，改善了传统遗传算法的最优解。

本技术领域技术人员可以理解的是，除非另外定义，这里使用的所有术语(包括技术术语和科学术语)具有与本发明所属领域中的普通技术人员的一般理解相同的意义。还应该理解的是，诸如通用字典中定义的那些术语应该被理解为具有与现有技术的上下文中的意义一致的意义，并且除非像这里一样定义，不会用理想化或过于正式的含义来解释。

以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (2)

1.基于改进遗传算法的智能小车路径规划方法，其特征在于，包括以下步骤：

步骤1)，构建栅格地图，以地图左下角第一个栅格为原点建立坐标系；

步骤2)，初始化种群，并初始化遗传算法的以下参数：种群数量NP、最大迭代次数max_gen；

步骤3)，产生初始化可行路径：

步骤3.1)，先按顺序在每一行随机选取一个无障碍栅格，形成一条包含M个栅格的间断的路径，M为路径中栅格的个数，并令i＝1；

步骤3.2)，根据以下公式计算第i个栅格和i+1个栅格之间的D值：

D＝max{abs(x_i+1-x_i),abs(y_i+1-y_i+1)}

式中，(x_i，y_i)是第i个栅格的坐标，(x_i+1，y_i+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个栅格之间中点栅格的坐标(x_c，y_c)：

步骤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)，根据对路径长度和路径平滑度的要求选用不同的权重构造相应的适应度函数；

步骤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公式具体如下：

其中f_max为整个迭代循环过程中的最大适应度值，

是整个迭代循环过程中的平均适应度值，f′为此次交叉操作中的较大适应度值；

步骤7)，变异操作：

步骤7.1)，首先从第一个个体开始比较两个相邻个体的适应度值大小，然后保留其中适应度值较大的个体记录其适应度值为f′，然后根据交叉概率公式计算此次变异操作中的具体变异概率Pm，再随机选取0-1之间的一个数作为交叉比较概率Pmm，k＝1；

步骤7.2)，从第k个种群开始比较第k个种群的交叉概率Pm，若j种群的变异概率小于k+1，则在k和k+1种群所包含的相同栅格中随机选取一个栅格，交换此相同栅格后面的全部路径；然后令k＝k+1，判断k是否小于种群数量，若k值小于种群数量，则重复步骤7.2)变异概率Pm公式具体如下：

步骤8)，重复步骤5)至步骤7)max_gen次，得到迭代平均路径长度和最优路径长度，输出遗传算法的收敛曲线图。

2.根据权力要求1所述的基于改进遗传算法的智能小车路径规划方法，其特征在于，所述种群数量NP＝200，最大迭代次max_gen＝100。

Images