龔玉玲，武美萍，徐曉棟，龔 非

(1.泰州學(xué)院 船舶與機電工程學(xué)院，江蘇 泰州 225300；2.江南大學(xué) 機械工程學(xué)院 江蘇省食品先進制造裝備技術(shù)重點實驗室，江蘇 無錫 214122；3.中國航天科工集團8511研究所，南京 210007)

基于改進遺傳算法的孔群數(shù)控加工路徑優(yōu)化*

龔玉玲1，武美萍2，徐曉棟1，龔 非3

(1.泰州學(xué)院 船舶與機電工程學(xué)院，江蘇 泰州 225300；2.江南大學(xué) 機械工程學(xué)院 江蘇省食品先進制造裝備技術(shù)重點實驗室，江蘇 無錫 214122；3.中國航天科工集團8511研究所，南京 210007)

針對孔群加工路徑優(yōu)化中遺傳算法存在的局部最優(yōu)和收斂速度慢等問題，提出采用模擬退火算法改進遺傳算法進行路徑優(yōu)化。首先根據(jù)孔群數(shù)控加工的特點建立數(shù)學(xué)模型，采用遺傳算法設(shè)計種群編碼，建立適應(yīng)度函數(shù)選擇優(yōu)秀種群，并對保留的優(yōu)秀種群進行交叉、變異等操作，實現(xiàn)種群進化，其次引入模擬退火算法對其適應(yīng)度函數(shù)進行拉伸處理，調(diào)整種群進化差異性而加速尋優(yōu)進度，同時采用改進的Metropolis準則調(diào)整接受概率，調(diào)節(jié)舊種群和新種群的進化程度，增強遺傳算法的全局搜索能力。實例表明：改進算法用于某模具的孔群加工，有效克服遺傳算法的早熟現(xiàn)象，縮短收斂次數(shù)，平均路徑縮短比例達6.9%，提高了加工效率，效果良好。

孔群加工；改進遺傳算法；模擬退火算法；Metropolis準則

0 引言

在孔群的數(shù)控加工中，孔群加工路徑的優(yōu)化設(shè)計，有利于縮短刀具空行程距離，提高加工效率和設(shè)備的使用率[1-2]，因此孔群路徑的優(yōu)化問題成為目前CAM中研究熱點問題[3-4]。目前，在解決工程實際問題時，通常采用插入法[5]、單元劃分法[6]等方法，但隨著孔群加工數(shù)量和規(guī)模日益增大，此類方法計算誤差較大。隨著近年來計算機技術(shù)的不斷發(fā)展，許多學(xué)者將智能算法，如啟發(fā)式算法[7]、蟻群算法和相鄰排序算法[8]、遺傳算法(genetic algorithm，GA)[9]等算法用于解決路徑優(yōu)化問題，取得了一定效果。

遺傳算法借簽生物進化“優(yōu)勝劣汰”的遺傳機制，求解簡單，并行計算能力強，魯棒性強等優(yōu)點，被廣泛地用于較多領(lǐng)域[10]，在孔群的路徑優(yōu)化方面取得了成功的案例[11-12],如文獻[11]重點研究遺傳算法中參數(shù)影響，以尋找合適的參數(shù)進一步縮短孔群加工路徑，但是仍存在迭代慢，甚至迭代難于收斂等問題，文獻[12]采用編碼、交叉和變異等方案，解決迭代中無法收斂等問題，提高優(yōu)化效率，但是遺傳算法優(yōu)化過程中存在容易陷入局部最優(yōu)。針對遺傳算法中容易出現(xiàn)局部最優(yōu)和收斂速度慢等問題，本文通過對遺傳算法中適應(yīng)度函數(shù)與接受概率進行模擬退火處理，實現(xiàn)改進遺傳算法對孔群路徑優(yōu)化處理，獲得全局最優(yōu)解并提高收斂效率。

1 孔群數(shù)控加工路徑模型

孔群數(shù)控加工路徑優(yōu)化問題與典型旅行商問題有相似的地方，即為保證數(shù)控刀具遍歷每個待加工孔，尋找刀具加工的最短路徑；但是也有較大區(qū)別，待加工的孔一般需要多種刀具、加工多道工序完成一個孔的加工：如鉆孔、擴孔、鉸孔、鏜孔等工序，加工過程中需要換刀，對刀等操作，根據(jù)孔群加工的特點，建立孔群加工模型。設(shè)孔群加工模型集合表達式為：

