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

焦合军，周万春，李渊博

(郑州工程技术学院 机电与车辆工程学院，河南 郑州 450044)

1 引言

移动机器人的路径规划是机器人导航技术中一个重要的组成部分。移动机器人可以在预先设定的条件下，按照一定的规则，从起点到终点并避开障碍物寻找一条最优路径，该路径长度小，消耗时间少。路径规划有全局和局部之分，全局路径规划着眼于已知路径信息，局部路径规划着眼于未知的环境信息[1]。

目前在移动机器人全局路径规划中，常用的进化算法有遗传算法、人工鱼群算法[2]、粒子群算法和蚁群算法等。然而，传统的遗传算法求解过程耗时长，生成的路径没能达到最优避障；蚁群算法收敛的速度比较慢，容易出现停滞，陷入局部最优；人工鱼群算法在优化初期有很好的收敛性，后期收敛较慢，并且随着人工鱼的增多，造成存储需求大、计算量大的缺点；粒子群算法有较快逼近最优解的能力，可以对系统参数进行有效的优化，优势在于对连续函数的优化，其缺点是容易早熟收敛，局部寻优能力变差。

本文针对一般的遗传算法进行改进，在遗传操作时加入A*算法，调整交叉和变异的概率，不仅使前期进化能力增强，改进交叉和变异方法，催生新的染色个体能力加强，又提高了算法的搜索效率。

2 路径规划

2.1 环境模型建立

在对机器人路径建模时，首先要对其环境地图进行平面化处理，使用栅格地图是简单有效的方法。在栅格图中，黑格表示障碍物，白格代表机器人可以经过的自由空间。使用序号标记法进行栅格标记，按照从左到右，从上到下的原则依次加1进行标记。在图1所示的模型中，S,2,3,…,99 ，E等称为栅格节点，S 为机器人起始点位置，E为目标点位置。给定栅格序号T(i,j)与直角坐标点P(i,j)[X(i,j),Y(i,j)]的关系如下：

(1)

2.2 编码方式

遗传算法中的染色体是一组个体编码，针对机器人路径规划问题，我们定义为从起始点到终点的一条路径。为了保证路径的可靠性和实用性，路径中不可出现重复序号和障碍物序号[3]。如图2所示，一条有效路径可以表示为：S→12→23→33→44→54→65→75→85→86→87→88→98→99→E。

2.3 种群初始化

使用栅格法进行路径规划时，机器人在周围无障碍的情况下可以向左、左上、左下、右、右上、右下、上、下8个方向移动。文中将A*算法用于遗传算法的初始化，随机分配一个无障碍点，在已有起始点和终点利用A*算法建立链接，具体的实现步骤如下：

第一步 将起点坐标和终点坐标(如图 1中的S和E)加入染色体编码中；

图1 机器人路径规划地图模型

第二步 在地图模型中加入1 个无障碍随机点作为目标点，利用A*算法分别建立起始点到该点以及该点到终点的路径，在路径建立过程中避免障碍点和外围区域，之后将起始点和终点链接起来；

第三步 种群要保持染色体的差异性，对路径节点一模一样的进行删除，最终生成一个集合。此刻结束初始化。

图2 地图序号标记

2.4 适应度函数

采用机器人从起始点到终点的路程作为路径规划的适应度评价，所以在路程的规划指标下，分别得适应度函数为[4-5]：

(2)

2.5 遗传操作

2.5.1 选择算子

为了选出适应度较好的一部分个体，结合贪心算法，在初始种群中，算出适应度的平均值，每个染色体个体的适应度值与该平均值比较，如果大于平均值，保留该染色体个体，否则，丢弃该个体。每次迭代，重复此操作。这种选择方法，保证了每次迭代使种群向优秀方向过渡。通过与平均值的比较，不仅保证了个体的多样性，而且保证了种群的稳态繁殖。

2.5.2 交叉算子

在种群中找出一对有共同点的染色体，共同点不是起始点和终点，随机选择其中一个共同点，交换这两个染色体的前半部分路径点，染色体交叉示意如图3所示，图中a,c两个图的染色体在序号点处交叉，生成b,d图中两个染色体。

2.5.3 变异操作

变异操作对遗传算法最优解的产生有积极的作用，变异操作可以防止遗传算法陷入早熟和局部最优的环境。在一条全路径上选取除了起始点和终点的两个随机节点，根据A*算法生成一条两个节点间的路径，代替两个节点的原路径。为了避免优秀路径不被破坏，变异操作后期要考虑减少或停止变异操作。例如：个体变异前为 V ={S，11，…，96，87，98，99，E} ，变异节点为96和98，产生的新路径为：C ={S，11，…，96，97，98，99，E}。

2.7 混合遗传算法流程

首先利用A*算法产生原始种群，并得出各个个体的适应度值，之后选择并以一定概率进行交叉和变异操作找出最优解的个体，最后判断是否符合结束条件，在进行个体适应度数值和最优解之间进行比较，满足结束条件，退出遗传操作，否则继续交叉和变异，生成新一代种群[6]。该算法的步骤如图4所示。

3 仿真分析

为了证明算法的合理性，本文在Visual C++环境中分别编写了路径规划的一般遗传算法和混合遗传算法，对比两种算法的特点。由于具体尺寸上没有指定，本文用数字表示相关参数。栅格的尺寸为10×10，起点为(0,0)，终点为(9,9)，在 2个地图环境下得到的路径长度和收敛速度如图5、6所示。

图3 交叉操作示意图

图4 混合遗传算法的步骤

对于一般遗传算法，遗传种群数目为50，变异和交叉的概率为0.06和0.9，最大迭代数为50；对于本文提出的算法，种群数目为50，5次迭代前交叉率是0.9，5代后交叉率为0.3，5代前变异率为0.06，5代后变异率为0.01，最大遗传代数为50。

两种算法结果不同，一般遗传算法最佳路径长16.5228，混合遗传算法的最优路径长度为14.8173，一般遗传算法的路径长于混合遗传算法，并且从适应度变化折现中看出，一般遗传很快进入局部最优，一般遗传算法的收敛速度没有混合遗传算法快。

4 结论

本文针对机器人的路径规划，讨论了一种新的混合遗传算法。通过实验对比，混合了A*算法的遗传算法在机器人路径规划方面是有效的。该算法有以下特点：

(1)引入随机节点，通过A*算法保证了种群中染色体的多样性，保证了路径的局部最优。

(2)算法中的交叉和变异方法，催生新的染色个体能力强，方便个性差距大的个体出现。

(3)算法可以调整交叉和变异概率，算法的前期进化能力较强，算法的求解效率有所提高。

图5 一般遗传算法仿真结果

图6 混合遗传算法仿真结果