基于改进蚁群算法的桥式起重机路径规划问题研究

周 浩，曹旭阳，王殿龙，陈敬涛

（大连理工大学机械工程学院，辽宁 大连 116024）

1 引言

桥式起重机具有占地资源少、负载能力强、操作灵活等优点，广泛应用于车间、仓库、船厂、港口等场所的物料搬运。但现有的桥式起重机的工作效率很大程度上仍要依赖驾驶员的熟练程度，此外如何在高危和有害的作业场所自动化地完成避障搬运任务也是亟需解决的问题[1]。围绕桥式起重机自动化运行，路径规划问题成为了重要研究课题。常用的路径规划算法有人工势场法、A*算法、Dijkstra 算法、遗传算法、蚁群算法等[2]。其中蚁群算法及其改进算法得到了较为广泛的应用。文献[3]修改概率公式中的期望值，对路径中三种不同拐点角度赋值，进而修改信息激素更新规则，改进后算法所寻路径优于基本算法，但在评价函数中没有考虑拐点数量的影响；文献[4]建立α（信息素启发式因子）和β（期望启发式因子）的互锁关系，动态自适应调整α 和β，提出广义信息素更新规则，取得了较好的仿真实验效果，但互锁关系由取值经验与仿真实验获得；文献[5]研究改进遗传算法在桥式起重机中的应用，修改目标函数解的遗传表示，替补栅格集合由原来的8个改为4 个，虽然减少了节点数量，但也降低了环境适应性[3-5]。

所以，针对传统蚁群算法收敛速度慢，容易陷入局部最优等缺点，改进算法的自适应启发函数和信息素更新机制，同时根据桥式起重机的运行特征，提出新的评价标准。最后通过MATLAB仿真研究验证改进算法的可行性和有效性。

2 栅格地图构建

采用栅格法来构建桥式起重机二维有限空间运行环境地图，如图1 所示。设置栅格空间的左下角为坐标原点，以原点水平方向为x轴，以原点垂直方向为y轴，然后以起重机单位运动步长L为指标来划分x轴和y轴上的栅格区域，每一个栅格方块都能够以唯一直角坐标xy的方式表示出来。然后由栅格阵列左上角的首个栅格起，按照从左至右，从上至下给每个栅格编定序号图中白色栅格为自由栅格，黑色栅格为障碍栅格，障碍不满一个栅格则填充满此栅格[6-7]。图中坐标与序号编码对应关系，如式（1）所示。

式中：Nx—每一行的栅格总数；mod—求余操作；int—取整操作。

图1 栅格法环境模型Fig.1 The Environment Model Created by Grid Method

3 传统蚁群算法

蚁群算法是一种具有分布计算、信息正反馈和启发式搜索特征的新型启发式智能优化算法，其数学模型可表示为：在觅食过程中，各蚂蚁间通过遗留在路径上信息素浓度强弱和节点状态转移概率大小来实现最短路径搜索功能[8]。将蚂蚁放在设置的栅格地图起始点后，根据状态转移概率公式计算其访问下个栅格的概率。计算公式：

式中：allowed—除了禁忌表以外蚂蚁可以选择的栅格；ηij—启发函数，决定蚂蚁选择哪条路径，表达式为ηij=1/dij。其中，dij为i栅格与j栅格的距离；α 是信息启发式因子，表示蚂蚁在运动过程中所积累的信息素在路径选择时所起的作用；β 是期望启发式因子，表示启发信息对于蚂蚁路径选择的重要程度。为了使选择具有随机性，不陷入局部最优，采用轮盘赌算法来选择下一个栅格。

计算各蚂蚁经过的路径长度，当执行路径搜索任务的所有蚂蚁在完成一次循环搜索后，记录当前迭代下的最优解，同时对路径上的信息素浓度进行更新，信息素更新公式：

上的信息素增量。

4 蚁群算法的改进

4.1 自适应启发函数改进

传统蚁群算法中启发函数为相邻两个栅格之间距离的倒数，数值差异小，启发性弱，降低了算法的搜索效率。A*算法将当前栅格，可选栅格以及目标栅格的位置关系建立自适应构造估价函数，通过估价函数来选择下一步栅格[9]。

式中：g（n）—起始栅格到可选栅格n的代价；h（n）—可选栅格n到目标栅格的代价。

结合A*算法估价函数的基本思想，构建蚁群算法的自适应启发函数，自适应的启发函数中加入了当前栅格和目标点之间的距离，这样可以更快的找到最短路径，减小迭代次数。

式中：dij—当前栅格i与栅格j的距离；djE—栅格j与目标点E的距离。

