分区自适应蚁群算法的多面体数控钻床加工路径优化*

游海涛，罗红波，董 特，施显阳

(四川大学机械工程学院，成都 610065)

0 引言

伴随“高效率”、“低成本”的加工概念深入人心以及孔群钻孔加工需求的不断增加，数控钻床作为其主要加工工具，其钻孔加工路径规划已引起国内外学术界以及企业的高度关注。然而，目前钻孔加工路径规划大多凭借操作工人经验，这势必将导致工时和成本增加等诸多问题。钻孔加工时间主要有装刀时间、换刀时间、刀具空程移动的时间和进行切削加工的时间[1]。其中刀具空程移动时间占整个钻孔加工时间的主要部分，因此选择一条最短的空程走刀位移变得至关重要。大量已有研究[2-4]的钻孔加工路径大多基于二维平面规划。可以将多面体孔群加工路径优化看作TSP问题(旅行商问题)，生成最短的空程走刀路径是降低加工成本和提高生产效率的关键技术之一。查阅国内外文献，许多学者对此类问题围绕优化算法进行了大量的研究。Mircea Ancău[5]提出了一种启发式算法对PCB的刀具路径和加工时间进行了优化，但未对钻孔参数优化；凌玲等[6]加入最小加工成本的数学模型并利用改进遗传算法对加工路径优化，但该算法求解问题规模较小不适用于大规模问题；Abbas A T等[7]采用改进蚁群算法对矩形排列孔群进行了优化，为求解大规模TSP问题提供了一定思路；Cuneyt Oysu等[8]利用一种基于遗传算法和模拟退火算法的混合算法优化了钻孔加工过程中的路径距离，该算法综合性能优于原两单一算法；Kumar A等[9]采用遗传算法对钻削加工中的总时间和总距离进行了优化并求解出来最优钻削时间，但该算法收敛速度较低需约3500次迭代才能收敛于最优解；冯志雨等[10]利用DP-ACS(Density Peak clustering algorithm-Ant Colony System)分工合作思想处理了大规模TSP问题，但该研究未能将局部优化路径连接生成全局最优路径;刘勇等[11]利用免疫克隆与蚁群算法结合算法对Oliver30问题做出了求解；张瑜等[12]采用COAMHC(Antibody Clone Optimization Algorithm inspired by MHC)解决了50、75、100个城市路径距离优化问题，该算法通过引入多种算子提高了算法的收敛速度和求解精度。以上研究成果大多是针对满足一定准则下二维路径优化，未能涉及到三维空间钻孔加工路径优化。

1 问题描述

1.1 多面体数控钻床模型

多面体数控钻床是一种具有多自由度的自动化设备。通常，除了采用经典的立式钻床设计外，在此基础上分别增加了一个绕Y、Z轴的旋转轴，实现多面孔群加工转换，克服了多次装夹导致加工孔相互位置精度降低的缺点，其结构示意图如图1所示。该图显示了X-Y-Z机床坐标系和Xw-Yw-Zw工件坐标系，钻头可沿X、Y、Z轴平行移动，通过电机旋转改变B、C轴角度，从而实现一次装夹工件的多面钻孔加工。

图1 多面体数控钻床模型示意图

1.2 钻孔加工路径规划

数控钻床加工路径规划其核心部分是对所有加工孔的孔序规划。钻孔加工过程中还需要考虑钻头与夹具或工件自身几何干涉等诸多问题。如果不考虑钻孔过程中的一些约束条件，例如钻头偏斜、孔径扩大、表面质量较低等因素，那么钻孔路径规划问题可以表示为：遍历所有加工孔，找出满足钻孔加工规划准则最优的钻点序列。通常在加工路径规划问题中常用的准则是空程走刀路径最短、加工过程时间最短、机床能耗最低等。本文使用的准则是路径最短[13]。所以，此优化问题可以描述为：

(1)

式中，X代表钻孔孔序，S(X)代表空程走刀的路径距离。

根据此准则得到其目标函数表达式：

S=∑d(Pi,Pi+1)+d(PN,P1)

(2)

由上式可知空程走刀距离S由两部分构成，其中d(Pi,Pi+1)为当前钻孔点Pi到下一点Pi+1的距离，式中i=1,2,3,…,N-1。d(PN,P1)为终点到起点的距离。然而，在实际钻孔加工过程中必须考虑钻头与工件之间的几何干涉问题，即工件内部与钻头的避障处理。

