基于特征分層拓?fù)渑判蚝透倪M(jìn)蟻群算法的工藝路線研究*

馮 羚，黃海松，姚立國

(貴州大學(xué) 現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴陽 550025)

0 引言

工藝路線是指零件從毛坯到成品狀態(tài)轉(zhuǎn)變中，企業(yè)根據(jù)其材料、結(jié)構(gòu)、設(shè)計(jì)信息等按照一定的最優(yōu)準(zhǔn)則完成的加工過程。由于零件的多樣性、加工設(shè)備的局限性、生產(chǎn)環(huán)境的復(fù)雜性，使得對工藝路線決策較為復(fù)雜。工藝路線是毛坯和成品的連接紐帶，很大程度決定了成品的質(zhì)量和企業(yè)的效益，合理安排工藝路線在產(chǎn)品制造方案中顯得尤為重要。近年來，一些啟發(fā)式的算法常被用來解決工藝路線決策這一類問題。李聰波等[1]以車間高效低碳為目標(biāo)建立機(jī)械加工工藝模型，應(yīng)用遺傳算法對模型求解，并用機(jī)床電動(dòng)機(jī)基座加以驗(yàn)證模型的實(shí)用性。夏然飛等[2]考慮加工中心工件加工時(shí)間最短，采用和聲搜索算法，引入刀具、工作臺轉(zhuǎn)位約束矩陣，對工藝生成方案進(jìn)行求解。范孝良等[3]針對復(fù)雜零件工藝規(guī)劃效率低，質(zhì)量差的問題，采用蝙蝠算法，設(shè)計(jì)蝙蝠編碼解碼策略對工藝路線問題進(jìn)行求解。付曉東等[4]采用基于神經(jīng)網(wǎng)絡(luò)的專家系統(tǒng)，將零件信息轉(zhuǎn)換為特征矩陣作為輸入，自適應(yīng)BP算法訓(xùn)練網(wǎng)絡(luò)模型，得到軸類零件的工藝規(guī)劃。

與這些算法相比，蟻群算法具有正反饋、隨機(jī)性、禁忌搜索等特點(diǎn)，在求解工藝決策問題時(shí)表現(xiàn)良好。文獻(xiàn)[5]以雙螺桿壓縮機(jī)端蓋加工工藝規(guī)劃為目的，用“或”型工藝約束，針對決策問題編制了加工要素選擇模塊，并采用啟發(fā)式要素選擇規(guī)則，改進(jìn)了蟻群算法的結(jié)構(gòu)。Shi Gang Wang等[6]在CAD/CAM集成系統(tǒng)中，對路徑優(yōu)化問題采用蟻群算法與LK算法融合的智能算法，對孔組鉆具工藝路徑進(jìn)行了優(yōu)化，實(shí)現(xiàn)CAD/CAM的多個(gè)特征優(yōu)化。黃風(fēng)立等[7]提出一種禁忌特征動(dòng)態(tài)更新與蟻群算法結(jié)合求解工藝路線的方法，解決方案設(shè)計(jì)中剛性約束問題，并通過實(shí)例驗(yàn)證算法的可行性。常志勇等[8]提出以約束矩陣表征加工元之間的加工順序，建立制造資源目標(biāo)函數(shù)，應(yīng)用自適應(yīng)蟻群算法對工藝路線進(jìn)行求解。上述研究，較多是通過智能算法在約束條件下求解最優(yōu)目標(biāo)函數(shù)問題，但因?yàn)榧s束過多，搜索范圍大，存在效率低，甚至運(yùn)行多次才能得到可行解的問題?；诖?，本文提出了一種基于特征分層拓?fù)渑判蚝透倪M(jìn)蟻群算法的工藝路線優(yōu)化方法，構(gòu)建分層拓?fù)漤樞蚬ば蛟蛄斜碚鞴ば蛟g的加工順序關(guān)系，螞蟻搜索這些拓?fù)湫蛄校s小可行解的范圍，以解決搜索效率和解的可行性等問題。

1 零件特征描述

零件特征是指包含零件一定的結(jié)構(gòu)形狀、加工精度、裝配要求等一系列信息的結(jié)合，是組成零件的基本單元。零件特征一般可以分為以下兩類。①主要特征：構(gòu)建零件幾何拓?fù)浣Y(jié)構(gòu)且無法進(jìn)行二次拆分的特征，例如：平面、孔等。②輔助特征：輔助主要特征的局部特征，可以進(jìn)行二次拆分，例如：螺紋、鍵槽等。

