謝書童 郭隱彪

廈門大學(xué),廈門,361005

0 引言

數(shù)控加工的主要目的是節(jié)約加工成本、提高加工效率、提高工件加工質(zhì)量。在給定加工約束條件下,如何選擇最優(yōu)加工參數(shù)(集)來(lái)達(dá)到節(jié)約加工成本目的(即帶約束的最小化問(wèn)題),是一個(gè)具有重要實(shí)際意義的研究課題。以往對(duì)加工參數(shù)的優(yōu)化通常采用傳統(tǒng)的數(shù)學(xué)處理方法(如動(dòng)態(tài)規(guī)劃、線性或非線性規(guī)劃算法)尋求問(wèn)題的最優(yōu)解[1],然而大量的加工參數(shù)優(yōu)化問(wèn)題是多約束非線性的復(fù)雜問(wèn)題,利用這些方法很難取得最優(yōu)解。另外,隨著現(xiàn)代啟發(fā)性算法(meta—heuristic algorithm)的迅速發(fā)展和廣泛應(yīng)用,不少學(xué)者將其應(yīng)用在機(jī)械領(lǐng)域的加工參數(shù)優(yōu)化問(wèn)題中,利用它們搜索問(wèn)題的次優(yōu)解。文獻(xiàn)[2-3]運(yùn)用蟻群算法(ACO)解決車削參數(shù)優(yōu)化問(wèn)題,文獻(xiàn)[4]則采用粒子群算法(PSO)來(lái)解決同樣的問(wèn)題,文獻(xiàn)[5-7]先后使用改進(jìn)的遺傳算法(GA)來(lái)實(shí)現(xiàn)車削參數(shù)的優(yōu)化選擇。模擬退火算法(SA)在文獻(xiàn)[8]中也被用來(lái)解決同樣的優(yōu)化問(wèn)題。但是每種啟發(fā)性算法都有各自的局限性,遺傳算法使用交叉算子和變異算子對(duì)種群中的個(gè)體進(jìn)行隨機(jī)的交叉和變異來(lái)產(chǎn)生下一代,這種做法帶有一定的盲目性,會(huì)破壞個(gè)體中的優(yōu)秀基因,導(dǎo)致算法收斂于局部最優(yōu)解。同時(shí),遺傳算法、粒子群算法、蟻群算法等基于種群的進(jìn)化算法在解決復(fù)雜優(yōu)化問(wèn)題時(shí)是通過(guò)種群中的每一個(gè)個(gè)體的進(jìn)化(即所求問(wèn)題的解的迭代)來(lái)實(shí)現(xiàn)的,它們側(cè)重于從“微觀”層面對(duì)問(wèn)題進(jìn)行數(shù)學(xué)建模。而分布估計(jì)算法(estimation of distribution algorithms,EDAs)[9-12]中沒(méi)有傳統(tǒng)的交叉和變異等操作,取而代之的是通過(guò)一個(gè)概率模型來(lái)描述種群所表示的解的分布,采用統(tǒng)計(jì)學(xué)習(xí)手段從群體“宏觀”的角度對(duì)問(wèn)題進(jìn)行數(shù)學(xué)建模,所以分布估計(jì)算法是一種把進(jìn)化算法和統(tǒng)計(jì)學(xué)習(xí)有機(jī)結(jié)合的全新進(jìn)化算法。此外,分布估計(jì)算法還通過(guò)概率模型來(lái)描述變量之間的關(guān)系,從而能有效地解決非線性、變量耦合的優(yōu)化問(wèn)題。本文采用基于分布估計(jì)算法的優(yōu)化方法來(lái)解決多道車削加工參數(shù)的優(yōu)化問(wèn)題,實(shí)現(xiàn)最小化加工成本的目標(biāo)。

1 車削參數(shù)優(yōu)化問(wèn)題的數(shù)學(xué)模型

對(duì)于多道車削加工參數(shù)優(yōu)化問(wèn)題,因?yàn)槲墨I(xiàn)[8]提出的數(shù)學(xué)模型考慮了大量的實(shí)際加工約束條件,更接近實(shí)際加工,因此本文采用該數(shù)學(xué)模型。待優(yōu)化的車削參數(shù)組合包括粗切削速度vr、粗進(jìn)給量 fr、粗車量(粗車深度)dr、精切削速度vs、精進(jìn)給量 fs和精車量(精車深度)ds。(單個(gè))工件加工成本CU主要由4個(gè)部分組成,即實(shí)際切削過(guò)程中的加工成本CM、工件裝卸操作和刀具空走所用成本CI、換刀操作成本CR、刀具磨損成本CT,所以

