汽车门板焊接路径的多种群自适应融合蚁群优化

李 斌，李康满，梅阳寒

（1.东莞职业技术学院，广东东莞 523808；2.衡阳师范学院，湖南衡阳 421002）

1 引言

汽车车身由白车身、内外饰件、电气附件等组成，其中白车身由形状各异的薄板冲压件构成，其中的焊点数量多达4000～6000个，如何安排焊点的焊接顺序、规划焊接路径对焊接效率和生产节拍影响较大[1]，因此研究白车身焊点的路径规划问题具有重要意义。

焊接路径规划是指根据设置的焊点位置，规划出一条遍历所有焊点的焊接路径，在满足焊接机器人运动约束的前提下，实现设定目标的最优化，设置的优化目标包括焊接路径最短、路径最平稳等[2]。

对于焊接路径规划算法的研究，可以分为非进化类规划算法和进化类规划算法两大类。其中非进化类规划算法是指不具备进化能力的算法，包括模拟退火法、人工势场法、A*算法、动态规划法、分支界定法等。文献[3]使用模拟退火算法对无人机山地作业路径进行了规划，实现了无人机的能耗降低，但是由于模拟退火算法是随机近似算法，最终解未必是最优解。文献[4]在人工势场法中引入了逃离策略、穿越策略和距离调节因子，解决了局部极值和目标不可达问题，实现了动态环境下的避障。进化类规划算法是指算法模拟生物群体的智能性，使算法具有较强的进化能力，包括蚁群算法、粒子群算法和遗传算法等。文献[5]将粒子群算法和细菌觅食算法进行混合，规划了无人机在三维空间的轨迹，减小了路径长度和碰撞风险。文献[6]对蚁群算法进行改进，采用无限步长扩展蚂蚁视野，并引入了新的信息素更新规则，改进蚁群算法明显提高了算法在栅格环境中的路径搜索效率。进化算法在路径规划中的应用是当前的研究热点，路径规划的优劣主要取决于算法的寻优性能或优化能力，因此进化算法在路径规划中的研究本质上是提高算法优化能力的研究。

这里以汽车前后车门内饰焊接路径优化为研究课题，建立了车门焊接路径的优化模型，提出了多种群信息素自适应融合蚁群算法，该算法有效平衡了路径多样性和算法收敛性。将多种群信息素自适应融合蚁群算法应用于车门焊接路径规划，达到了减少焊接路径长度的目的。

2 焊接路径规划建模

2.1 焊点信息与问题描述

这里以某型车前后门的内饰门板焊接过程为研究对象，汽车的内外饰件为塑料制品，因此本文研究的焊接过程为非金属品的焊接过程。前后门板内饰的焊点，如图1、图2所示。其中前门板共51个焊点，后门板共62个焊点。

图1 门板的焊点分布Fig.1 Solder Joint Distribution of Car Door

车门内饰焊接路径规划描述为：对于图1给出的前后车门板焊点，规划出一条焊接路径，在满足焊接机器人运动约束前提下，实现焊接路径最短，达到提高焊接工作效率的目的。

2.2 超声波焊接技术简介

这里对汽车门板上的焊点进行电焊，根据焊接能量来源的不同，点焊包括超声波焊接、激光焊接、气体焰焊接等，其中超声波焊接具有节能、高效、强度高、耗时少等诸多优点，因此本文使用超声波焊接方式。

超声波焊接系统的组成，如图2所示。主要包括电源、超声波振荡器、换能器、底砧等，其工作原理为：超声波振荡器将50Hz的市电转化为20kHz的高频电流，换能器将高频电流转化为高频振动，并通过焊接头传递给焊接物，焊接物因高频摩擦而产生巨大热量使接触面熔化，而后停止振动并对焊点施压，冷却后得到融合的焊点。

图2 超声波焊接原理图Fig.2 Principal Diagram of Ultrasonic Welding

2.3 焊接路径优化建模

将内饰门板的焊接问题等效为旅行商问题（Travel Salesman Problem，TSP）。在内饰门板焊接中，焊点为离散分布的，类似于TSP问题中的城市；在内饰门板焊接中，焊接头需将所有焊点遍历一次，类似于旅行商遍历所有城市。因此，可以将内饰门板焊接的路径规划问题完全等效为旅行商问题。

将完全无向赋权图记为G=(V，E，D)［7］，V=(v1，v2，…vN)—焊点集合，vi(i=1，2，…，N)—第i个焊点，N—焊点总数；E={eij}为边集，eij—焊点i与焊点j之间的路径；D={dij}—任意两个焊点之间的距离矩阵，dij—焊点i与焊点j之间的距离。

将路径标识参数记为xij，当焊接路径中包含路径eij时xij=1，当焊接路径中不包含路径eij时xij=0。焊接路径规划以路径最短为优化目标，要求每个焊接点均遍历且只遍历一次。则焊接路径的优化模型为：