G=(V,E,D)

(1)

F(x)=f(x)+βd(x)

(2)

式中，f(x)為刀具孔間的行程路徑長度，

β為加權(quán)系數(shù)，取β=1.5；

在尋找滿足式(2)最優(yōu)解的前提下，還需要滿足工藝的加工規(guī)律：①先粗加工在精加工；②先光孔加工后螺紋加工等機加工要求。

F(x)為全局孔群加工路徑總長度，優(yōu)化目標是尋找一條最優(yōu)的路徑，使得F(x*)=min{F(x)}。

2 改進遺傳算法的加工路徑優(yōu)化

遺傳算法是通過種群編碼和種群選擇、交叉、變異等操作，生成新后代，在新后代中選擇優(yōu)秀后代作為下一代的種群進行循環(huán)操作，留下最優(yōu)子代作為最優(yōu)解。

2.1 種群編碼

2.2 種群適應(yīng)度函數(shù)

(i≠j)

(3)

適應(yīng)度函數(shù)為遍歷所有孔且回到初始機床參考點的距離倒數(shù)。優(yōu)化目標是選擇適應(yīng)度大的染色體，適應(yīng)度越大，路徑越短，染色體質(zhì)量越好，反之染色體質(zhì)量越差。

2.3 種群選擇、交叉、變異操作

(1)種群的選擇操作

根據(jù)進化論理論，由式(3)計算的染色體適應(yīng)度，選擇適應(yīng)度強的染色體，刪除差的染色體，根據(jù)選中的染色體概率作為其適應(yīng)度占種群里適應(yīng)度總和的比例，根據(jù)比例選擇一定百分比的優(yōu)秀個體進行下面的交叉、變異操作，以保證全局性的優(yōu)化選擇[13]。

(2)種群的交叉操作

對保留的染色體，采用映射雜交方式，確定交叉操作父代，將父代樣本兩兩分成一組，隨機選擇任意位置按照概率px交叉操作。交叉后，如果同個個體染色體之間出現(xiàn)重復(fù)基因，利用部分映射的方法消除重復(fù)基因。假定在[1 10]范圍隨機選擇整數(shù)r1和r2，確定兩個位置，對兩個位置中間數(shù)據(jù)進行交叉操作。假設(shè)r1=3，r2=6，則：

位置：1 2 3 4 5 6 7 8 9 10

交叉操作后，不重復(fù)的數(shù)字保留，重復(fù)的數(shù)字暫時以*代替，并利用中間段對應(yīng)關(guān)系進行映射，消除沖突，結(jié)果為：

(3)種群的變異操作

隨機選擇任意位置按照概率pm變異操作，變異后，產(chǎn)生新染色體。如在[1 10]范圍內(nèi)隨機挑選整數(shù)r1和r2，確定兩個位置，假設(shè)r1=3，r2=6，則：

位置： 1 2 3 4 5 6 7 8 9 10

2.4 改進遺傳算法的種群進化

文獻[11]采用的遺傳算法，通過種群的編碼、選擇、交叉和變異方案，實現(xiàn)了種群的優(yōu)化，但是計算中隨機性較大，對進化程度控制不足，首先，在進化初期，一些個體會因競爭力很強而控制優(yōu)化過程，容易陷入局部最優(yōu)而無法獲得全局最優(yōu)解；其次，在進化后期，由于個體的適應(yīng)度差異慢慢變小，選擇機制可能趨于隨機任意選擇，進化緩慢，難以搜索到全局最優(yōu)解。因此引入模擬退火算法，種群進化中，不僅接受優(yōu)秀種群，而且還以一定概率接收惡化解，從而增強種群的多樣性，使搜索方向回退，跳出局部最優(yōu)陷阱，以尋找全局最優(yōu)解；同時通過模擬固體退火過程(升溫過程、平衡過程、冷卻過程三個階段)的溫度控制，對適應(yīng)度函數(shù)進行退火拉伸處理，以提高全局收斂速度。

(1)適應(yīng)度函數(shù)退火處理

令初始最高溫度Tmax，最低溫度為Tmin，降溫函數(shù)采用衰減函數(shù)：

Tk+1=αTk(k=0,1,2,…)

(4)

式中,α為降溫系數(shù)，該值為常數(shù)，取0.5～0.99，該值決定了降溫速度。衰減量少時迭代次數(shù)增加，從而搜索更大的解空間，返回更好的解。每個溫度下對應(yīng)的循環(huán)次數(shù)為gmax,當循環(huán)次數(shù)為g。