1.3 钻孔避障方法

图2 工件图

选用某数控车床夹具如图2所示，该图显示了夹具各螺纹孔的分布及几何特征。同时在Matlab上绘制了钻孔点集的分布，如图3所示。因为工件相对于主轴箱较小，所以本文只考虑钻头与工件内部的避障问题。

图3 钻孔点集分布图

图4为当前点和下一点在相邻平面内的避障示意图，为了找到一条避障且最短的空程走刀路径本文引入过渡点这一概念，如图5所示。

图4 相邻面避障示意图

1.4 避障过渡点求解

图5显示面1面2为两相邻平面，设点A为钻孔起始点，点C为钻孔终点，AC连线区域为障碍区域(不可加工),做A与C连线和相邻面交线2的公垂线，该公垂线与直线2交于过渡点B，因为AC连线长度为定值且当线1为公垂线时两异面直线最短，所以由勾股定理可知A到B，B到C为最短无碰撞空程走刀路径。

图5 过渡点求解几何关系图

为了找到过渡点坐标本文进行了如下计算：设点A(Xa,Ya,Za)和点C(Xc,Yc,Zc)位于直线1上，点B(Xb,Yb,Zb)和点D(Xd,Yd,Zd)位于直线2上。

直线1和直线2的数学表达式如下：

(3)

(4)

设不同平面的公垂线的方向向量：[A,B,C]。因为公垂线与线1和线2正交可得式：

(5)

可知：

可知线1和公垂线确定的平面α定义为：

(6)

为方便计算本文将简化部分运算式，设H=Xc-Xa;I=Yc-Ya;J=Zc-Za;K=Xd-Xb;L=Yd-Yb;M=Zd-Zb，同时设式(7)。

(7)

由式(7)可将平面α和线2表示为式(8)。

(8)

2 求解方法描述

2.1 标准蚁群算法

在蚁群算法中，蚂蚁通过满足一定的概率规则来判断下一钻孔点的去向，式(9)为该概率规则。

(9)

式中，τij(t)表示t次迭代过程中钻孔点i到下一钻孔点j路径上的信息素值；ηij(t)表示钻孔点i到下一钻孔点j的路径长度的倒数，其值越大表示路径越短蚂蚁越容易选择j作为下一钻孔点；Allowed表示蚂蚁K没有遍历的钻孔点；α和β为两个可以调整的参数，分别代表信息素浓度和自启发因子的权重[14]。遍历完所有钻孔点后则要进行信息素的更新，其表达式如下：

(10)

(11)

2.2 自适应蚁群算法

2.2.1自适应蚁群算法原理

自适应蚁群算法通过提出一种可动态变化ρ值的办法能很好地解决标准蚁群算法“早熟”现象。其信息素挥发公式为：

(12)

式中，φ,λ均为常系数，nc为迭代次数，ncmax为最大迭代次数。分析可知在算法运行初期由于ρ(nc)值较大从而使得算法收敛速度加快。在算法迭代后期，路径上的信息素Δτij(t)积累并不断增加导致算法陷入局部最优，由上式(12)可知信息素挥发系数ρ(nc)逐渐减少，从而使得算法容易跳出局部寻优。

自适应蚁群算法流程如下：

(1)初始化各参数：迭代次数nc，ncmax、α信息素重要程度参数和β启发式因子重要程度参数、蚂蚁个数m、信息素值τ、自适应常系数φ,λ、信息素增强参数Q。

(2)将m个蚂蚁放置于n个钻孔点上。

(3)m个蚂蚁按照式(9)规则选择下一钻孔点，完成各自钻孔点的遍历。

(4)记录本次遍历过程的最优路径。

(5)根据式(10)～式(12)更新全局信息素值。

(6)若满足最大迭代次数条件下，则求解结束,得出最短钻孔距离，否则nc=nc+1，转入(2)进行下一次迭代。

2.2.2 算例验证

本文选用TSPLIB中的4个TSP问题：eli76、eli51、att48、chn31，利用标准蚁群算法和自适应蚁群算法进行测试。分别测试30次取其平均值，算法参数设置见表1所示，算法求解结果如图6～图9所示。

表1 自适应蚁群算法参数设置

