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

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

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

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

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

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

孔群加工；改進(jìn)遺傳算法；模擬退火算法；Metropolis準(zhǔn)則

0 引言

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

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

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

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

G=(V,E,D)

(1)

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

(2)

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

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

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

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

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

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

2.1 種群編碼

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

(i≠j)

(3)

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

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

(1)種群的選擇操作

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

(2)種群的交叉操作

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

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

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

(3)種群的變異操作

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

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

2.4 改進(jìn)遺傳算法的種群進(jìn)化

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

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

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

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

(4)

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

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

(2) 接受概率退火處理

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

(5)

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

②當(dāng)df>0時(shí)，表示新解路徑比當(dāng)前路徑長,則按照概率P1對(duì)新個(gè)體隨機(jī)與其它子染色體位置對(duì)換后保存，計(jì)算df，當(dāng)df<0則保存，否則還原成原種群。

③當(dāng)df=0時(shí)，按照概率P2對(duì)新個(gè)體隨機(jī)與其它子染色體位置對(duì)換后保存，計(jì)算df，當(dāng)df<0則保存，否則還原成原種群。

2.5 改進(jìn)遺傳算法的實(shí)現(xiàn)

改進(jì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è)置當(dāng)前溫度t=Tmax；

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

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

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

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

Step7：對(duì)于新種群p′，利用Metropolis準(zhǔn)則，選擇是否替換當(dāng)前種群p；

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

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

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

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

3 實(shí)例分析

3.1 孔群加工特點(diǎn)

本文以某模具孔群加工為例，見圖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,對(duì)應(yīng)的孔的數(shù)量分別為18、6、64、16個(gè)。首先采用中心鉆孔定位，然后用不同直徑鉆刀鉆孔，最后攻絲、開鍵槽或鉸孔等加工。其中M8與M4均需要鉆刀1φ2加工，加工時(shí)為減少換刀次數(shù)可以同時(shí)加工。具體的加工工序?yàn)橹行目足@刀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í)驗(yàn)及數(shù)據(jù)分析

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

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

表2 優(yōu)化實(shí)驗(yàn)路徑長度

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)數(shù)據(jù)分析

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

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

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

4 結(jié)論

本文采用改進(jìn)遺傳算法解決孔群加工路徑優(yōu)化問題。通過對(duì)遺傳算法中種群選擇、交叉、變異等操作，并在種群進(jìn)化過程中引入模擬退火算法的Metropolis準(zhǔn)則，調(diào)節(jié)新舊種群的更新，有效改進(jìn)了傳統(tǒng)遺傳算法早熟、局部搜索能力不強(qiáng)等缺陷，特別是針對(duì)數(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è)自動(dòng)化,2013,35(17)：46-49.

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

[6] 趙玉成,袁樹清,許慶余. TSP問題的單元?jiǎng)澐址╗J]. 力學(xué)與實(shí)踐,1998,20(6):35-36.

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

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

[9] 李國聞,張丹,杜海遙,等. 基于遺傳算法的機(jī)電產(chǎn)品布線結(jié)構(gòu)優(yōu)化設(shè)計(jì)方法[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]. 機(jī)械設(shè)計(jì)與制造,2011(2):31-33.

[12] 肖軍民.一種改進(jìn)遺傳算法在孔群加工路徑中的優(yōu)化[J].組合機(jī)床與自動(dòng)化加工技術(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] 裴小兵,賈定芳. 基于模擬退火算法的城市物流多目標(biāo)配送車輛路徑優(yōu)化研究[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),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é)院校級(jí)科研課題(TZXY2016YBKT002)；泰州學(xué)院雙語教學(xué)課程建設(shè)項(xiàng)目(泰院教發(fā)[2016]11號(hào))

龔玉玲(1978—)，女，湖北襄陽人，泰州學(xué)院講師，碩士，研究方向?yàn)榇芭c機(jī)電工程技術(shù)，精密加工和檢測(cè)的教學(xué)與研究，(E-mail)79043638@qq.com。

TH166;TG659

A

(編輯李秀敏)