假設(shè)某零件Α一共有m個(gè)特征，則該零件可以表示為：

Α=(φ1,φ2,…φi…,φm)

(1)

式(1)中，φi表示第i個(gè)加工特征，i=1，2，……，m。

φi=(ω1,ω2,…ωj…,ωn)

(2)

式(2)中，ωj表示第j個(gè)工序元，j=1，2，……，n。

在零件加工中，每個(gè)工序元對應(yīng)的加工資源有所不同，加工資源主要指機(jī)床、刀具、夾具等。因此，工序元可以看做一個(gè)加工資源的集合。設(shè)機(jī)床集合為x={x1,x2,…,xo}，刀具集合為y={y1,y2,…,yp}，夾具集合為z={z1,z2,…,zq}，其中o，p，q為加工制造部門機(jī)床、刀具、夾具的總和。對于零件Α，特征φi中的ωj工序元有：

ωj=(xα,yβ,zγ)

(3)

式(3)中xα,yβ,zγ分表表示制造加工工序元ωj所需要的機(jī)床、刀具、夾具。其中1?α?o，1?β?p，1?γ?q。

2 基本問題

2.1 基于特征分層拓?fù)漤樞蚬ば蛟蛄?/h3>

零件在進(jìn)行工藝路線設(shè)計(jì)時(shí)，首先要遵循的工藝準(zhǔn)則[9]如先粗后精、基準(zhǔn)先行、聚類加工以及一些特定的準(zhǔn)則，例如螺紋，一般安排在外圓精車后，粗精磨外圓之前。

零件由特征組成，每一個(gè)特征存在若干串行或并行關(guān)系。圖1所示是由4個(gè)特征組成的工序元順序關(guān)聯(lián)關(guān)系。如特征1，工序元101在前，工序元102在后；特征2，工序元201、203、206，屬于并行關(guān)系。工序元上方C1、C2等代表加工該工序元所需要的加工資源，0表示起點(diǎn)，1表示終點(diǎn)。一個(gè)有向無環(huán)圖是由若干節(jié)點(diǎn)和弧組成的，且不存在閉合回路。對于圖1此有向無環(huán)圖，可以用弧線上的權(quán)值來對工序元節(jié)點(diǎn)進(jìn)行拓?fù)渑判騕10]。定義弧尾工序元的入度為弧頭入度加1，多條弧尾則取最大值。圖1中，工序元205的入度為3，工序元401的入度為5。當(dāng)工序元按照入度值從小到大排列，且相鄰工序元之間入度值小于或等于1的時(shí)候，稱為分層拓?fù)漤樞蚬ば蛟蛄小?/p>

分層拓?fù)湫蛄?(201,203,206,305,301,207,204,202,208,209,401,402)；

分層拓?fù)湫蛄?(203,101,201,301,305,202,207,102,205,209，401,402)；

構(gòu)建特征分層拓?fù)湫蛄?，可以表征工序元先后加工順序，得到的分層拓?fù)湫蛄邪藛栴}所需要的最優(yōu)解。

圖1 特征分層拓?fù)漤樞蛴邢驘o回圖

2.2 加工資源最優(yōu)模型

零件在進(jìn)行工藝路線設(shè)計(jì)時(shí)，其次要遵循加工資源約束。一般而言，企業(yè)在對加工工藝路線進(jìn)行設(shè)計(jì)的時(shí)候，會考慮多方面的問題，例如：加工成本、生產(chǎn)效率、產(chǎn)品質(zhì)量等。需要一個(gè)量化的目標(biāo)函數(shù)，考慮加工資源更換率最低。機(jī)床的更換率降低，加工基準(zhǔn)不需要頻繁更換，減少了因?yàn)榛鶞?zhǔn)更換帶來的誤差，提高了產(chǎn)品的加工精度；刀具的更換率降低，減少了換刀次數(shù)，生產(chǎn)效率得到提高；夾具的更換率降低，減少了裝夾誤差和裝夾次數(shù)，質(zhì)量得到保證。定義工序元i到工序元j之間的加工資源(機(jī)床、刀具、夾具)更換率為Cij。

