基于改进蚁群算法的焊接机器人路径优化*

孙振博,王明伟,李 姝,张文超

(大连工业大学机械工程与自动化学院,大连 116034)

0 引言

一辆普通汽车的白车身焊点约有4000～5000个,其中一半以上的焊点是由焊接机器人完成焊接任务的,而传统的机器人焊接路径通常是依靠人工经验获得,这就导致焊接路径长、焊接质量可靠性低等问题,因此对于焊接机器人路径自动规划算法的研究,是汽车智能制造技术重点研究方向[1-2]。针对焊接机器人路径规划问题,许多学者在智能优化算法方面进行了大量研究。蚁群算法(ant colony optimization,ACO)是一种基于蚂蚁在寻找食物时的行为策略的优化算法,在解决路径搜索问题中具有较好的性能,但对于解决复杂路径问题时,存在着容易陷入局部最优解等问题。

为解决蚁群算法存在的问题,圣文顺等[3]通过将蚁群算法与遗传算法融合的方式扩大了蚁群算法的解空间,同时引入贪心策略改进蚁群算法收敛速度。吕文壮等[4]提出利用粒子群算法对蚁群算法随机产生的解进行交叉与变异,扩大了蚁群算法的搜索空间,改善了算法的收敛准确度。秦东各等[5]提出一种改进的蚁群算法,通过2-opt算子对于蚁群算法中部分蚂蚁路径进行优化,提高收敛速度,并针对蚁群算法信息素挥发因子参数特性提出了一种动态调整信息素挥发因子策略,以避免算法过早收敛。

本文为提高了焊接机器人路径规划的效率和精度,针对ACO算法易陷入局部最优且收敛速度慢等问题提出一种改进的蚁群算法(DWAG),通过动态权重策略与排序因子策略改进了蚁群算法的信息素更新方式以改善算法的收敛性能,同时结合遗传算法中交叉与变异操作以提高算法搜索的广度与深度。本文将DWAG算法应用于实际焊接机器人的路径规划中。白车身后地板总成焊接路径规划实例表明,DWAG算法相比于ACO算法,缩短了焊接路径距离,提升了焊接效率且求解稳定性更佳。

1 焊接机器人的路径规划问题描述

焊接路径规划可以简单描述为:假设某工位有n个焊点需要焊接,装有焊枪的点焊机器人从起始点出发,遍历所有焊点且每个焊点只遍历一次后回归起始点[6-7]。本文以白车身后地板总成点焊工位上的某一台点焊机器人为研究对象,工位焊点分布如图1所示。

设n个焊点的集合为C={c1,c2,…,cn},将第m条焊接序列设为cm=(cm1,cm2,…,cmn),其中cm(i)∈C(1≤i,j≤n),焊点之间的距离为d(cmi,cmj)≥0。焊接路径总距离可表达为:

(1)

在焊接机器人的路径规划中,焊接路径最短距离是重要的评价标准之一,为了提高工作效率,在路径规划的过程中需保证Lm尽可能小[8]。

2 基本的蚁群算法

(2)

tabuk(k=1,2,…,m)称为禁忌表,蚂蚁数量设为m,用以记录蚂蚁k当前已经走过的城市。ηij是某种启发信息,其具体数值为焊点i与焊点j之间距离的倒数,即ηij=1/dij,dij(i,j=1,2,…,n)表示焊点之间的距离,焊点数量为n,τij(t)表示t时刻对应于焊点i、j之间的信息量,其中,α、β体现信息素和启发信息素对蚂蚁决策的影响程度。当前蚂蚁遍历所有焊点完成一次循环后,对每条路径上对应的信息量进行更新:

τij(t+1)=(1-ρ)τij(t)+Δτij

(3)

式中:ρ∈(0,1)表示信息素的衰减程度,信息素增量Δτij表示蚂蚁k在本次循环中在焊点i和焊点j之间所有留下的信息量:

(4)

(5)

式中:Q为常数,Lk表示第k只蚂蚁在本次迭代中所走过路径的长度。

