分區自適應蟻群算法的多面體數控鉆床加工路徑優化*

游海濤，羅紅波，董 特，施顯陽

(四川大學機械工程學院，成都 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%，并且收斂速度有明顯提升，對實現多面體數控鉆床加工效率提高及節約加工成本有一定的指導作用。