孔群分类加工路径的优化算法

2015年06月03日

  0 引言
    柔性钣金钻削或攻丝加工中,孔群加工所占的比重较大,如果不对加工路径进行优化,将直接影响生产效率。孔群加工中,不同孔径的圆孔需分类使用不同刀具加工,相当多的时间花费在刀具移位和换刀等辅助加工时间上。因此,合理规划孔群加工路径,缩短刀具总的空行程距离、减少换刀次数,将有助于减少辅助加工时间,提高加工效率,延长设备使用寿命。孔群加工路径规划是典型旅行商问题(Travelling SalesmanProblem,TSP),其解空间存在“组合爆炸”。该问题在数学上可获得精确解,但对于大规模节点,这种解法耗时巨大,难以满足工程中实际应用。因此,为解决工程中实际问题,常求解该问题的近似解,这些近似解在一定程度上满足工程的实际需求。近年来,产生很多搜索算法,如贪心算法、蚁群算法、遗传算法、模拟退火算法等。对孔群加工而言,2006年丁静等人综合直线/阵列法、最近邻居点法、亲近点法后优化了钣金件孔群加工路径。2007年曲晶等人引入蚁群算法优化PCB板加工中的孔群加工路径。2008年张振普等针对孔群加工路径分析研究多种典型优化算法,表明贪心算法解决问题效率高、时间复杂度低。这些方法在一定程度上优化孔群加工路径。针对孔群中分类使用不同刀具加工问题,本文提出蚁群算法与贪心算法相结合,同一类孔之间采用蚁群算法,不同类孔之间过渡应用贪心算法获得最近的孔,而采用其他智能概率搜索算法获得解不唯一,最后在自主开发钣金刻铣加工CAD/CAM软件中进行实例验证。

1 问题描述
    针对柔性钣金对孔群进行钻削或攻丝加工时,孔群中不同类型的孔需通过切换不同刀具来完成加工要求。在实际加工生产中,若不考虑切换刀具的次数与频率这一影响因素,直接按最短路径标准进行孔群的路径优化,显然会因为换刀次数的增加而浪费加工时间,降低加工效率。所以为将换刀次数降到最少,在进行孔群路径优化时,使用同一把刀具加工完所有可加工的孔,再换刀。
    在上述前提下,将孔群钻削或攻丝加工过程概括如下:对某一类孔,换上对应刀具后,从指定的孔开始,沿着使该刀具总的空行程最短轨迹,从一个孔移动到另一孔,直到该类孔都被加工完,再由该类最后被加工的孔查找与之最近的下一类某个孔,进行下一类孔的加工,如此循环,直到所有孔被加工完。把此问题描述成以下优化模型:
    (1) 变量设计。假设某孔群有N个孔,按所使用不同刀具加工分为m类。第r类孔数量为rn(r =1,2,…,m),则

    第r类中第k个孔表示为Hrk(r=1,2,…,m,k=1,2,…,nr),则第r类孔组成集合Vr={Hr1,Hr2,…,Hrn} 。dij表示任意两个孔之间的距离。
    (2)目标函数。在集合Vr中,采用蚁群算法找到一个不重复的全排列 Gr= {Gr1,Gr2,...G rn},使得


取得最小值。由第r类最后被加工孔Grnr查找下一类某个孔,使得M=min(d (Gmr,Hgk)),g=1,2,…,m&g≠ r,取得最小值。
(3) 约束条件。加工路径从一个孔出发,对每一个孔只加工一次,遍历加工每个孔,直到所有孔都被加工完。
(4) 优化算法。同一类孔之间采用蚁群算法,不同类孔之间采用贪心算法。