式中：Z—焊接路径长度，约束条件1和约束条件2保证所有焊接均经过且只经过一次。

3 多种群自适应融合蚁群算法

信息素是蚁群之间进行信息交流的媒介，通过不同蚁群之间信息素的融合与交互，可以实现不同蚁群之间的信息交流。这里基于蚁群的路径多样性、蚁群间路径的差异性，构造了多种群信息素自适应融合的蚁群算法。

3.1 子群构成

这里所谓的多种群蚁群由基本蚁群、蚁群系统、最大最小蚂蚁系统组成。在此对基本蚁群与蚁群系统的区别进行明确，最大最小蚂蚁系统的工作原理可参考文献[8]，这里不再介绍。

基本蚁群算法使用局部信息素更新策略，即蚂蚁每选择一个城市则进行信息素更新，包括信息素的挥发和残留，为：

式中：ξ—信息素挥发系数—蚂蚁k残留的信息素浓度。

蚁群系统与基本蚁群算法的区别主要体现在两个方面：

（1）在基本蚁群算法中，基于概率(t)使用轮盘赌策略确定最终选择的城市；而在蚁群系统中使用伪随机策略选择下一城市。

（2）基本蚁群算法中使用局部信息素更新策略，而蚁群系统同时使用局部信息素更新策略和全局信息素更新策略。蚁群系统的伪随机策略描述为[10]：

式中：j—蚂蚁选择的下一城市；q0—一概率阈值，q∈[0,1]—随机变量；J—使用式（3）轮盘赌策略选择的城市。

蚁群系统使用的全局信息素更新策略为：算法每迭代一次，则在最优路径上实施信息素正反馈更新，即：

3.2 基于信息熵的路径多样性度量方法

蚁群算法的信息素分布可以反应算法的搜索状态，当信息素分布相对集中时说明算法已经相对收敛，路径多样性较差；信息素分布较为均匀时说明算法处于大范围搜索状态，路径多样性较好。这里使用信息素分布浓度的信息熵衡量信息素分布的无序性，从而对算法搜索状态的路径多样性进行度量，为：

式中：Ls(p(t))—迭代t次时信息素分布的信息熵，也即路径多样新度量参数；p(t)—迭代t次时信息素浓度比例矩阵；pij(t)—城市ij间信息素与总信息素的比值，即：

式中：τij(t)—城市ij间的信息素浓度。

3.3 基于相对熵的蚁群差异性度量方法

相对熵可以衡量两个分布之间的差异性，因此这里借助相对熵对不同子群的信息素分布相似程度进行衡量，为：

式中：Gs(pk，ph)—子群k和子群h之间的差异性度量值；pk—子群k的信息素浓度比例矩阵；ph—子群h的信息素浓度比例矩阵—子群k的城市ij间信息素与总信息素的比值—子群h的城市ij间信息素与总信息素的比值。

使用Gs(pk，ph)度量不同蚁群之间的差异性，当Gs(pk，ph)较小时说明两个子群之间的差异性较小，也即两个子群之间的信息素分布极为相似，两个子群进行交互作用的效果极为有限。

当Gs(pk，ph)较大时说明两个子群之间的差异性较大，也即两个子群之间的信息素分布差别较大，两个子群进行交互作用的效果较好。

根据以上分析，与子群k进行交互的子群g选择方法为：

式中：C—所有子群的集合。

3.4 多种群信息素自适应融合

多种群信息素融合的目的是将多个子群算法的优势进行结合，实现算法多样性和收敛性的平衡。

基于前文给出的路径多样性度量方法和蚁群差异性度量方法，这里提出了一种多种群信息素的自适应融合方法，为：

式中：λ—融合率—子群k的信息素分布信息熵—信息素分布信息熵的阈值；子群g—与子群k的交互蚁群。

式（10）可解释为：当小于阈值时，说明子群k的信息素分布过于集中，路径多样性较差，此时根据子群间差异，选择与子群k差异最大的子群g与其交互，从而增加子群k的路径多样性；

当大于阈值时，说明子群k的信息素分布较为分散，路径多样性较好，此时不进行信息素的融合与交互，各子群按照各自的工作原理进行路径规划。

由以上分析可知，式（10）是一种根据子群路径多样性自适应进行信息素融合的过程，同时参加融合的子群也是根据差异性自适应选择，因此该方法命名为多种群信息素自适应融合。

3.5 算法流程

根据多种群信息素自适应融合蚁群算法的构造原理，制定算法流程如下。

（1）将所有蚂蚁放置于起点位置，基本蚁群算法、蚁群系统、最大最小蚂蚁系统三种蚁群算法按照各自的工作原理进行迭代；

（2）每完成一次迭代，计算各子群信息素分布的信息熵，对各子群的路径多样性进行度量；

（3）若所有子群的路径多样性均较好，则继续迭代并判断各子群路径多样性；

