基于混合算法的數控加工路徑規劃優化

摘 要： 對數控加工中的孔群加工路徑規劃優化方法進行研究。將孔群的加工路徑規劃問題與典型旅行商問題進行類比，建立刀具空行程最短的數學模型和適應度函數。針對常規混合算法不能夠將兩種算法進行融合，只是單純疊加，無法在最佳時機進行算法轉化，使得算法混合優勢不夠明顯等問題，該文對混合算法進行改進。使用遺傳算法得到若干優化解，并將其變成初始信息素從而改成初始信息素偏低問題。使用動態轉移代替靜態轉移法將遺傳算法切換到蟻群算法。算法后期，信息素更新方法使用動態揮發系數法，對交叉變異概率使用信息素和適應度進行動態調節，交叉變異位置使用信息素和啟發信息決定。以一種機械零件的孔群加工為例，對研究的混合算法的加工路徑規劃優化方法進行實例分析，結果表明相比常規混合算法，該文研究的混合算法具有更高的求解精度和優化效果。

關鍵詞： 數控加工； 孔群加工； 路徑規劃； 混合算法

中圖分類號： TN911?34； TP18 文獻標識碼： A 文章編號： 1004?373X（2016）16?0055?03

Abstract： The optimization method of hole group machining path planning in NC machining is studied in this paper. The problem of hole group machining path planning is compared with the typical traveling salesman problem， and the mathematical model and fitness function of shortest air travel of cutting tool are set up. Since the conventional hybrid algorithm can not integrate the two algorithms together， but only a simple stack， and can not perform algorithm conversion in the best time， which makes the hybrid algorithm superiority unobvious， the hybrid algorithm is improved in this paper. The genetic algorithm is used to get a number of optimization solutions， which would be turned into the initial pheromone to change the situation that the initial pheromone is low. The genetic algorithm is switched to the ant colony algorithm by using the dynamic transfer instead of the static transfer method. In the latter stage， the dynamic volatile coefficient method is used in the pheromone updating method. The pheromone and adaptive degree are adopted to adjust the probability of cross mutation dynamically. The cross mutation position is determined by information elements and heuristic information. Taking the machining of a machine part as an example， the machining path planning optimization method of the hybrid algorithm is analyzed in this paper. The results show that the hybrid algorithm has higher accuracy and better effect in comparison with the conventional hybrid algorithm.

Keywords： NC machining； hole group machining； path planning； hybrid algorithm

0 引 言

孔群加工是數控加工中一個非常常見的任務，孔加工在箱體、蓋板以及底座等機械零件加工時占有很大比例。孔群加工的生產效率不僅受單個鉆孔時間的影響，而且還受加工刀具在孔與孔之間運動的輔助時間影響，根據統計分析，傳統孔群加工時，總加工時長的70%以上都消耗在了輔助時間上，因此對于加工路徑進行優化，縮短輔助時間對于提高加工效率以及降低能耗等具有重要意義，也是數控加工領域的熱點研究問題之一[1?2]。

1 加工路徑規劃問題模型

可以將孔群的加工路徑規劃問題與典型旅行商問題進行類比，最優的加工路徑即要求加工刀具以最短的空行程保證經過每一個孔位置一次。使用數學語言描述為：設定一個帶正權的完全圖[G=V，E]，其中[V={1，2，…，n}]，[E]為邊集合，設定[dij]為邊的權值；經過V上各個頂點的回路即G的巡回路線；該條路線權值的和就是該路線的消耗；加工路徑規劃問題和旅行商問題就是對巡回路線的消耗求解最小值的問題，可以用以下模型描述：

加工路徑規劃或典型TSP問題已經通過數學方法得到精確解，但是這種精確解法不適用于節點眾多的工程問題。粒子群優化算法、遺傳優化算法以及人工免疫算法、神經網絡算法和蟻群算法等現代智能算法能夠較好地解決這種解空間為“組合爆炸”式的組合優化問題。因此本文采用遺傳算法和粒子群算法混合的算法進行加工路徑優化研究[3?4]。

2 混合算法

常規遺傳算法初始計算速率較快，但是會導致局部尋優能力下降；另外由于不能夠對系統反饋路徑信息進行較好的利用，會產生冗余迭代，陷入局部最小值等缺點。常規蟻群算法存在初始信息素偏低而產生的計算速率低以及陷入局部最小值等缺點。

目前常規的混合算法已經能夠將遺傳算法和蟻群算法進行簡單結合，以期望發揮各自優勢；但是由于常規的混合算法不能夠將兩種算法進行融合，只是單純疊加，無法在最佳時機進行算法轉化，使得算法混合優勢不夠明顯[5]。

為此，本文使用遺傳算法得到若干優化解，并將其變成初始信息素從而改成初始信息素偏低問題。使用動態轉移代替靜態轉移法將遺傳算法切換到蟻群算法。算法后期，信息素更新方法使用動態揮發系數法，對交叉變異概率使用信息素和適應度進行動態調節，交叉變異位置使用信息素和啟發信息決定。本文研究的混合算法的操作流程[6]如下：

Step1：根據任務確定目標函數和適應度函數；

Step2：由遺傳算法生成[nGA]組優化解；

Step3：將生成的[nGA]組優化解通過信息素轉換方法變為初始信息素；

Step4：對蟻群算法的參數進行初始化，并隨機地將M個螞蟻放置在N個節點處；

Step5：根據螞蟻狀態轉移規則構造的搜索機制遍歷所有N個節點，構成一個路徑；