通過溫度調(diào)整，適應(yīng)度函數(shù)在溫度Tmax高時(遺傳算法初期)，溫度降低較快，計算的各個染色體的適應(yīng)度函數(shù)差別比較小，染色體被復(fù)制的概率也低，避免個別好的染色體充斥全部種群，造成早熟；而隨后溫度以α倍率緩慢降低，目標函數(shù)相近的染色體適應(yīng)度函數(shù)值差異將不斷增大，優(yōu)秀染色體優(yōu)勢更加明顯，防止種群進化停滯不前。通過對適應(yīng)度函數(shù)的拉伸處理，可以解決遺傳算法的早熟和進化停滯等缺陷，提高尋優(yōu)速度。

(2) 接受概率退火處理

若路徑長度函數(shù)為f(d)，當前解的路徑為f(d1)，新解的路徑為f(d2)，路徑差為df=f(d2)-f(d1)，采用Metropolis準則修改種群規(guī)則為：

(5)

①當df<0時，表示新解路徑比當前路徑短，則保存該新個體，即f(dcurrent)=f(d2)；

②當df>0時，表示新解路徑比當前路徑長,則按照概率P1對新個體隨機與其它子染色體位置對換后保存，計算df，當df<0則保存，否則還原成原種群。

③當df=0時，按照概率P2對新個體隨機與其它子染色體位置對換后保存，計算df，當df<0則保存，否則還原成原種群。

2.5 改進遺傳算法的實現(xiàn)

改進遺傳算法需要從大量路徑中尋找一條滿足式(2)的最優(yōu)路徑，流程見圖1所示，其具體步驟如下：

Step1：設(shè)置算法參數(shù)：即設(shè)置種群規(guī)模s，初始溫度Tmax，終止溫度Tmin，降溫系數(shù)α，交叉概率px，變異概率pm，內(nèi)循環(huán)次數(shù)gmax，最優(yōu)染色體pbest；

Step2：設(shè)置當前溫度t=Tmax；

以上案例表明伊匹單抗和曲美木單抗無論是單藥還是聯(lián)合PD-1/PD-L1通路的單克隆抗體帕博利珠單抗和納武利尤單抗，均獲得了較好療效，聯(lián)合治療具有更高的抗瘤效果。但是均出現(xiàn)了少數(shù)心臟不良反應(yīng)，如心肌缺血、心肌纖維化、心律失常、免疫性心肌炎、心肌病及心力衰竭癥狀，可能與免疫相關(guān)性心肌細胞保護缺失有關(guān)，CTLA-4在維持包括心肌在內(nèi)的不同組織起保護性作用，上述小鼠實驗及臨床案例充分證實使用CTLA-4單克隆抗體抑制CTLA-4基因表達，心肌細胞不能得到有效保護，進而出現(xiàn)心肌細胞不同程度的缺血和壞死，而自身免疫性心肌炎及心衰可危及生命。

Step4：設(shè)置當前循環(huán)次數(shù)g=1；

Step5：根據(jù)種群的適應(yīng)度選擇策略，選擇優(yōu)秀染色體種群p；

Step6：對選擇的染色體種群p，按照交叉概率px，變異概率pm操作生成新種群p′；

Step7：對于新種群p′，利用Metropolis準則，選擇是否替換當前種群p；

Step8：令g=g+1,如果g

Step9：令t=αT，如果t>Tmin，轉(zhuǎn)入Step4；否則轉(zhuǎn)入Step10；

Step10：輸出最優(yōu)解pbest及最短路徑f(dbest)。

圖1 改進遺傳算法的孔群路徑優(yōu)化流程圖

3 實例分析

3.1 孔群加工特點

本文以某模具孔群加工為例，見圖2所示，孔的特征及加工方式見表1所示。

圖2 某模具孔群加工布置圖

孔特征尺寸數(shù)量鉆刀1鉆刀2鉆刀3攻絲1攻絲2鉸刀1鍵槽刀1立銑刀1立銑刀2a1M818?2?6M8a2M46?2M4a3?4．564?4．3?4．5a4?1816?12?17．8?18