4.2 信息素更新机制改进

传统蚁群算法在蚂蚁完成一次迭代后，对所有到达目标点蚂蚁走过的路径都进行信息素的更新。这种方式导致整个寻优过程效率降低，后续蚂蚁不能够迅速地找到信息素浓度高的较优路径。狼群算法是基于狼群群体智能，模拟狼群捕食行为及其猎物分配方式，抽象出“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制的一种群体智能算法[10]。为了提高蚁群算法的收敛速度和避免陷入局部最优，借鉴狼群算法中“强者生存”的狼群更新机制对路径上的信息素进行更新。换言之，每次迭代结束之后，增加局部最优路径上的信息素量，减少局部最差路径上的信息素量。其更新规则由公式给出。

式中：δ—局部最优路径的蚂蚁数量；ω—局部最差路径的蚂蚁数量；L1—局部最优路径的路径长度；L2—局部最差路径的路径长度。

为验证改进后算法的有效性，应用MATLAB 对传统蚁群算法和改进蚁群算法进行仿真，仿真实验参数设置如下：m=50，α=1，β=7，ρ=0.5，Q=1，得到在两种环境下的算法仿真结果，如图2、图3 所示。为减小误差，进行20 次独立重复实验，得到实验数据统计结果，如表1 所示。从仿真结果可以看出，在不同的栅格地图下，改进蚁群算法的路径长度最大值和平均值都要优于传统蚁群算法，同时有效降低了算法的迭代次数，提高收敛速度，此外算法运行时间也得到一定优化。

图2 环境1 算法仿真结果Fig.2 The Results of Algorithm Simulation in the First Environment Model

图3 环境2 算法仿真结果Fig.3 The Results of Algorithm Simulation in the Second Environment Model

表1 路径规划统计结果Tab.1 The Results of Path Planning

4.3 结果评价标准改进

不同于在栅格地图仿真环境下研究路径规划算法，在考虑车间环境以及桥式起重机机械电气特性后，路径最短的一个评价标准在实际的工程应用中并不一定能得到最优路径。最优路径不仅需要考虑路径的长短，还受到运行时间以及稳定性的影响，所以提出以路径长度、运行时间和稳定性为代价的改进评价标准，最优路径即为代价最小的路径。

在桥式起重机搬运物料的过程中多为匀速运动，所以除路径长度外大小车的启停是运行时间的主要影响因素。桥式起重机启停多采用梯形加减速[11]，加减速过程必然会有速度的丢失，从而造成运行时间的增加。显然，在仿真环境下没有办法实现控制桥式起重机的加减速过程，但可以抽象出节点数量来控制启停次数，通过减少节点数量来降低运行时间。

桥式起重机柔性钢丝绳的连接方式以及外力作用会引起吊重的摆动，从而很难实现精确定位，降低了工作效率，同时这种周期性的摆振也易引起钢结构的疲劳，影响了起重机的稳定性运行。为了研究路径对运行稳定性的影响，将复杂的三维桥式起重机模型简化，如图4 所示。

图4 三维桥式起重机简化模型Fig.4 The Sketch of a Three Dimensional Overhead Crane

式中：x、y—大、小车的位移；α、β—吊重在X、Y方向的摆角；ux、uy—大、小车的控制输入；fx、fy—X、Y方向的摩擦力；l—吊重绳长；mp—吊重质量，小车质量为mt。应用拉格朗日方程和虚位移原理来建立系统的动力学模型。在线性简化后上得到二自由度摆角的数学模型[11]。

在第二节改进算法的基础上，改进结果评价标准，为验证改进评价标准的有效性，在环境1 下对该算法进行仿真，从仿真结果可以看出，改进后的评价标准在牺牲一定路径长度的基础上减少了节点的数量，获得更优的工程应用路径。

表2 路径规划统计结果Tab.2 The Results of Path Planning

5 结论

针对蚁群算法收敛速度慢，容易陷入局部最优的缺点，借鉴A*算法估价函数的基本思想和狼群分配原则中“强者生存”的狼群更新机制改进自适应启发函数以及信息素更新机制。根据桥式起重机的运行特征，研究容易被忽略的路径工程应用问题，通过对桥式起重机大小车启停和吊物摇摆的运动动力学分析，抽象出两个仿真因子：路径长度和节点数量，提出以路径长度、运行时间和稳定性等性能参数为代价的新的评价标准。栅格环境下的桥式起重机路径规划仿真结果表明，改进的蚁群算法提高算法的收敛速度，避免搜索陷入局部最优，通过改进的评价标准可以得到较优的工程应用路径。