Cij=λ1Eij+λ2Fij+λ3Gij

(5)

其中，λ1、λ2、λ3分別為機(jī)床、刀具、夾具的更換率加權(quán)系數(shù)，Eij、Fij、Gij分別為從工序元i到工序元j機(jī)床、刀具、夾具的更換次數(shù)。

(6)

(7)

(8)

3 工藝路線優(yōu)化

3.1 基于改進(jìn)蟻群算法工藝路線設(shè)計(jì)

本文采用雙層蟻群算法來求解工藝路線設(shè)計(jì)中多約束問題，流程如圖2所示。將求解過程劃分為兩個(gè)過程：一層蟻群算法從工序元中按加工順序得到初始信息素濃度，二層蟻群算法按選擇概率函數(shù)和初始信息素濃度找到工序元特征分層拓?fù)渑判蛐蛄?，在上述工序元序列中找到滿足加工資源更換值最小的序列。期望值是根據(jù)企業(yè)現(xiàn)有的加工資源更換效率而定。

圖2 工藝路線設(shè)計(jì)流程圖

(1)為了將該方法描述清楚，以圖1中的特征1、特征2、特征4為例。特征1所代表的的是端面，101102代表粗車精車；特征2所代表的是軸，201202代表粗車精車，203204205代表粗車精車粗磨，206207208209代表粗車精車粗磨精磨；特征4所代表的是槽，401402代表粗銑精銑，每個(gè)工序元對應(yīng)的加工資源C1、C2、……有所不同。首先考慮加工順序，先粗后精，聚類加工。一般蟻群算法用于求解優(yōu)化問題的時(shí)候，初始信息素濃度定義各個(gè)單元相同。改進(jìn)的蟻群算法，通過一層蟻群算法信息素更新，使得第二層蟻群算法的初始信息素濃度改變，并且和工序元之間加工順序有關(guān)，一層蟻群算法信息素更新后，入度相同的特征元之間信息素濃度高于其他，如101、201、203、206之間入度均為1，信息素濃度肯定大于它們和其他工序元濃度。

(2)一層蟻群搜索使得滿足分層拓?fù)漤樞虻墓ば蛟畔⑺貪舛仍黾?，螞蟻在啟?dòng)二層蟻群搜索的時(shí)候優(yōu)先選擇和自己入度相同或相近的工序元。隨機(jī)選擇起點(diǎn)工序元，這些序列都滿足按入度從小到大排列規(guī)則，如圖3所示，其對應(yīng)的加工資源如表1。螞蟻在啟動(dòng)二層蟻群搜索的時(shí)候，螞蟻在這些序列中搜索滿足加工資源更換最小的序列。

圖3 入度排列關(guān)聯(lián)圖

工序元加工資源101、201、206C1102、204、207C2202C3203C4205、208M1209M2401X1402X2

3.2 改進(jìn)的信息素更新規(guī)則

信息素更新采用蟻周系統(tǒng)，其具有隨機(jī)性能保證全局搜索，更新規(guī)則如下：

一層蟻群搜索公式(13)～式(15)：

(13)

(14)

Ltabu=min(Cij，i，j=1，2…n)

(15)

rij為i，j經(jīng)過m只螞蟻后的信息素濃度，rijk為第k只螞蟻在i，j邊留下的信息素濃度，Q為信息素一個(gè)常量，Ltabu_s為禁忌列表中前s個(gè)工序元對應(yīng)入度的大小，s為拓?fù)渑判蛑腥攵葹?的工序元個(gè)數(shù)，Lrudu_s是為了保證在第二層蟻群搜索中，隨機(jī)選擇起點(diǎn)加工元中入度為1的能排在前面。

二層蟻群搜索公式(16)～式(18)：

rie jf′(t+n)=ρrie jf′(t)+Δrie jf′

(16)

(17)

(18)

rie jf′(t+n)為經(jīng)過n次迭代i，j加工資源更換路徑上的信息素，Δrie jf′為p只螞蟻經(jīng)過后留在ie，jf路徑上的信息素，Ltabu′為加工資源禁忌列表里面，螞蟻完成一次遍歷后得到的加工資源更換率。

4 仿真與分析

4.1 算法性能測試