由圖2和表1可見，該板有4類待加工孔，尺寸分別為M8、M4、φ4.5、φ18,對應(yīng)的孔的數(shù)量分別為18、6、64、16個。首先采用中心鉆孔定位，然后用不同直徑鉆刀鉆孔，最后攻絲、開鍵槽或鉸孔等加工。其中M8與M4均需要鉆刀1φ2加工，加工時為減少換刀次數(shù)可以同時加工。具體的加工工序為中心孔鉆刀1φ2→鉆刀2φ6→攻絲1M8→攻絲2M4→鉆刀3φ4.3→鉸刀1φ4.5→鍵槽刀1φ12→立銑刀1φ17.8→立銑刀2φ18 。刀具均在0處完成換刀，完成各道工序加工。

3.2 路徑優(yōu)化實驗及數(shù)據(jù)分析

改進遺傳算法的參數(shù)設(shè)置為：初始種群規(guī)模s=100，初始溫度Tmax=100℃，終止溫度Tmin=0℃，降溫系數(shù)α=0.99，各溫度下的最大迭代次數(shù)gmax=200，交叉概率px=0.7，變異概率pm=0.01。

為驗證改進遺傳算法的優(yōu)化效果，選擇與遺傳算法[12]，模擬退火算法[14]分別進行路徑優(yōu)化比較。以鉸刀1φ4.5(64個孔)的刀具加工路徑為例，分別進行10次優(yōu)化實驗，優(yōu)化結(jié)果見表2所示。

表2 優(yōu)化實驗路徑長度

由表2中10次路徑優(yōu)化結(jié)果可見，改進遺傳算法在最大路徑，最短路徑和平均路徑都優(yōu)于前兩種算法，其中平均路徑縮短比例分別為6.9%和17.7%，10次路徑優(yōu)化中最短路徑見圖3所示，最短路徑優(yōu)化迭代搜索過程圖見圖4所示。

圖3中三種算法的最短路徑分別為1819.75，1992.38，1808.74，改進遺傳算法相比遺傳算法、模擬退火算法，其路徑縮短了11.01，183.64。

由圖4分別為改進遺傳算法、遺傳算法、模擬退火算法最短路徑的迭代次數(shù)，其迭代次數(shù)分別為：551，591，663次，搜索迭代次數(shù)減少了40次，112次，可見改進遺傳算法以較快的速度獲得全局較優(yōu)解。

(a)遺傳算法最短路徑圖

(b)模擬退火算法最短路徑圖

(c)改進遺傳算法最短路徑圖圖3 三種算法鉆孔最短路徑圖

圖4 三種算法最短路徑迭代搜索過程圖

3.3 實驗數(shù)據(jù)分析

對圖2中其它幾種特征孔進行路徑優(yōu)化，重復(fù)做10次實驗，統(tǒng)計路徑長度見表3所示。

表3 各種孔的優(yōu)化實驗路徑長度

由表2和表3可見，加工6個規(guī)則孔時，三種算法計算結(jié)果一樣，但是隨著孔群的數(shù)量從6個增加到64個孔，相比傳統(tǒng)遺傳算法，平均路徑縮短0.1%(16個孔)，4.0%(24個孔)，6.9%(64個孔)；相比模擬退火算法，平均路徑縮短0.9%(16個孔)，9.1%(24個孔)，17.7%(64個孔)，由此可見孔的數(shù)量越多，排列不規(guī)律時，該算法的優(yōu)勢越明顯。

4 結(jié)論

本文采用改進遺傳算法解決孔群加工路徑優(yōu)化問題。通過對遺傳算法中種群選擇、交叉、變異等操作，并在種群進化過程中引入模擬退火算法的Metropolis準則，調(diào)節(jié)新舊種群的更新，有效改進了傳統(tǒng)遺傳算法早熟、局部搜索能力不強等缺陷，特別是針對數(shù)量多、排列不規(guī)則的孔群加工，優(yōu)化程度更加明顯。

[1] ONWUBOLU G C,CLERC M. Optimal path for automated drilling operations by a new heuristic approach using particle swarm optimization[J]. International Journal of Production Research,2004,42(3):473-491.

[2] HSIEH Y C,LEE Y C,YOU P S. Using an effective immune based evolutionary approach for the optimal operation sequence of hole-making with multiple tools[J]. Journal of Computational Information Systems,2011,77(2)：411-418.

[3] Luong L, Spedding T. An integrated system for process planning and cost estimation in hole making[J]. International Journal of Advanced Manufacturing Technology,1995,10(6):411-415.

