一种改进的遗传算法求解机器人最优路径

梁亚楠 尹亚明

(成都理工大学 四川 成都 610059)

一种改进的遗传算法求解机器人最优路径

梁亚楠 尹亚明

(成都理工大学 四川 成都 610059)

遗传算法具有全局搜索性强、鲁棒性高、且具有较好的收敛性的有点。随着人们逐渐对其深入的认识，人们发现这种算法容易陷入早熟的状态。对此，本文改进了初始化种群的过程，并对选择，交叉，变异三种算子进行优化。

遗传算法；自适应遗传算法；机器人路径优化

一、引言

近几年关于机器人路径规划的研究是一个热点。高申勇等[1]基于虚拟弹簧模型，建立弹簧力学模型，寻找机器人移动的最优路劲；李晋[2]将遗传算法与蚁群算法相结合，提出了解决机器人路劲规划的方法；王冬云等[3]采用改进的具有群集智能的蜂群算法，结合三次贝塞尔曲线来描述路径，以达到路径最优的目的。

二、机器人环境描述及编码

(一)工作空间描述

本文采用栅栏法表示机器人的运动空间[4]，如图1所示。基于以下几点：1.机器在一个二维平面内活动。2.对每个空格进行编号，每个空格的编号可由以下式子计算；H=10y+x。3.图中阴影部分表示障碍物，空白表示自由栅栏，工作空间内障碍物的数量和位置都是已知的。

图1 机器人工作空间

(二)初始种群的产生及路径的编码

采用机器人移动经过栅栏的编号的有序组合来进行编码，如图1所示，0为机器人初始位置，99代表机器人移动的终点。所经过的方格的编号的组合，就代表一个个体的编码。如:0,11,21,30,41,42,43,54,64,74,85,86,87,97,98,99。由于初始群体产生具有随机性，这就会同时产生有效路径和无效路径。有效路径是指机器人所走过的路线不经过障碍点，无效路径是指机器人所走过的路线会经过障碍点。

本文采用随机生成的方法随机来生成初始种群。对于无效路径，采用变异调整的方法进行处理：对任意一条无效路径，找出这条路径所经过的所有的障碍物点，在障碍物点之前的第一个非障碍物点采用调整策略，即按照其他非障碍方向进行调整，产生多条新的路径，若产生的是无效路径，则舍去该路径。比较剩余的有效路径的适应度大小，将适应度大的保留，其余的舍去，用这条新路径替换原来调整之前的无效路径。

如，初始生成的路线为A:0,11,21,31,41,42,52,63,73,74,84,85,96,87,97,98,99。由于63号栅栏存在障碍物，则这条路线成为无效路径，机器人经过63号栅栏点之前通过的第一个空白栅栏编号为52，在52号栅栏处对路径进行调整，按照上面提出的方法，共生成三条新的路劲，分别是：

路线B：1:0,11,21,31,41,42,52,62,72,82,83,84,85,96,87,97,98,99

路线C，1:0,11,21,31,41,42,52,53,54,64,65,75,85,96,87,97,98,99

路线D：1:0,11,21,31,41,42,52,43,44,54,64,65,75,85,96,87,97,98,99

由于路线B经过72号栅栏为障碍物栅栏，所以舍去这条路径，路线C和路线D均为有效路径，经过比较计算可知，路径C的长度比路径D短，舍去路径D，用路径C替换路径A。

三、适应度函数的确定

适应度函数是用来评价个体满足环境的适应能力的大小，适应度的大小决定着个体继续生存的概率，适应度函数越大，个体生存能力越优，越能适应恶劣的环境。我们采用机器人路径长短的倒数作为适应度函数：

四、遗传算子

(一)选择算子

传统的遗传算法采用了轮盘赌的方法进行样本的选择，本文结合了精英策略和联赛制。先对初始样本进行相应的处理。算法陷入早熟和局部最优的原因是因为存在某些个体的适应度远远大于其他个体的适应度，我们用标准差δ来评判种群离散程度。

我们利用三倍标准差法筛选初始种群。然后采用精英策略，按照一定的比例保留初始种群中适应度大的，让他们直接参与下一代遗传，剩下的个体，采用联赛制度，设置参数I=2，即从剩下的个体中每次随机挑选出两个个体，比较这两个个体的适应度大小，让适应度大的参与下一代遗传运算，适应度小的个体放回原种群。

(二)交叉算子

交叉运算是产生新个体的重要方式，机器人路径编码不能任意交叉，否则会产生不连续路径。我们采用单点交叉的方式，对选中的两个个体，若存在相同的栅栏节点，则随机选取其中一个节点，在该节点处进行交叉操作，否则，不进行交叉。例如：

路线A：0,10,20,30,40,41,51,52,43,54,64,65,75,76,86,87,97,98,99

路线B：0,11,21,31,41,42,43,34,35,36,46,47,48,49,58,68,78,79,89,99

路线A和路线B存在共同节点41和43，我们随机选取43号节点，则交叉都得到两条新路线：

A’:0,10,20,30,40,41,51,52,43,34,35,36,46,47,48,49,58,68,78,79,89,99

B’:0,11,21,31,41,42,43,54,64,65,75,76,86,87,97,98,99

(三)变异算子

本文采用下面这种变异方式：

1.随机选取个体中某个节点为变异点；

2.考察变异点的上、右上、右、右下、下五个方向，若这五个方向为空白栅栏，不存在障碍物，则分别进行五个方向的变异；

3.若某条路径通过障碍物节点，则删除这条路径；

4.比较剩下的路径的适应度大小，用适应度大的路径替换原来变异前的路劲，其余的路径舍去。

五、结论

这种改进过后的遗传算法，相比于传统的遗传算法，在算法的机制上有了很大的改进，通过这种改进有效的避免了算法陷入局部最优和早熟的现象，同时，大大提高了算法的运行速度。通过实验仿真表明，采用本文所述的改进方法，相比于传统遗传算法，运行速度提高了31%，在遗传的代数上，找到最优解的代数从121代减少到84代，明显加快的算法的收敛速度。

[1]高申勇,许方镇,郭鸿杰.基于弹簧模型的移动机器人路径规划研究[J].仪器仪表学报,2016,37(4):796-803.

[2]李晋.基于蚁群算法和遗传算法的机器人路径规划研究[D].哈尔滨工业大学,2012.

[3]王东云,徐艳平,瞿博阳,等.基于改进蜂群算法的机器人路径规划[J].计算机系统应用,2017,26(2):145-150.

[4]石欣,印爱民,陈曦.基于RSSI的多维标度室内定位算法[J].仪器仪表学报,2014,35(2):261-268.