2 路径优化的混合算法
    柔性钣金加工中心在对孔群进行钻削或攻丝加工时,需更换刀具对孔群中不同种类的孔既不重复也不遗漏地加工完,因此要对孔群进行分类规划加工轨迹。针对孔群加工轨迹规划问题,研究比较近年来产生的贪心算法、蚁群算法等优化求解算法。因这两种算法在优化求解孔群加工轨迹规划问题上各有优劣,故提出蚁群算法与贪心算法相结合的混合算法优化求解孔群路径,进而缩短钻头或丝锥空走行程,提高实际生产中钻削或攻丝加工孔群的效率。下面将对蚁群算法和贪心算法的实现及特点进行概述,并详细阐述蚁群算法与贪心算法相结合的具体实现及巧妙结合过程。

2.1 蚁群算法及贪心算法概述
    使用蚁群算法解决孔群路径优化问题时,用τij 表示第i孔和第j孔连线上信息素强度,初始值τij(0)=(n.Lnn)-1 ,其中n为圆孔个数,Lnn为最近邻域启发产生路径长度。ηij为启发因子,其值为1/ dij,表示(i,j)的能见度。P kij表示第k蚂蚁由位置i转移到位置j 的概率。蚂蚁在运动过程中,依据伪随机比例规则由位置i转移到位置j,如式(1)和(2)所示。

 
随着时间推移,信息素不停地挥发,定义α为全局挥发系数,ρ为局部挥发系数。蚂蚁每次位置移动,依据式(3)对所经过路径上信息素进行局部更新。


经过n个时刻,所有的蚂蚁完成一次搜索,依据式(4)更新当前搜索到最优路径上各边的信息量,其中Δτij (t+n)为边(i,j)上信息增量,Lgb为当前全局最优路径。
    蚁群算法具有正反馈性、并行性和隐含性的特点,使算法具有强大的优化性能和快速的收敛性能,其优劣性能与全局挥发系数、局部挥发系数有关,如选择不合适易使算法陷入局部最优。贪心算法是指从问题的初始状态出发,直接去求解每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解。贪心算法的特点是算法复杂度低,运算速度快,但它并不是从整体上加以考虑,只是获得问题的局部最优解。

 

2.2 混合算法
    在对柔性钣金实际加工生产中,通常同一类型孔群中圆孔数量很多,而孔群分类的类型数则较少。若对同一类孔群中数量较多且分布无序的圆孔采用贪心算法进行优化,因其算法思想应用局部最优策略,致使刀具空走行程往往有增无减,实际求得的解并非最优。在此情形下使用蚁群算法进行优化,可有效避免陷入局部最优解,从而解决贪心算法存在的不足。若对分类较少的孔群之间过渡路径采用蚁群算法进行优化,因蚁群算法其优劣性能易受挥发系数、搜索蚂蚁数目等其他基本参数的设置影响,求得解波动较大,很难得到最优解。这种情况下使用蚁群算法这种智能概率搜索算法不一定能找到距离最近的孔,而采用贪心算法能确定找到距离最近的孔。由此可见,蚁群算法与贪心算法分别独自解决孔群分类加工的路径优化问题都不能取得很好的优化效果。
    为在解决孔群分类加工路径优化问题上取得良好的优化效果,根据蚁群算法和贪心算法各自特点和优劣,提出将蚁群算法与贪心算法的优点巧妙结合利用,对同一种类下的孔与孔之间加工路径进行优化时采用蚁群算法,对不同种类的孔群间的过渡加工路径进行优化时采用贪心算法,从而得出蚁群算法与贪心算法相结合的混合算法以缩短刀具加工时的路径长度,提高实际加工效率。


