基于混合算法的數(shù)控加工路徑規(guī)劃優(yōu)化

摘 要： 對(duì)數(shù)控加工中的孔群加工路徑規(guī)劃優(yōu)化方法進(jìn)行研究。將孔群的加工路徑規(guī)劃問(wèn)題與典型旅行商問(wèn)題進(jìn)行類比，建立刀具空行程最短的數(shù)學(xué)模型和適應(yīng)度函數(shù)。針對(duì)常規(guī)混合算法不能夠?qū)煞N算法進(jìn)行融合，只是單純疊加，無(wú)法在最佳時(shí)機(jī)進(jìn)行算法轉(zhuǎn)化，使得算法混合優(yōu)勢(shì)不夠明顯等問(wèn)題，該文對(duì)混合算法進(jìn)行改進(jìn)。使用遺傳算法得到若干優(yōu)化解，并將其變成初始信息素從而改成初始信息素偏低問(wèn)題。使用動(dòng)態(tài)轉(zhuǎn)移代替靜態(tài)轉(zhuǎn)移法將遺傳算法切換到蟻群算法。算法后期，信息素更新方法使用動(dòng)態(tài)揮發(fā)系數(shù)法，對(duì)交叉變異概率使用信息素和適應(yīng)度進(jìn)行動(dòng)態(tài)調(diào)節(jié)，交叉變異位置使用信息素和啟發(fā)信息決定。以一種機(jī)械零件的孔群加工為例，對(duì)研究的混合算法的加工路徑規(guī)劃優(yōu)化方法進(jìn)行實(shí)例分析，結(jié)果表明相比常規(guī)混合算法，該文研究的混合算法具有更高的求解精度和優(yōu)化效果。

關(guān)鍵詞： 數(shù)控加工； 孔群加工； 路徑規(guī)劃； 混合算法

中圖分類號(hào)： TN911?34； TP18 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

孔群加工是數(shù)控加工中一個(gè)非常常見的任務(wù)，孔加工在箱體、蓋板以及底座等機(jī)械零件加工時(shí)占有很大比例?？兹杭庸さ纳a(chǎn)效率不僅受單個(gè)鉆孔時(shí)間的影響，而且還受加工刀具在孔與孔之間運(yùn)動(dòng)的輔助時(shí)間影響，根據(jù)統(tǒng)計(jì)分析，傳統(tǒng)孔群加工時(shí)，總加工時(shí)長(zhǎng)的70%以上都消耗在了輔助時(shí)間上，因此對(duì)于加工路徑進(jìn)行優(yōu)化，縮短輔助時(shí)間對(duì)于提高加工效率以及降低能耗等具有重要意義，也是數(shù)控加工領(lǐng)域的熱點(diǎn)研究問(wèn)題之一[1?2]。

1 加工路徑規(guī)劃問(wèn)題模型

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

加工路徑規(guī)劃或典型TSP問(wèn)題已經(jīng)通過(guò)數(shù)學(xué)方法得到精確解，但是這種精確解法不適用于節(jié)點(diǎn)眾多的工程問(wèn)題。粒子群優(yōu)化算法、遺傳優(yōu)化算法以及人工免疫算法、神經(jīng)網(wǎng)絡(luò)算法和蟻群算法等現(xiàn)代智能算法能夠較好地解決這種解空間為“組合爆炸”式的組合優(yōu)化問(wèn)題。因此本文采用遺傳算法和粒子群算法混合的算法進(jìn)行加工路徑優(yōu)化研究[3?4]。

2 混合算法

常規(guī)遺傳算法初始計(jì)算速率較快，但是會(huì)導(dǎo)致局部尋優(yōu)能力下降；另外由于不能夠?qū)ο到y(tǒng)反饋路徑信息進(jìn)行較好的利用，會(huì)產(chǎn)生冗余迭代，陷入局部最小值等缺點(diǎn)。常規(guī)蟻群算法存在初始信息素偏低而產(chǎn)生的計(jì)算速率低以及陷入局部最小值等缺點(diǎn)。

目前常規(guī)的混合算法已經(jīng)能夠?qū)⑦z傳算法和蟻群算法進(jìn)行簡(jiǎn)單結(jié)合，以期望發(fā)揮各自優(yōu)勢(shì)；但是由于常規(guī)的混合算法不能夠?qū)煞N算法進(jìn)行融合，只是單純疊加，無(wú)法在最佳時(shí)機(jī)進(jìn)行算法轉(zhuǎn)化，使得算法混合優(yōu)勢(shì)不夠明顯[5]。