自适应蚁群算法对上述问题求得的最优解分别为：583、460、35120、15631。对于att48案例，自适应蚁群算法在迭代前20次的收敛速度快于标准蚁群算法，在23次迭代后自适应蚁群算法收敛于最优解，而标准蚁群算法其最优解的精度和收敛性都要低于自适应蚁群算法，其他案例亦然。

图6 chn31仿真结果

图7 att48仿真结果

图8 eil51仿真结果

图9 eil76仿真结果

2.3 分区自适应蚁群算法

数控钻床在进行钻孔加工时，需要加工的孔会很多，自适应蚁群算法很难使得求解出的路径为最优解。钻孔点的分区按照物以类聚，就近分配的原则[17]，将K个钻孔点表示：Xj=(xj1,xj2,xj3…xjk)，在遵循划分原则的条件下对其进行N个区间划分：Xj=([xj11,xj12…],[xj21,xj22…],…[xjn1,xjn2…])。例如K=7,N=3时则可以将钻孔点区域划分：Xj=([1，2],[3，4],[5，6，7])。该算法的核心思想是分区求解最优解或次优解，然后寻找区域之间的最优解或次优解，最终得到求解结果。区域划分应该保证该区域尽可能多的钻孔点且分布区域面积尽量大，其示意图如图10所示。

(a) 钻孔点描述 (b) 钻孔点分区

该分区自适应蚁群算法的步骤为：

(1)按照分区原则，对所有钻孔点进行分区规划，确定每一区域钻点坐标，初始化算法各参数。

(2)将m个蚂蚁放置于每一区域n个钻孔点上。

(3) 蚂蚁按照概率公式(9)选择下一钻孔点走向，完成各钻孔点遍历。

(4)记录蚂蚁本次遍历的最优钻孔路径。

(5)根据式(10)～式(12)更新本次钻孔路径信息素和全局路径信息素。

(6) 寻找各区域边界点，通过几何避障法确定交线过渡点坐标位置，计算各区域之间安全加工距离。

(7)清空禁忌表，到达最大迭代次数时结束运算，输出结果，否则跳转到(2)继续运算。

3 仿真结果分析

以某数控车床夹具72个螺纹孔为实例，利用Matlab R2016a软件编写算法程序，分区自适应蚁群算法和标准蚁群算法得到的优化钻孔顺序如表2所示。仿真结果如图11和图12所示，图13和图14分别显示了算法收敛性和优化目标之间的关系，表3为两种算法参数设置。

表2 钻孔优化顺序对比

图11 分区自适应蚁群算法优化结果

图12 标准蚁群算法优化结果

图13 平均距离优化结果

图14 最短距离优化结果

表3 标准蚁群算法及分区自适应蚁群算法参数

分区自适应蚁群算法得到的最优解较标准蚁群算法的最优解缩短了132.2 mm且分区自适应蚁群算法在第22次迭代之后算法收敛到最短钻孔加工路径距离1 119.7 mm，而标准蚁群算法在第92次迭代时才收敛到最短钻孔加工路径距离1 251.9 mm；在开始进行迭代时分区自适应蚁群算法距最优解较短而标准蚁群算法离最优解还有一定距离。上述仿真结果表明：在进行大规模钻孔加工作业时，由于问题规模的增大，标准蚁群算法在这种情况下其解空间更容易陷入局部最优。将大规模问题分解成数个小规模问题，再通过引入自适应变化的信息素挥发素之后，分区自适应蚁群算法较标准蚁群算法有更好解的精度且不易陷入局部最优解，其全局搜索能力和收敛性都要明显优于标准蚁群算法。综上所述，通过分区和加入动态变化的信息素挥发系数使得分区自适应蚁群算法在解决大规模钻孔加工路径优化问题时能更快且更准确地得到最优或次优钻孔加工路径。

4 结论

现有数控钻床在钻孔工作时，钻孔加工孔序确定通常由人工完成，存在钻孔加工路径距离无优化且效率低的问题。本文针对多面体数控钻床加工路径优化问题，主要研究了钻孔加工过程中钻头空程走刀路径距离及其避障方法，基于物以类聚，就近分配的思想，提出了分区自适应蚁群算法，使该算法应用于某数控车床夹具72个螺纹钻孔加工路径距离寻优问题中。仿真结果表明该算法优于标准蚁群算法，其最优解较标准蚁群算法提高11.8%，并且收敛速度有明显提升，对实现多面体数控钻床加工效率提高及节约加工成本有一定的指导作用。