3 改进的蚁群算法以及性能测试

蚁群算法具有全局搜索能力强、能够处理复杂问题等优点,但也存在缺点。为了改进蚁群算法的缺点,本文将遗传算法中的交叉和变异操作引入蚁群算法,并结合动态权重与排列因子策略进行优化。

3.1 引入交叉和变异操作

引入交叉和变异操作可以增加蚁群算法的全局搜索能力[9]。从而增加算法在搜索空间中的探索能力,避免算法陷入局部最优解。

本文选择的交叉算子为Ox(order crossover),Ox交叉算子在遗传算法中,是一种常用的交叉操作方法之一,用于将两个父代个体的染色体进行重组生成新的子代个体。

具体来说,Ox交叉操作首先从两个父代个体中随机选择两个交叉点,r1与r2,这两个交叉点满足r1

Aparent=[1 2 3 4 5 6 7 8]
Bparent=[3 5 8 1 7 4 2 6]

在经过Ox交叉算子后,子代child1和子代child2可表示为:

child1=[8 2 3 4 5 1 7 6]
child2=[2 5 8 1 7 3 2 6]

对于变异操作,本文采用交换变异与逆转变异。当遗传算法在解决优化问题时,交换变异(swap mutation)是一种常用的变异操作,是指随机互换染色体中的两个基因位。对于逆转变异,常用于改变染色体中的局部排列顺序,以便算法更好的探索搜索空间。在逆转变异中,通常会随机选择两个边界点,确定一个基因片段,之后翻转该基因片段。例如父代染色体A通过交换变异得到子代染色体a。

A=[1 2 3 4 5 6 7 8]
a=[1 2 5 4 3 6 7 8]

父代染色体B通过逆转变异得到子代染色体b,这里两种变异算子随机选择两个基因点位均为r1=3,r2=5。

B=[1 5 8 7 4 6 3 2]
b=[1 5 4 7 8 6 3 2]

3.2 引入动态权重与排序因子策略

本文通过引入动态权重和排序因子策略以提高算法的性能和鲁棒性。如下为基于动态权重与排序因子的信息素更新策略:

τij(t+1)=(1-θ)τij(t)+Δτij·θ

(6)

式中:θ(0.1≤θ≤0.7)为动态权重因子,此处可代表信息素影响权重,θ计算方式为:

(7)

式中:λ(0≤λ≤1)为下降速率因子,控制动态权重因子的变化幅度;t为当前迭代次数,tmax为总的迭代次数。具体来讲,采用指数函数计算动态权重因子,根据当前迭代次数和总迭代次数的比例自适应地调整θ[10]。当λ取0.5,动态权重因子θ变化曲线如图2所示。

图2 动态权重因子θ变化曲线

Δτij表示该次迭代中边ij上信息素的增量,即:

(8)

(9)

式中:Lbest为当前迭代最优路径长度,Lk为第k只蚂蚁在本次迭代中所走过路径的距离,mη为参与信息素更新计算的优秀蚂蚁群体,在每次迭代中,根据路径的长度对于蚂蚁群体进行排名(距离短的靠前),只有在蚂蚁群体中排名靠前的部分蚂蚁即优秀蚂蚁群体才允许在路径上释放信息素。mη可表示为:

mη= [m*η]

(10)

式中:m为蚂蚁总数,η(0.2≤η≤0.7)为百分比调整因子。可表示为:

η=θ

(11)

总的来讲,动态权重策略的优点在于在算法的求解过程中对于优秀蚂蚁群体所占蚂蚁总群体的数量比例以及信息素的蒸发程度随着算法在求解过程中的需要进行了自适应调整,这就保证算法在求解过程中解空间的相对完整性,同时也提高了算法的收敛速度;排序因子策略是对于动态权重策略获得的蚂蚁群体进行进一步的择优,根据排名因子策略,对所选择的优秀蚂蚁群体中的蚂蚁的影响权重进行线性递减的方式调整,使路径长度较短的蚂蚁在信息素更新时具有更大的贡献。这样,路径长度较短的蚂蚁可以更快地传播信息素,加速了优秀蚂蚁所留下的信息素在搜索空间中的传播速度,从而加速全局最优解的收敛速度,减少了陷入局部最优解的可能性。

