面向生产车间的单车路径优化算法研究

陈泽宇，冯子骁，宋佳员

（1.河海大学机电学院，江苏 常州213022；2.河海大学物联网学院，江苏 常州213022）

1 引言

自动引导小车（Automated Guided Vehicle，AGV）在20 世纪50 年代被首次提出。作为一种智能搬运设备，由于其自动化程度高、易于控制等优点，广泛应用于仓储、物流行业。在一些加工车间内，使用AGV 来搬运物料，能有效节约劳动成本和提高工作效率，因此对AGV 应用的研究极为重要，其中如何设置AGV 的路径直接影响企业生产效率和成本，需要对其进行深刻研究。

目前求解AGV 最优路径主要采用的是人工智能的算法，比如蚁群算法[1-2]、粒子群算法[3]、神经网络算法[4]、快速扩展随机树寻路算法[5]以及遗传算法[6-7]。这些有群体智能的算法都有正反馈机制和较优的扩展性，在路径规划和旅行商问题（TSP）[8-10]中被成功应用。文献[1]中使用了优化后的蚁群算法，相较于传统算法避免了寻优的盲目性，从而提高了算法效率。文献[3]中使用三角函数变化方式对其参数进行自适应调整，并加入鸡群算法去除扰动，有效避免了算法停滞。文献[4]采用的是基于神经网络算法来规划机器人移动路径，缩短了搜寻时间。而其中遗传算法虽然提出时间较早，但是由于其是多点式搜索，更有可能搜索到全局的最优解，所以如今多数路径规划问题仍可以用遗传算法去求解。但是传统的遗传算法有自身固有缺点，比如容易早熟、收敛效果差的缺点，因此，在使用时必须对其进行改进。本文提出的改进型遗传算法，是在传统遗传算法基础上，对其中交叉和变异过程进行优化，提高算法计算效率，缩短计算时间，获得更好的搜索结果。

2 模型建立

对于研究AGV 的路径规划问题，首先要建立合适的地图模型，常用的方法有可视图法[11-12]、传统栅格法[13]和人工势场法[14-15]。其中栅格法（grid method）具有简单、易于表达和灵活等优点，所以本文采用栅格法建立AGV 地图模型。如图1 所示，黑色区域表示障碍或者机器，白色区域AGV可以行驶，行驶方向为AGV 所在格的周围八个栅格。此外，此栅格可以坐标化便于之后遗传信息的编写和路径长度计算。本文之后的算法都在此栅格地图的基础上进行求解。

图1 地图栅格模型

3 改进型遗传算法

3.1 改进型遗传算法模型

遗传算法是模拟达尔文进化论所创建的，根据生物遗传和进化的特点和步骤，引入了基因复制、交叉突变等遗传信息的处理方式，并且采用了进化论中适者生存的法则，对基因信息进行筛选。

本文提出的改进型遗传算法来求解最优路径，首先会产生第一代中会产生多条路径，记为1iL。其中，下标i表示第一代的第i条路径，上标为代数，路径由构成路径的坐标点构成，从点按顺序排布，每一条路径都能代表一个遗传信息，如式（1）所示。

对于第一代所有路径的集合记为C1，其中C1表示为：

之后计算C1中的长度，记为，表示为：

比较之后选出这一代中路径长度最短的一组遗传信息，将其路径长度作为之后评估的标准。

在获取第一代信息后，对遗传信息进行复制，准备下一步基因交叉和突变。复制时，根据每一条路径的长度和最短路径的比值确定对应遗传信息的比值后设置一个复制阈值P0，如果比值低于这个阈值，则该遗传信息不进行复制，但这个值不能取太大，太大容易快速进入局部最优，损失部分可交换的遗传信息，所以选择合适的阈值有利于提高算法求解速度，且能提高算法的收敛性。

遗传信息复制结束后需要对信息进行重新结合，也就是“交叉重组”。交叉重组旨在扩大搜索范围，产生新品种的后代，为之后迭代复制提供资源，随着复制过程中的筛选体现出优胜劣汰的特点。该操作的过程是将已经复制的遗传信息进行部分互换，找到两组遗传信息中共用的坐标点，对其进行前后段互换，即可得到一个新的遗传信息，扩大遗传算法的搜索。具体先任选一个信息设为，然后算出该信息与其他信息之间的路径的距离如式（4）所示。

i

0

i

按照此概率选择方式完成一对信息配对后，将所有信息都进行同样的操作，之后对每一对信息组中的公共点随机选择作为交叉节点，互换遗传信息，完成一次“交叉重组“操作，得到第二代遗传信息

3.2 改进型遗传算法流程

基于以上算法描述，得到改进型遗传算法的基本流程如下：①获取第一代所有的遗传信息，即初始信息集合；②对信息集合中每一条遗传信息进行计算评估，根据其评估值和阈值的对比，判断信息是否有继续遗传下去的必要，如果没有则去除此信息，如果有则进行下一步；③复制选择后的遗传信息，作为交叉重组的基础；④使每一条遗传信息根据概率公式配对、重组，得到新一代信息集合；⑤判断是否到达最大迭代数，若是则输出最优路径，算法结束，若不是则重复步骤②～④，直到算法结束。

4 仿真分析

在MATLAB 软件中对改进型遗传算法进行了仿真实验，在25×25 的栅格地图的背景下进行计算，总共设置100次迭代，每一代中有50 条遗传信息，计算结果显示改进型遗传算法在算法求解时间和收敛效果上均与传统算法相比有提升。

图2 为通过改进型遗传算法求解出的AGV 最短运动轨迹图。表1 为改进型遗传算法和传统的遗传算法的对比数据，每种算法各在相同情况下运行10 次后求平均值。

图2 AGV 最短路径轨迹

在两种算法所需计算时间方面，由表1 数据可知，改进型遗传算法由于在复制时提前进行筛查排除一些极差遗传信息，减去了大量后期交叉重组所需要的时间，减少了一定的计算量，使得计算时间由平均13.862 9 s 缩短至12.684 7 s，减少了8.49%。

在两种算法所解最短路径长度方面，由于改进型算法在引入了概率计算和去除极端信息时，有助于算法收敛，所以改进型遗传算法的最短路径为38.627 4，而传统遗传的最短路径为39.974 1，且10 次平均下来改进型遗传算法也要优于传统算法，体现出改进后算法的优良性质。

表1 算法性能对比

5 总结

对于传统遗传算法在求解AGV 最短路径规划问题时的一些不足，在传统算法的基础上，我们增加了遗传信息复制阶段的评估筛选和交叉重组阶段的概率配对，以此来缩短算法计算时间和提高算法的收敛性。最后的仿真结果也证明了改进型遗传算法有优于传统遗传算法之处。