式中,k0為單位時(shí)間的工人成本和管理成本之和,美元/min;D、L分別為工件的直徑和長(zhǎng)度,mm;dt為車削總余量,mm;h1、h2分別為與車刀空走時(shí)間和進(jìn)刀/退刀時(shí)間有關(guān)的常量;tc、te分別為工件裝卸的時(shí)間、換刀時(shí)間,min;TP為刀具(粗、精)權(quán)重壽命,min;kt為刀具成本,美元/edge。

粗車次數(shù)為

本文研究的目標(biāo)是在約20個(gè)接近實(shí)際加工的粗精車削約束條件下,最小化CU(vr,vs,fr,fs,dr,ds,n)。約束條件包括[7-8]:①vr、vs、fr、fs、dr、ds的上下限約束;②刀具壽命約束;③切削力、切削功率和表面粗糙度約束;④穩(wěn)定切削面積約束以及切屑和刀具接觸面溫度約束;⑤粗車參數(shù)和精車參數(shù)的相關(guān)性約束。

2 算法

分布估計(jì)算法是一種新興的基于種群的進(jìn)化算法[9-11],其基本思想是將輸入變量xi看作一個(gè)隨機(jī)變量,所有的輸入變量構(gòu)成一個(gè)隨機(jī)矢量x=(x1,x2,…,xk),這時(shí)一個(gè)個(gè)體就是該隨機(jī)矢量的一個(gè)取值,而一個(gè)群體就對(duì)應(yīng)于隨機(jī)矢量的一個(gè)分布。利用聯(lián)合概率分布捕捉變量之間的依賴關(guān)系,并在此概率分布上進(jìn)行采樣以得到更優(yōu)的群體[10—12]。分布估計(jì)算法中有多種概率模型,如單變量、雙變量、多變量(三個(gè)或三個(gè)以上)相關(guān),本文采用單變量模型來(lái)估計(jì)種群分布,這種算法稱為單變量邊緣分布算法(univariate marginal distribution algorithm,UMDA)[10]。算法中隨機(jī)矢量的聯(lián)合概率分布為單個(gè)隨機(jī)變量的概率分布乘積:

式中,l為種群代數(shù);k為問(wèn)題維數(shù)(待優(yōu)化的變量個(gè)數(shù));N為種群大小;Popl為優(yōu)秀子種群。

2.1 概率矢量和算法框架

概率分布矢量PV由待優(yōu)化變量 ——粗切削速度vr、粗進(jìn)給量 fr、精切削速度vs、精進(jìn)給量 fs和精車量ds依次相連而成,每個(gè)變量用20位二進(jìn)制表示,共100位。概率分布矢量PV以每一位的值為0.5來(lái)初始化。此外,待優(yōu)化變量dr可由ds與式(1)通過(guò)遍歷算法算出。

本文提出兩個(gè)基于UMDA的算法,一個(gè)是基于基因修復(fù)策略的邊緣分布估計(jì)算法(UMDArp),該算法具有基因修復(fù)和懲罰函數(shù)兩種約束條件處理方法,其基本流程如圖1所示,主要步聚如下:

(1)使用概率矢量PV(0.5,0.5,…,0.5),采樣產(chǎn)生N個(gè)個(gè)體的初始種群,并計(jì)算每個(gè)個(gè)體的適應(yīng)值。

(2)選出適應(yīng)值最高的M個(gè)個(gè)體,作為優(yōu)秀子種群。

(3)根據(jù)選出的M個(gè)個(gè)體,估計(jì)出新的概率分布PV,然后利用概率分布PV,采樣產(chǎn)生新一代的N個(gè)個(gè)體。

(4)判斷迭代數(shù)gen是否超過(guò)最大代數(shù)的一半(MaxGen/2),若超過(guò),就啟用基因修復(fù)功能,加快算法后期的收斂。

(5)計(jì)算每個(gè)個(gè)體的適應(yīng)值,迭代數(shù)加1。

(6)判斷算法是否達(dá)到最大迭代數(shù)MaxGen,若是,輸出優(yōu)化種群;否則轉(zhuǎn)(2)進(jìn)入迭代。