综上所述,动态权重和排序因子策略可以提高算法的性能和鲁棒性,增强算法在全局和局部搜索空间的探索能力,减少陷入局部最优解的风险,提高算法的适应性和效率,这样的改进有望在实际应用中帮助蚁群算法更好地克服其缺点,提高算法的性能和效果。

3.3 算法流程及性能测试

判断陷入局部最优的条件为:迭代次数若大于1且全局最优路径长度与个体最优路径长度的差的绝对值小于0.01时即算法在求解问题过程中发生停滞。具体的交叉、变异操作:对全局最优与个体最优进行交叉、变异操作。取优操作:从参与交叉、变异操作的所有个体中取一个路径长度最短个体替代为新的个体最优与全局最优。根据式(10),取优秀蚂蚁群体进行信息素更新计算。图3为DWAG算法流程图。

图3 DWAG算法流程图

本文采用TSPLIB数据集中的st70、rat99和ch130数据集,对比了ACO算法和DWAG算法的性能。表1列出了两种算法在测试数据集上的最大值、最小值和方差。最小值是用来评估算法求解最优解的能力。方差则表示算法在求解问题时稳定性,当方差越小时,算法的在求解问题时的稳定性越佳。

表1 测试数据集结果比较

从表1的数据可以看出,DWAG算法相比于ACO算法,在求解最优解的能力和在求解问题过程中的稳定性方面都表现优异,优化效果显著。图4为两种算法求解3种案例的收敛结果比较。

(a) st70 (b) rat99

从图4可以明显看出,相比于DWAG算法,ACO算法收敛速度差,寻优效果能力不足,易陷入局部最优,而DWAG算法很好的弥补了ACO算法的缺点,且随着案例规模复杂度的提升,两者在求解不同问题的性能差距进一步增大。综合来看,DWAG算法相比于ACO算法具有更好的优化效果和稳定性,是一种更为优秀的算法。

4 改进算法实例应用测试

本文以后地板总成某一点焊机器人工位为研究对象,在MATLAB中,分别对ACO算法与DWAG算法规划的焊接路径进行仿真。为保证结果的相对准确性,本文对两种算法分别运行20次。表2记录了两种算法对应用实例仿真结果的最小值、最大值以及方差,可以较为客观地评价各算法的寻优性能。

表2 仿真结果比较

图5为DWAG算法的路径优化效果,最小路径长度为2 976.782 8 mm,方差为各算法运行20次后统计的最优解方差。

图5 改进蚁群算法规划结果

从仿真结果可以看出,DWAG算法方差最小,由此可得DWAG算法优化结果相比于ACO算法更为稳定。

图6为两种算法的优化结果比较,可以较为明显的看出两种算法在焊接路径规划问题上的收敛性能以及优化结果的接近度。

根据仿真结果显示,在汽车后地板点焊路径规划中,DWAG算法表现出明显优于ACO算法的收敛速度和优化效果。方差分析也表明,DWAG算法得到的结果更加稳定。这表明相对于ACO算法,DWAG算法具有更强的优化能力。因此,DWAG算法可以有效地克服ACO算法易陷入局部最优和收敛速度慢等缺点,为焊接路径规划提供前期的焊接顺序建议,并为后续具体实现提供参考。

5 结论

针对焊接机器人路径规划问题,提出了一种改进的蚁群算法并进行实例应用,得到以下结论:

(1)引入动态权重策略以及排序因子策略加快了ACO算法的收敛速度,引入遗传算法的交叉和变异操作避免ACO算法在求解问题过程中陷入局部最优解。

(2)从最短焊接路径距离、寻优稳定性、收敛速度综合对比了DWAG算法与ACO算法,验证了DWAG算法在焊接机器人路径规划方面性能更佳。