混合算法流程图如图1所示。
混合算法步骤如下:
<1>参数初始化。假定m只蚂蚁,孔群共分为e类,循环次数N=0,c=0,最大迭代次数为Nmax。
<2>由某一个孔查找与之同类的孔组成集合r V 。
<3>循环次数N ← N +1。
<4>蚂蚁数目k ←k +1。
<5>对第k只蚂蚁,根据公式(1)选择节点j,并前进。
<6>把选择的节点j加入到第k只蚂蚁的禁忌表中,并修改表allowedk。
<7>根据公式(3)更新该边上的信息量。
<8>若第k只蚂蚁没有遍历完nr个节点,则转到第<5>步,若遍历完所有的节点,则转到第<8>步。
<9>若蚂蚁数k小于蚂蚁总数m,则转到第<4>步,直到m只蚂蚁遍历完rn个节点,再执行第<10>步。
<10>根据公式(4)更新当前搜索到最优路径上各边的信息量。
<11>若循环次数N未达到最大迭代次数Nmax ,则转到第<3>步,若达到最大迭代次数则结束循环,并输出最优路径Gr= {Gr1,Gr2,…,Grn}。
<12>循环次数c←c +1。
<13>若循环次数c ≤ e,由<11>中找到的最优路径Gr最后被加工的孔Grnr采用贪心算法在未加工孔中查找与之最近的下一类某个孔,并转到第<2>步,若c > e则结束程序。

3 钣金刻铣加工CAD/CAM中孔群路径优化实验结果与分析
    在自主开发的钣金刻铣加工CAD/CAM软件中,以分布无序的3类共41个圆孔孔群进行实例验证,其中3类孔群的孔径大小分别设置为60mm、30mm、20mm,圆孔数量相应设置为14、18、9个,分别使用刀具T1、T2、T3、加工,进而对比混合算法与X向路径法、Y向路径法、贪心算法及蚁群算法优化孔群加工路径效果。

 

3.1 路径优化实验
    X向路径法是孔群按其X坐标值进行排序。经过X向路径法优化后孔群加工路径长度为18389.2mm,结果如图2(a)。Y向路径法是孔群按其Y坐标值进行排序。经过Y向路径法优化后孔群加工路径长度为20582.6mm,结果如图2(b)。贪心算法是从指定孔开始,访问与其最邻近的孔,然后继续在没有访问的孔中选择最邻近的孔,直到所有孔都访问完。经过贪心算法优化后孔群加工路径长度为11823.6mm,结果如图2(c)。蚁群算法模拟蚂蚁觅食行为,寻找最优路径。参数设置与混合算法蚁群部分相同。在相同参数设置的情况下,应用蚁群算法进行10次路径优化实验,实验数据如表1所示,其路径长度平均值为11204.7mm,最优值为10839.8mm,结果如图2(d)。混合算法参数设置如下:全局更新规则挥发系数α=0.1,局部更新规则挥发系数ρ=0.1,期望启发因子β=5,孔群分类数e=3,阀值q0=0.9,迭代次数为2000。在相同参数设置的情况下,应用混合算法进行10次路径优化实验,实验数据如表2,其路径长度平均值为10511.5mm,最优值为10054.0mm,结果如图3所示。

 

3.2 实验数据分析
由表3中不同算法优化后孔群加工路径长度及耗时对比可知,混合算法优化后路径长度比X向路径法优化后缩短42.84%,比Y向路径法优化后缩短48.93%,比贪心算法优化后缩短11.10%,比蚁群算法优化后缩短6.19%。由此可见,混合算法优化后路径长度最短,能够有效缩短加工路径,节省时间,提高加工效率。

4 结束语
在对柔性钣金进行钻削或攻丝加工孔群时的路径优化,为解决频繁换刀造成设备寿命缩短、
辅助时间增加、效率降低等问题,本文提出混合算法优化孔群分类加工路径,并以孔群分布无序为例,在自主开发的钣金刻铣加工CAD/CAM软件中进行实例验证。通过与X向路径法、Y向路径法、贪心算法及蚁群算法相对比,混合算法优化后路径长度最短。将混合算法应用在柔性钣金孔群分类钻削或攻丝加工中,合理规划孔群加工路径,可以有效缩短刀具空行程距离,提高加工效率。

来源:石家庄塔迈洛机电科技有限公司
石家庄塔迈洛机电科技有限公司
王丽花
经营模式 :
生产厂家
所在地区 :
河北省 石家庄市 桥西区 中华南大街517号

在线客服

在线时间

周一至周五
8:00-18:00

周六至周日
8:00-21:00