另一個(gè)算法是只有懲罰函數(shù)的無(wú)基因修復(fù)策略的邊緣估計(jì)算法(UMDAp),其算法框架與UMDArp基本一致,只是沒(méi)有基因修復(fù)功能。

2.2 約束條件處理

2.2.1 懲罰函數(shù)

針對(duì)模型中的約束條件,采用懲罰函數(shù)對(duì)違反約束條件的個(gè)體進(jìn)行懲罰,即把不滿足約束的個(gè)體的適應(yīng)值降低。破壞不同的約束條件,施以不同程度的懲罰,懲罰函數(shù)如下:

由于是最小化問(wèn)題,所以加工成本函數(shù)CU(X)值越小,賦以越大的適應(yīng)值,適應(yīng)值函數(shù)可表示為

UMDAp算法采用式(2)進(jìn)行懲罰,而UMDArp算法則不用其中約束條件n=(dt—ds)/dr的懲罰,用基因修復(fù)策略代替,其他約束懲罰與UMDAp相同。

2.2.2 基因修復(fù)

在采樣產(chǎn)生新一代種群時(shí),不少個(gè)體基因中的精車量ds雖然滿足其上下限,但是會(huì)導(dǎo)致粗車次數(shù)n不為整數(shù),或者粗車量dr超過(guò)可行上限,產(chǎn)生了非法解。解決這三個(gè)變量相互約束的方法除了上述的懲罰函數(shù),本文提出了基因修復(fù)策略,對(duì)個(gè)體中的不良基因精車量ds進(jìn)行修復(fù),即重新調(diào)整精車量ds,使其同時(shí)滿足三者之間約束條件。例如,在后繼的算例中,精車量 ds∈[1,3],隨著種群的進(jìn)化,會(huì)產(chǎn)生基因中的ds落在(2,3)范圍內(nèi)的個(gè)體,假定其值為2.4。此時(shí),dt=6,dr∈[1,3]。那么n=(dt—ds)/dr=3.6/dr,若要滿足這個(gè)方程的話,要么使dr=3.6,但dr超過(guò)可行上限;要么使n不為整數(shù),這又破壞了粗車次數(shù)為整的約束,產(chǎn)生不可行解。若此時(shí)對(duì)這不良基因進(jìn)行修復(fù),把ds(2.4)修改成[1,2]內(nèi)的隨機(jī)數(shù),則此個(gè)體很可能變成可行解,甚至變成優(yōu)化解。這有助于解決可行解較稀疏的多約束問(wèn)題,是懲罰函數(shù)做不到的。因?yàn)榇周嚧螖?shù)n是一個(gè)小整數(shù),所以調(diào)整dt、ds和n三個(gè)變量同時(shí)滿足約束難度不大,這也是采用基因修復(fù)的一個(gè)原因?；蛐迯?fù)和懲罰函數(shù)相結(jié)合的約束處理方案使得 UMDArp算法取得成功。此外,文獻(xiàn)[2,5]算法正是因?yàn)闆](méi)有考慮ds的正確取值,故而出現(xiàn)了粗車次數(shù)不為整數(shù)的偏差結(jié)果,后來(lái)分別由文獻(xiàn)[3,6]對(duì)其進(jìn)行了修正。

3 模擬實(shí)驗(yàn)

UMDArp和UMDAp算法用MAT LAB實(shí)現(xiàn),參數(shù)設(shè)定如下:種群大小為2000、迭代數(shù)為50、截?cái)噙x取率為0.9。測(cè)試其性能的加工例子來(lái)自于文獻(xiàn)[7-8],如表1所示,其中一些變量的含義也可參見(jiàn)文獻(xiàn)[7-8]。兩個(gè)算法均在Windows平臺(tái)(CPU為 PⅣ2.0GHz、內(nèi)存為1GB)上運(yùn)行1000次,取平均值。并與以往提出的算法SA/PS[8]、FE —GA[6]、GA[7]、ACO[7]和 PSO[4]的結(jié)果進(jìn)行了比較,如表2所示。

表1 車削實(shí)例的條件參數(shù)[7-8]

表2 不同算法的結(jié)果比較

