丁家会 冒宇露 顾立博 戴彦楚 吴雪倩

摘 要：针对传统路径规划算法存在路径不可达、寻优计算规模大等缺陷导致算法的计算量大、收敛精度低等问题，本文提出采用改进遗传算法优化中间节点，结合Dijkstra算法求最短路径算法补齐节点间的路径形成一条完整路径的方式，保证遗传操作中的路径全部为可行路径。与传统遗传算法作对比，试验结果表明改进后的算法在收敛精度和寻优能力上都取得了明显的效果。

关键词：遗传算法;路径规划;中间节点

中图分类号：TP301.6     文献标识码：A       文章编号：1003-5168（2021）27-0006-03

Abstract： In view of the problems of traditional path planning algorithms such as unreachable paths and large-scale optimization calculations， which lead to large calculations and low convergence accuracy， this paper proposes an improved genetic algorithm to optimize intermediate nodes， combined with Dijkstra's shortest path algorithm to fill in the path between nodes to form a complete path， to ensure that all paths in the genetic operation are feasible paths. Compared with the traditional genetic algorithm， the experimental results show that the improved algorithm has achieved obvious results in convergence accuracy and optimization ability.

Keywords： genetic algorithm; path planning; intermediate node

路徑规划研究已经进行了很多年，研究者们提出多种方法来解决此问题，不同的方法适用范围也各不相同，没有一种路径规划方法适用于所有环境信息。其中，人工势场法[1]、网格法[2]、粒子群算法[3]等是路径规划中的典型方法。但一些传统的优化算法在非线性、离散的路径规划问题中受局限较大，优化效果并不太好。因此，遗传算法凭借其较强的全局寻优能力而被广泛地应用于路径规划问题，本文提出一种基于Dijkstra算法的改进遗传算法用于求解机器人路径规划问题。

1 算法介绍

1.1 遗传算法

遗传算法实时性能良好，应用于移动机器人路径规划的基本思想是：将路径个体表示为路径中的一系列中间点，然后通过编码将其转化为数学问题。具体而言，它包括初始化路径种群，然后执行一系列遗传运算，如选择、交叉、变异等，在满足终止条件后停止进化，并输出当前的最优个体[4]。

1.2 Dijkstra算法

1959年，荷兰科学家Dijkstra提出并命名了一种求解单源点到其余顶点的最短路径问题的算法——Dijkstra算法，其思想是按路径长度递增的次序一步一步并入来求取，是贪婪算法的一个应用[5]。

2 改进算法的原理及步骤

研究发现，传统遗传算法解决路径规划问题存在以下缺陷：（1）路径个体编码设计不合理，导致进化过程中产生不可行路径;（2）遗传算子的设置参数应能在线调整。

本文中的解决方法为：对于问题（1），采用遗传算法优化中间节点，随机生成n个非障碍物的中间节点，中间节点和路径起始点间用Dijkstra算法求最短路径补齐;针对问题（2），采用改进遗传算法[6]中的自适应调节方法，从而在线调节算法中的交叉和变异概率。

改进算法进行路径规划的主要步骤：①建立栅格环境，标明障碍物、路径点与非障碍物的序列号;②确定起始和终点位置、种群数量sizepop、迭代次数itermax等初始化参数及中间节点数量n;③随机生成sizepop*n个路径节点作为初始化种群pop，采用Dijkstra求最短路算法生成完整的可行路径集合path;④将路径集合中的个体代入目标函数，根据适应度值选择个体进行下一步遗传操作;⑤对中间节点进行交叉、变异操作，直到生成新的节点种群，并得到新的路径集;⑥判断是否满足终止条件，若不满足返回④;若满足，输出最优节点和路径。

3 算法的设定

本文选用实数编码[7]方式根据path中每条路径的适应度对pop中对应的中间节点进行优化，保证算法运行过程中参与运算的路径全部都是可行解。

设置适应度函数如公式（1）所示：

其中，T表示机器人经过的路径点的数目，L表示起点与终点间所有路径点的距离之和，即一条路径的完整长度，用公式（2）表示：

其中，L（Pi，Pi+1）表示相邻两个端点间的距离。L越大，说明个体效果越差，因此将适应度值小的个体作为优秀个体，不断寻优直到找到全局最优解。

另外，采用算术交叉方式对个体进行交叉操作，交叉方式如公式（3）所示：

式中，pop表示交叉后的个体，pop1和pop2分别表示较优父代个体和较差父代个体，k取[0，0.5]区间内的任意数，使得新个体较大概率继承优秀父代。

变异方式如公式（4）所示：

式中，pop表示变异后的个体，pop（a，：）表示当前变异的个体，popmax表示终点的实数序号，nvar表示当前变异个体的长度，根据公式（4）随机生成一个新个体。

另外，交叉率和变异率的确定以文献[6]中的自适应公式为依据，如公式（5）和公式（6）所示。

其中，N1表示父代適应度值中较大者的排序号，N2为平均适应度值的排序号，N3为最大适应度值的排序号。

4 仿真实验与分析

为验证算法有效性，在静态栅格环境中对该算法进行仿真，相同环境下与传统遗传算法作对比，设置种群规模sizepop=60，最大进化代数itermax=100，自适应调整参数Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.05。传统遗传算法中随机生成初始化种群，采用轮盘赌选择法，设置交叉率Pc=0.6，变异率Pm=0.1，种群规模为60，最大进化代数为100。

在10*10和15*15栅格环境中，改进后的寻优路径及最大适应度曲线对比图分别如图1和图2所示。

对比发现，改进算法找到的路径优于传统遗传算法，证明了改进算法的优越性。从最大适应度曲线图中可以看到传统遗传算法的收敛精度低于改进算法，推测由于自适应策略的加入使得改进算法的交叉率和变异率在进化中后期变大，帮助种群跳出局部最优。

试验结果表明改进算法规划的路径比传统遗传算法规划的效率更高，其收敛速度和收敛精度都优于传统遗传算法，节约了实际工作时间。

5 结语

本文主要介绍了移动机器人在静态环境下基于改进的遗传算法实现的路径规划问题，主要工作包括构建栅格地图作为机器人的环境模型，采用改进遗传算法优化中间节点，再用Dijkstra算法求最短路算法补齐节点间的路径，这种方式得到的路径都是可行解，将离散化问题转化为连续问题。设置最短距离为适应度函数，提出算数交叉方式和随机变异策略，交叉率、变异率的设定采用自适应策略。最后仿真验证改进算法的有效性和可行性。

参考文献：

[1] 梁献霞，刘朝英，宋雪玲，等.改进人工势场法的移动机器人路径规划研究[J].计算机仿真，2018， 35（04）：291-294，361.

[2] 林巍凌.引入导航网格的室内路径规划算法[J].测绘科学，2016，41（02）：39-43.

[3] 贾会群，魏仲慧，何昕，等.基于改进粒子群算法的路径规划[J].农业机械学报，2018，49（12）：371-377.

[4] HOLLAND J H. Adaptation in natural and artificial systems[M]. Cambridge City： MIT Press， 1975.

[5] KAZUO M， AKIYOSHI S. Dijkstra's algorithm and L-concave function maximization[J]. Mathematical Programming， 2014，145（1-2）：163-177.

[6] 丁家会，张兆军.基于个体排序的自适应遗传算法[J].电子科技，2020，33（3）：6-11，32.

[7] 林丹，李敏强，寇纪凇，等.基于实数编码的遗传算法的收敛性研究[J].计算机研究与发展，2000（11）：1321-1327.