為此，本文使用遺傳算法得到若干優(yōu)化解，并將其變成初始信息素從而改成初始信息素偏低問(wèn)題。使用動(dòng)態(tài)轉(zhuǎn)移代替靜態(tài)轉(zhuǎn)移法將遺傳算法切換到蟻群算法。算法后期，信息素更新方法使用動(dòng)態(tài)揮發(fā)系數(shù)法，對(duì)交叉變異概率使用信息素和適應(yīng)度進(jìn)行動(dòng)態(tài)調(diào)節(jié)，交叉變異位置使用信息素和啟發(fā)信息決定。本文研究的混合算法的操作流程[6]如下：

Step1：根據(jù)任務(wù)確定目標(biāo)函數(shù)和適應(yīng)度函數(shù)；

Step2：由遺傳算法生成[nGA]組優(yōu)化解；

Step3：將生成的[nGA]組優(yōu)化解通過(guò)信息素轉(zhuǎn)換方法變?yōu)槌跏夹畔⑺兀?/p>

Step4：對(duì)蟻群算法的參數(shù)進(jìn)行初始化，并隨機(jī)地將M個(gè)螞蟻放置在N個(gè)節(jié)點(diǎn)處；

Step5：根據(jù)螞蟻狀態(tài)轉(zhuǎn)移規(guī)則構(gòu)造的搜索機(jī)制遍歷所有N個(gè)節(jié)點(diǎn)，構(gòu)成一個(gè)路徑；

Step6：對(duì)各個(gè)路徑的信息素含量以及適應(yīng)值進(jìn)行求解，并通過(guò)選擇操作，確定如果結(jié)束條件已滿足，則跳至Step10，如果結(jié)束條件沒(méi)有滿足，則跳至Step7；

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

Step8：對(duì)已獲得的（M+U）條路徑，根據(jù)適應(yīng)度和信息素含量進(jìn)行排序，并抽取排名前M條路徑；

Step9：對(duì)信息素進(jìn)行更新，并跳回Step5；

Step10：獲得全局最優(yōu)的路徑，完成優(yōu)化任務(wù)。

本文采用的動(dòng)態(tài)控制適應(yīng)度函數(shù)方法為[7]：

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

式中：[F]是適應(yīng)度平均值；[Nc]是迭代次數(shù)；[k1]，[k2]，[c1]，[c2]均為調(diào)節(jié)系數(shù)。

構(gòu)造新的搜索機(jī)制，螞蟻按照下面方式選擇節(jié)點(diǎn)：

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

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

以提高算法進(jìn)化質(zhì)量，設(shè)定兩個(gè)終止條件，即進(jìn)化次數(shù)達(dá)到設(shè)定值，或連續(xù)若干代的個(gè)體平均適應(yīng)值和信息素含量低于設(shè)定的閾值[8?10]。

3 實(shí)例分析

本文以一種機(jī)械零件的孔群加工為例，對(duì)本文研究的混合算法的加工路徑規(guī)劃優(yōu)化方法進(jìn)行實(shí)例分析，待加工機(jī)械零件中孔群分布如圖1所示[11?14]。

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

[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。使用常規(guī)混合算法得到加工路徑如圖2所示，使用本文研究的混合算法得到的加工路徑如圖3所示。

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

4 結(jié) 論

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

參考文獻(xiàn)

[1] 丁同梅.基于GA切削參數(shù)和TSP孔群加工路徑優(yōu)化的研究[D].天津：天津大學(xué)，2007.

[2] 凌玲，胡于進(jìn)，王青青，等.基于改進(jìn)遺傳算法的孔群加工路徑優(yōu)化[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2009（8）：88?91.

[3] 董力，黃宗南，趙學(xué)中.基于改進(jìn)遺傳算法的點(diǎn)位加工路徑優(yōu)化[J].機(jī)械制造，2007（2）：35?37.

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

[5] 劉保業(yè).基于改進(jìn)遺傳蟻群算法的激光加工路徑規(guī)劃[D].青島：青島理工大學(xué)，2012.

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

[7] 黃發(fā)良，蘇毅娟.基于GA與PSO混合優(yōu)化的Web文檔聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，34（7）：1531?1533.

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

[9] 蔡蕓，周立煒.人工魚群算法在孔群加工路徑優(yōu)化中的應(yīng)用研究[J].武漢科技大學(xué)學(xué)報(bào)，2011（3）：182?185.

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

[11] 肖軍民.一種改進(jìn)遺傳算法在孔群加工路徑中的優(yōu)化[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2015（2）：151?153.

[12] 王鑫.基于加工特征的機(jī)床關(guān)鍵零件高效數(shù)控加工切削參數(shù)優(yōu)化技術(shù)研究[D].株洲：湖南工業(yè)大學(xué)，2014.

[13] 王笑蓉.蟻群優(yōu)化的理論模型及在生產(chǎn)調(diào)度中的應(yīng)用研究[D].杭州：浙江大學(xué)，2003.

[14] 李薇.遺傳算法及其在TSP問(wèn)題中的應(yīng)用研究[D].貴陽(yáng)：貴州大學(xué)，2008.