從表2的加工成本CU的平均值來(lái)看,由本文UMDArp算法得到的結(jié)果比采用遺傳算法GA[7]得到的結(jié)果節(jié)約了5.6%的加工成本,比采用FE—GA[6]、SA/PS[8]、PSO[4]和 ACO[7]等算法得到的結(jié)果節(jié)約更多。相似地,UMDArp算法也找到了加工成本很低的CU最優(yōu)解2.0784美元,與其他算法找到的最優(yōu)解相比,降低了約0.2美元或0.16美元(每工件)的加工花銷。這均表明UMDArp算法能更有效地解決車削參數(shù)優(yōu)化問(wèn)題。而UMDAp所得的加工成本CU的平均值則不太理想,但還是找到不錯(cuò)的最優(yōu)解。最后,表3列出UMDArp算法找到的部分優(yōu)化解。

表3 UMDArp的部分解

4 結(jié)論

(1)針對(duì)最小化加工成本的車削參數(shù)優(yōu)化問(wèn)題,提出了兩個(gè)基于邊緣分布估計(jì)的UMDArp和UMDAp算法。通過(guò)計(jì)算機(jī)模擬表明,UMDArp算法比以往提出的模擬退火算法(SA)、遺傳算法(GA)、蟻群算法(ACO)和粒子群算法(PSO)具有更強(qiáng)的搜索能力,找到了更優(yōu)的車削參數(shù)集,降低了加工成本。

(2)在約束條件處理方法中,所采用的基因修復(fù)策略和懲罰函數(shù)相結(jié)合的方案優(yōu)于只用懲罰函數(shù)的方案。

此外,只有懲罰函數(shù)的約束處理方法的UMDAp算法也能找到較好的最優(yōu)解。基于邊緣分布估計(jì)的概率模型是分布估計(jì)算法中簡(jiǎn)單的概率模型。因此,采用更復(fù)雜的多變量相關(guān)的貝葉斯網(wǎng)絡(luò)(Bayesian networks)概率模型求解這一問(wèn)題將是我們未來(lái)的研究工作。

[1]Mukherjee I,Ray P K.A Review of Optimization Techniques in M etal Cutting Processes[J].Computers&Industrial Engineering,2006,50(1/2):15-34.

[2]Vijayakumar K,Prabhaharan G,Asokan P,et al.Optimization of M ulti—pass Turning Operations Using Ant Colony System[J].International Journal of Machine Tools&Manufacture,2003,43(15):1633-1639.

[3]Wang Y C.A Note on‘Optimization of Multi—pass Turning Operations Using Ant Colony System'[J].International Journal of Machine Tools&Manufacture,2007,47(12/13):2057-2059.

[4]Srinivas J,Giri R,Yang S H.Optimization of Multi—pass Turning Using Particle Swarm Intelligence[J].International Journal of Advanced Manufacturing Technology,2009,40(1/2):56-66.

[5]Onwubolu G C,Kumalo T.Optimization of Multipass Turning Operations with Genetic Algorithms[J].International Journal of Production Research,2001,39(16):3727-3745.

[6]Chen M C,Chen K Y.Optimization of Multipass Turning Operations with Genetic Algorithms:a Note[J].International Journal of Production Research,2003,41(14):3385-3388.

[7]Sankar R S,Asokan P,Saravanan R,et al.Selection of Machining Parameters for Constrained Machining Problem Using Evolutionary Computation[J].International Journal of Advanced Manufacturing Technology,2007,32(9/10):892-901.

[8]Chen M C,Tsai D M.A Simulated Annealing Approach for Optimization of Multi—pass Turning Operations[J].International Journal of Production Research,1996,34(10):2803-2825.

[9]Muhlenbein H,Paass G.From Recombination of Genes to the Estimation of Distribution Part 1,Binary Parameter[C]//4th International Conference on Parallel Problem Solving from Nature—PPSN IV.Berlin:Springer—Verlag,1996:178-187.

[10]M uhlenbein,H.The Equation for Response to Selection and Its Use for Prediction[J].Evolutionary Computation,1997,5(3):303-346.

[11]Larranaga P,Lozano J A.Estimation of Distribution Algorithms:a New Tool for Evolutionary Computation[M].Boston:Kluwer Academic Publisher,2002.

[12]Lozano J A,Larranaga P,Inza I,et al.Towards a New Evolutionary Computation:Advances in the Estimation of Distribution Algorithms[M].Berlin:Springer—Verlag,2006.