（4）若某子群的路径多样性较差，按照式（9）选择与该子群差异性最大的蚁群，两者进行信息素融合；

（5）重复执行（2）～（4），直至算法达到最大迭代次数，输出最优路径，算法停止。

4 实验验证与分析

本节首先对多种群信息素自适应融合蚁群算法的性能进行验证，而后使用该算法求解汽车门板焊接的路径规划问题。

4.1 算法性能测试

为了对多种群信息素自适应融合蚁群算法的性能进行测试，从常用测试集TSPLIB 中随机选择3 个样本进行测试，分别为ei151、kroA200和lin318，其中ei151为小规模测试集，kroA200为中等规模测试集，lin318为大规模测试集。

各子群的参数设置按照性能最优原则设置，基本蚁群算法参数设置为：α=2、β=3、ρ=0.3；蚁群系统参数设置为：α=1、β=3、ρ=0.3；最大最小蚂蚁系统参数设置为：α=1、β=2、ρ=0.4。为了保证算法进行充分的搜索，在性能测试中算法最大迭代次数设置为2000。为了对比算法的搜索性能，使用基本蚁群（Basic Ant Colony，BAC）、蚁群系统（Ant Colony System，ACS）、最大最小蚂蚁系统（Max−Min Ant Colony System，MMAS）和多种群自适应蚁群算法（Multi−Population Adaptive Ant Colony，MAAC）分别对3 种测试样本进行规划，每种算法独立进行实验10次，统计所得路径长度的最优值、平均值、标准差和迭代次数，结果，如表1所示。

表1 路径规划结果Tab.1 Path Planning Result

由表1可以看出，在ei151、kroA200和lin318等3个测试样本中，多种群信息素自适应融合蚁群算法规划路径的最优值、平均值、标准差和迭代次数均小于其余3种蚁群算法，说明多种群自适应蚁群算法规划的路径质量和算法平稳性均好于3种子种群算法，且算法收敛的规划次数较少。这是因为多种群信息素自适应融合算法中给出了算法的多样性度量方案和子群差异性度量方法，依据子群差异性自适应确定信息素融合对象，依据算法路径多样性确定信息素融合时机，因此多种群信息素自适应融合蚁群算法的规划性能优于3种子种群算法。基于多种群信息素自适应融合蚁群算法对3个测试样本的规划结果，如图3所示。

图3 3种测试样本的规划结果Fig.3 Planning Result of the 3 Testing Sample

4.2 汽车门板焊点路径规划

本节使用多种群信息素自适应融合蚁群算法对2.1节描述的汽车门板焊接路径规划问题进行求解，同时与文献[11]的自适应蚁群算法（Adaptive Ant Colony Algorithm，AAC）规划结果进行对比。2.1节图1中的焊点3维信息数据较大，这里不再给出。

焊接过程为：焊接机器人从初始位置Home点出发，遍历所有焊点后回到Home点，完成焊接过程。对于汽车的前后门板焊接路径，使用这里的多种群信息素自适应融合蚁群算法和文献[11]的自适应蚁群算法各自独立运行10次，统计10次规划结果的最优值、最差值、平均值和规划耗时，结果，如表2、表3所示。

表2 前门板的规划结果Tab.2 Planning Result of the Front Door

表3 后门板的规划结果Tab.3 Planning Result of the Back Door

基于多种群信息素自适应融合算法规划的前后门板焊接路径，如图4所示。

图4 前后门焊接路径规划结果Fig.4 Welding Path Planning Result of Front and Back Door

结合表2、表3和图4可知，在汽车前门和后门的焊接路径规划中，这里提出所的多种群信息素自适应融合蚁群算法规划的焊接路径最优值、平均值均小于文献[11]的自适应蚁群算法，且规划耗时也略短于自适应蚁群算法，这说明多种群信息素自适应融合蚁群算法的优化能力和优化效率好于文献[11]的自适应蚁群算法。这是因为文献[11]只是在蚁群算法基础上对参数初值确定方法进行了改进，同时依据迭代次数调整信息素浓度，是较为浅显的改进方法。这里所提算法给出了路径多样性度量方法、子群差异性度量方法，基于路径多样性自适应确定子群交流的时机，基于子群差异性自适应确定子群的交流对象，这是一种更深层次的从工作原理上的优化，因此这里所提算法的优化能力更好、优化效率更高。

5 结论

这里研究了汽车们班的焊接路径优化问题，建立了门板焊接路径的优化模型，提出了多种群信息素自适应融合算法，经验证，得出以下结论：（1）多种群信息素自适应融合蚁群算法能够有效平衡算法的多样性和收敛性，其优化能力好于基本蚁群、蚁群系统、最大最小蚁群系统等算法；（2）将多种群信息素自适应融合蚁群算法应用于车门焊接路径规划，得到了较优的焊接路径。