[4] 陳琳,劉曉琳,潘海鴻,等. 孔群分類加工路徑的優(yōu)化算法[J]. 制造業(yè)自動化,2013,35(17)：46-49.

[5] 童行行,王凌,何京芮. 旅行商問題基于參考點的相鄰插入法及其改進[J]. 計算機工程與應(yīng)用,2002(20): 63-65.

[6] 趙玉成,袁樹清,許慶余. TSP問題的單元劃分法[J]. 力學(xué)與實踐,1998,20(6):35-36.

[7] 曾議,孫莉,孫友文,等. 啟發(fā)式算法的孔群加工路線模糊多目標優(yōu)化[J]. 現(xiàn)代制造工程. 2016(4)：44-50.

[8] 潘海鴻，劉曉琳，廖小平,等.鈑金激光切割加工CAD/CAM軟件的孔群加工路徑優(yōu)化算法[J].組合機床與自動化加工技術(shù),2013(11):110-113.

[9] 李國聞,張丹,杜海遙,等. 基于遺傳算法的機電產(chǎn)品布線結(jié)構(gòu)優(yōu)化設(shè)計方法[J].中國科技論文,2015, 10 (16):1944-1948.

[10] Li S, Liu Y, Li Y,et al. Process planning optimization for parallel drilling of blind holes using a two phase genetic algorithm[J]. Journal of Intelligent Manufacturing , 2013, 24(4):791-804.

[11] 許兆美,金衛(wèi)鳳,李健.基于遺傳算法的孔群加工路徑優(yōu)化[J]. 機械設(shè)計與制造,2011(2):31-33.

[12] 肖軍民.一種改進遺傳算法在孔群加工路徑中的優(yōu)化[J].組合機床與自動化加工技術(shù),2015(2):151-153.

[13] Li YH,Guo H,Wang L,et al. A hybrid genetic-simulated annealing algorithm for the location-inventory-routing problem considering returns under E-supply chain environment[J]. Scientific World Journal, 2013(11):1653-1656.

[14] 裴小兵,賈定芳. 基于模擬退火算法的城市物流多目標配送車輛路徑優(yōu)化研究[J]. 數(shù)學(xué)的實踐與認識,2016,46(2):105-113.

ResearchonPathOptimizationofHoleGroupMachiningBasedonImprovedGeneticAlgorithm

GONG Yu-ling1，WU Mei-ping2，XU Xiao-dong1，GONG Fei3

(1.School of Shipbuilding & Electromechanical Engineering,Taizhou University, Taizhou Jiangsu 225300, China; 2.Jiangsu Key Laboratory of Advanced Food Manufacturing Equipment & Technology, School of Mechanical Engineering, Jiangnan University, Wuxi Jiangsu 214122, China)

Aiming at the problems of local optimum and slow convergence of genetic algorithm in the optimization of hole group machining path, an improved genetic algorithm based on simulated annealing algorithm is proposed. Firstly, mathematical model is established according to the characteristics of hole group machining, then the encode model of the population is designed based on genetic algorithm, the operations of crossover and mutation of outstanding population retention are implemented by the fitness function to make the population evolve. Secondly, the genetic algorithm is combined with simulated annealing algorithm to draw the fitness function for adjusting the evolution of population differences and accelerating the optimization progress, at the same time the improved Metropolis standards are used to adjust the probability of acceptance and evolution degree of the old and new regulation of population for enhancing the global search ability of genetic algorithm. Examples show that the algorithm has been used in hole group machining of the mould. The improved genetic algorithm compared with traditional genetic algorithm can overcome the prematurity of traditional genetic algorithm effectively, reduce the number of convergence and reduce by more than 6.9% on average path, which has increased of efficiency and has good effect.

hole group machining; improved genetic algorithm; simulated annealing algorithm; Metropolis criterion

1001-2265(2017)11-0052-05

10.13462/j.cnki.mmtamt.2017.11.014

2017-01-07；

2017-02-20

2016年度泰州學(xué)院校級科研課題(TZXY2016YBKT002)；泰州學(xué)院雙語教學(xué)課程建設(shè)項目(泰院教發(fā)[2016]11號)

龔玉玲(1978—)，女，湖北襄陽人，泰州學(xué)院講師，碩士，研究方向為船舶與機電工程技術(shù)，精密加工和檢測的教學(xué)與研究，(E-mail)79043638@qq.com。

TH166;TG659

A

(編輯李秀敏)