為了驗(yàn)證本算法的性能，采用經(jīng)典文獻(xiàn)中的數(shù)據(jù)為樣本，并與文獻(xiàn)中的結(jié)果進(jìn)行對比。數(shù)據(jù)來自于文獻(xiàn)[8]，共有40個(gè)工序元，采用本算法得到加工路線如表2所示。

通過表2看出機(jī)床更換3次，刀具更換7次，夾具更換10次，Cmin=5.7，結(jié)果與文獻(xiàn)得到的結(jié)果相差不大。圖4為測試兩例算法收斂情況，本文算法對特征包含的工序元進(jìn)行分層拓?fù)渑判?，縮小螞蟻搜索范圍，在較短的時(shí)間內(nèi)達(dá)到收斂，在收斂情況方面略優(yōu)于文獻(xiàn)[8]算法。

圖4 算法收斂情況對比

序號加工內(nèi)容位置加工資源更換加工資源次數(shù)機(jī)床刀具夾具1粗車5、6、8、92y2 t1 f1———2粗車1、2、3、48y2 t1 f113精車18y2 t2 f114精車92y2 t2 f115鉆9-12y2 t5 f116鉆1-18y2 t5 f117半精車2、3、4、2-18y2 t2 f2118半精車5、6、7、8、8-12y2 t2 f219粗磨5、6、7、8、5-1、6-1、7-12y5 t3 f311110粗磨2、3、4、2-2、3-18y5 t3 f3111精磨2、48y5 t4 f3112精磨6、7、82y5 t4 f3113銑鍵槽6-22、8y6 t1 f411114滾齒4-16y7 t8 f5111

表3 減速器傳動(dòng)軸特征屬性表

4.2 實(shí)例仿真

以某企業(yè)生產(chǎn)的減速器傳動(dòng)軸為例，如圖5所示，對該軸的特征進(jìn)行分析，得到特征屬性表3；該企業(yè)可用機(jī)床、刀具、夾具等可用加工資源信息如表4所示。

對該傳動(dòng)軸49工序元進(jìn)行分層拓?fù)渑判?，如圖6所示。算法參數(shù)設(shè)置如下：蟻群個(gè)數(shù)m=49，α=1，β=5，ρ=0.95，企業(yè)期望加工資源最小更換率ε=70%。通過算法求解，機(jī)床更換2次，刀具更換8次，夾具更換14次，得到工序元最佳加工順序如圖7所示，加工資源更換率為(0.55×2+0.15×8+0.3×14)×100%=65%，滿足企業(yè)要求。

圖5 某企業(yè)減速器傳動(dòng)軸設(shè)計(jì)圖

工序元刀具機(jī)床類型ω3、ω7、ω11、ω14、ω17、ω25、ω29、ω36、ω40、ω4590°車刀1CA6136、CA6140ω2、ω6、ω10、ω13、ω16、ω24、ω28、ω35、ω39、ω4590°車刀2CA6136、CA6140ω5、ω23、ω32、ω3445°車刀1CA6136、CA6140ω4、ω22、ω31、ω3345°車刀2CA6136、CA6140ω8、ω12、ω15、ω18、ω26、ω30、ω37、ω41粗磨砂輪M1320-520ω9、ω19、ω27、ω38、ω42精磨砂輪M1432Aω1、ω44平頭銑刀X62W、X6030ω20、ω21、ω43、ω44鍵槽銑刀X62Wω1、ω47麻花鉆CA6136、CA6140

圖6 傳動(dòng)軸工序元有向無環(huán)圖

圖7 傳動(dòng)軸加工路線

5 結(jié)束語

本文以特征為起點(diǎn)劃分工序元滿足了加工準(zhǔn)則中“聚類加工”即相同的基準(zhǔn)、特征上的加工元期望能排在一起加工。工序元按入度從小到大排序滿足了加工準(zhǔn)則中“先粗后精”的要求。定義了加工資源最優(yōu)模型，通過對兩層信息數(shù)更新規(guī)則的改進(jìn)，提高了算法的效率和解的可行性。實(shí)驗(yàn)結(jié)果表明，文中提出的算法能很好的在加工準(zhǔn)則約束和目標(biāo)函數(shù)約束下求解，得到滿足企業(yè)所期望達(dá)到的效果。