Step6：對各個路徑的信息素含量以及適應值進行求解，并通過選擇操作，確定如果結束條件已滿足，則跳至Step10，如果結束條件沒有滿足，則跳至Step7；

Step7：交叉變異操作獲得的M條路徑；

Step8：對已獲得的（M+U）條路徑，根據適應度和信息素含量進行排序，并抽取排名前M條路徑；

Step9：對信息素進行更新，并跳回Step5；

Step10：獲得全局最優的路徑，完成優化任務。

本文采用的動態控制適應度函數方法為[7]：

[Fi=F+k1cNc1Fi-FFmax-FF， Fi≥FF+k2cNc2F-FiF-FmaxF ， Fi

式中：[F]是適應度平均值；[Nc]是迭代次數；[k1]，[k2]，[c1]，[c2]均為調節系數。

構造新的搜索機制，螞蟻按照下面方式選擇節點：

[J=J1=argmaxj∈allowedkταij?ηβij ， 0≤q

式中：[allowedk]表示螞蟻下一次運行選取的節點；[q]是0～1的隨機數；[ταij]是邊（i，j）的信息素含量；[pkij]是在第i個節點、第k個螞蟻選取第j個節點的概率；[q1]和[q2]由用戶設定；

以提高算法進化質量，設定兩個終止條件，即進化次數達到設定值，或連續若干代的個體平均適應值和信息素含量低于設定的閾值[8?10]。

3 實例分析

本文以一種機械零件的孔群加工為例，對本文研究的混合算法的加工路徑規劃優化方法進行實例分析，待加工機械零件中孔群分布如圖1所示[11?14]。

該零件共有個30孔需要加工，需要對其進行路徑規劃。設定遺傳算法中參數：最大和最小迭代次數分別為50和10，停滯代數[Ddtz]=5，[nGA]=10。蟻群算法中參數為：α=1，β=4，γ=2，κ=2.5，δ=2.5，λ=1.5，ρGA=0.7，NCASmax=300。以鉆頭空行程最小為目標函數，建立相應的適應度函數為：

[f=1i=1n-1xi-xi+12+yi-yi+12+xn-x12+yn-y12] （4）

使用本文研究的混合算法得到的加工路徑為：K1?K12?K11?K13?K14?K18?K21?K20?K24?K25?K22?K26?K27?K28?K29?K30?K23?K19?K17?K16?K15?K9?K8?K5?K4?K3?K6?K7?K2?K1。使用常規混合算法得到加工路徑如圖2所示，使用本文研究的混合算法得到的加工路徑如圖3所示。

使用傳統加工方法的路徑長度為4 551.36 mm，使用常規混合算法得到加工路徑長度為1 526.23 mm，比傳統加工方法的路徑縮短了66.47%。使用本文研究的混合算法得到的加工路徑長度為1 263.21 mm，比傳統加工方法的路徑縮短了72.25%，比常規混合算法得到加工路徑縮短了17.23%。因此，相比常規遺傳算法，本文研究的混合算法具有更高的求解精度和優化效果。

4 結 論

本文將孔群的加工路徑規劃問題與典型旅行商問題進行類比，建立加工路徑規劃問題的數學模型。本文采用遺傳算法和粒子群算法混合的算法進行加工路徑優化研究，以鉆頭空行程最小為目標函數，建立相應的適應度函數。以一種機械零件的孔群加工為例，對本文研究的混合算法的加工路徑規劃優化方法進行實例分析，結果表明，相比常規混合算法，本文研究的混合算法具有更高的求解精度和優化效果，對于提高加工效率以及降低能耗等具有一定意義。

參考文獻

[1] 丁同梅.基于GA切削參數和TSP孔群加工路徑優化的研究[D].天津：天津大學，2007.

[2] 凌玲，胡于進，王青青，等.基于改進遺傳算法的孔群加工路徑優化[J].華中科技大學學報（自然科學版），2009（8）：88?91.

[3] 董力，黃宗南，趙學中.基于改進遺傳算法的點位加工路徑優化[J].機械制造，2007（2）：35?37.

[4] 馬兆敏，黃玲，胡波，等.帶基準孔的孔群加工路徑優化算法[J].機床與液壓，2008，36（11）：28?29.

[5] 劉保業.基于改進遺傳蟻群算法的激光加工路徑規劃[D].青島：青島理工大學，2012.

[6] 許方.基于混合蛙跳算法的Web文本聚類研究[D].無錫：江南大學，2013.

[7] 黃發良，蘇毅娟.基于GA與PSO混合優化的Web文檔聚類算法[J].小型微型計算機系統，2013，34（7）：1531?1533.

[8] 陳琳，劉曉琳，潘海鴻，等.孔群分類加工路徑的優化算法[J].制造業自動化，2013（17）：46?49.

[9] 蔡蕓，周立煒.人工魚群算法在孔群加工路徑優化中的應用研究[J].武漢科技大學學報，2011（3）：182?185.

[10] 王春香，郭曉妮.基于遺傳蟻群混合算法的孔群加工路徑優化[J].機床與液壓，2011，39（21）：43?45.

[11] 肖軍民.一種改進遺傳算法在孔群加工路徑中的優化[J].組合機床與自動化加工技術，2015（2）：151?153.

[12] 王鑫.基于加工特征的機床關鍵零件高效數控加工切削參數優化技術研究[D].株洲：湖南工業大學，2014.

[13] 王笑蓉.蟻群優化的理論模型及在生產調度中的應用研究[D].杭州：浙江大學，2003.

[14] 李薇.遺傳算法及其在TSP問題中的應用研究[D].貴陽：貴州大學，2008.