基于遗传算法机器人路径规划研究

沙勇

基于遗传算法机器人路径规划研究

沙勇

（齐齐哈尔大学学报（自然科学版）编辑部，黑龙江 齐齐哈尔 161006）

针对传统的机器人算法不是线性路径优化而导致不能较好地解决实际问题情况，介绍了采取遗传算法处理路径规划的方法解决路径规划问题的方案。

遗传算法；路径规划；机器人

目前，在机器人的路径规划研究领域，对于处理路径的优化方式一般有可视图法和人工势场法，对于传统的算法处理不是线性的路径优化问题的缺点[1]，遗传算法因其自身优势在机器人路径规划上就得到了应有的重视[2]。本文主要介绍了采取遗传算法处理路径规划的方法解决路径规划问题的方案。

1 构建环境模型

环境模型是根据传感器搜索到的全局环境信息进行环境的模型构建。该模型应该具有种群进行操作时可以保证初始条件不变的能力的稳定性，具有种群本身对外界干扰自身的保持能力鲁棒性。本文运用栅格法搭建环境模型地图。

栅格地图用大小均匀的栅格划分机器人所处的二维空间环境，栅格大小可以满足机器人的运动范围，对于2D的栅格地图，环境依次划分为均匀的栅格，每个栅格只有两种形态，包括二进制数0和1，对于占据状态，通常用1代表，对于空闲状态，通常用0代表；当处理3D的环境模型时，栅格的密集信息由每个单元格表示，用这些栅格来代表全局的环境模型。

2 初始化设置

2.1 路径编码

路径编码是一种把路径的可行解问题模拟为一种对遗传算法相对于进行全局搜索的空间进行的替换。编码的机理是算法进化过程里的前提，算法的效果主要取决于编码的合理性。本文采用标记序列号的方法进行编码，对于表示的一个个体，一般是在路径的初始位置上不出现重复与障碍物的序列号，这些路径才是合理的路径。例如，每一条染色体都是一列栅格序列号组成，它代表了机器人的路径，如图1所示。

图1 路径与相应的染色体

2.2 种群初始化

本文规划首先对种群初始化是对种群的初始化，对种群进行选择、交叉等操作，实现算法的快速性也取决于种群的初始化。在未知最优解的情况下，解决好初始化种群进而实现其优化是十分重要的。种群初始化的方法很多，在研究遗传算法时，基本遗传算法利用随机的方式初始种群，这就造成了算法的不确定性，人们对这方面的研究也越来越多，如何构造好的初始化种群成为遗传算法的一个热点[3-5]。本文运用随机操作和启发式结合的方法初始化种群，既可以加快路径规划的速度也可以有效地表示空间的信息。初始化一般包括两步。（1）为了保证路径长度的不变，在进行选择路径的时候，随机生成在中间点和对应位置的坐标之间的路径；（2）因为路径的起始位置已知，进行全局的路径搜索过程时，选择一条路径中不出现障碍物的一条，保证了算法的速度和路径的最优，由此获得其他的居中点。采用的主要方式是启发式。

为了避免安全性与平滑性对路径的干扰，从图1可以看出，这种方法的起始位置的连线上集合了生成的路径，可以得出路径不是最优的路径，需要进行进一步的优化，减少盲目性地生成种群。

3 适应度函数设计

在遗传算法之中，下一代的群体概率由上一代的适应度函数决定，遗传算法的设计取决于适应度函数的选择和设计，它是制约算法获得最优解的关键所在。算法的效率和质量都由适应度函数影响。适应度的函数为

式中，代表个体路径中的栅格数目，代表个体路径长度。由式(1)可知，函数与机器人运动的距离成正函数，所以，把函数作为适应度函数。路径的总长度，是初始位置间所有转向点之间的距离之和，用式(2)表示：

4 遗传算子操作

在本文中利用轮盘法的具体做法如下：（1）依据上面的适应度的函数逐次算出群体中的个体适应度，得到对应累积值Q，最终死亡累积值Q；（2）在[0, Q]间得到平均的随机数；（3）把Q与进行比较，第一个Q的个体被作为复制对象；（4）重复（2）,（3）项，直到得到满足的复制个体数。

由上面的方式即满足适者生存的法则，产生种群适应度最大的个体进行遗传可以获得新种群合适的路径数目。

4.1 交叉算子

交叉操作是指选择两个个体P1和P2作为父母体，将两者的部分码值进行交叉，假设有如下8位长的2个体：生成一个在1～7之间的随机的数，如果生成的数为3，把P1与P2的低3位进行交换：P1中高5位和P2中低3位构成数串二进制10001001，得到P1与P2的一个子代个体Q；P2中高5位和P1中低3位构成数串的二进制为11011110，得到P1与P2的一个子代个体2。

4.2 变异算子

变异算子的操作简单的过程就是修改数码串中某个位置中的数码，下面介绍简单的二进制编码形式。二进制中的数码只有0和1两种形式，以下面的二进制数码为例表示：它的码长是8，随机生成一个1至8里的数值，假如现在=5，对从右向左的第5位做变异操作，把原来的0变成1。二进制编码就是简单的将0与1互换：0变异为1，1变异为0。TSP变异操作：随机生成一个1至里的数，开始对回路中的第个的代码作变异操作，又生成一个1至之间的数，代替，12，注意数在数串里出现了重复，删除和相重复的即可获得合法染色体。

本文采用最佳适应度值过半的方法，它的意思就是当种群中包含一半以上的染色体达到相同的适应度，且种群平均适应值保持不变，终止种群就确定下来了。

[1] 肖南峰. 智能机器人[M]. 广州：华南理工大学出版社，2008: 12-15.

[2] 刘天孚，程如意. 基于遗传算法的移动机器人路径规划[J]. 计算机工程，2008, 34(17): 214-215．

[3] 张洪. 移动机器人动态路径规划方法研究[D]. 无锡：江南大学，2011: 25-28.

[4] 吕微. 基于混沌免疫遗传算法的优化问题研究[D]. 大庆：大庆石油学院，2010.

[5] 张雷，王道波，段海滨. 基于粒子群优化算法的无人战斗机路径规划方法[J]. 系统工程与电子技术，2008, 30(3): 506-510.

Research on robot path planning based on genetic algorithm

SHA Yong

(Journal of Qiqihar University(Natural Science Edition) Editorial Department, Heilongjiang Qiqihar 161006, China)

For the problem that the traditional robot algorithm is not linear path optimization and can not solve the problem well, this paper introduces the solution of path planning using genetic algorithm to solve the problem.

genetic algorithm；path planning；robot

2021-04-20

齐齐哈尔市科技局工业公关项目（440036）

沙勇（1963-），男，黑龙江齐齐哈尔人，副编审，本科，主要从事编辑工程、自动化应用研究，shayong10@163.com。

TP242;TP18

A

1007-984X(2021)05-0055-02