遺傳算法在箱體零件CAPP數(shù)控加工工步排序決策中的應(yīng)用研究

劉曉陽，劉恩福，方憶湘，李宗斌

LIU Xiao-yang1, LIU En-fu1, FANG Yi-xiang1, LI Zong-bin2

（1.河北科技大學(xué) 機(jī)械電子工程學(xué)院，石家莊 050024；2.西安交通大學(xué) 制造系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，西安 710049）

0 引言

機(jī)械制造中，箱體零件由于品種多樣、結(jié)構(gòu)復(fù)雜、生產(chǎn)狀態(tài)模糊和生產(chǎn)環(huán)境復(fù)雜，使得工序工步排序變成為極其復(fù)雜的決策過程。在現(xiàn)代數(shù)控加工中，一般工序數(shù)目較少，而一個工序內(nèi)工步數(shù)目較多，此時工步排序則變得更復(fù)雜、更詳細(xì)。本文使用遺傳算法解決了CAPP中加工工步的優(yōu)化排序，在文獻(xiàn)[4]的基礎(chǔ)上，目標(biāo)函數(shù)由換刀時間、工作臺轉(zhuǎn)位時間和刀具在三個坐標(biāo)軸方向快速移動到加工區(qū)域所需要的時間組成。并利用多色集合理論將工步排序的約束規(guī)則以圍道布爾矩陣的形式存儲，根據(jù)不同的加工對象，通過添加約束規(guī)則確保工步之間的約束順序。

1 工步排序的數(shù)學(xué)模型

工步排序的數(shù)學(xué)模型可描述為[4]：

設(shè)S={s1,s2,…,sn}是某工件在加工中心上一次裝夾的n(n>1)個加工工步的集合，S有n個元素， 所以存在n！種工步順序，這n個工步構(gòu)成某一種工序順序x={o1,o2,…,on}。通過進(jìn)行優(yōu)化找一個最優(yōu)的順序x*，能夠滿足要求的約束規(guī)則，并且使換刀、工作臺轉(zhuǎn)位的輔助時間和刀具在三個坐標(biāo)軸方向快速移動到加工區(qū)域所需要的時間最短。因此，目標(biāo)函數(shù)f(x)由三部分組成：

每次換刀時間為tT，若順序x中工步ai使用的刀具為Di，則順序x的換刀時間f1(x)：

式中g(shù)(*)的取值如式(3)：

工作臺轉(zhuǎn)位90°需要的時間為t'i，若順序x中相鄰工步i和i+1之間工作臺轉(zhuǎn)過角度Ai，則順序x的工作臺轉(zhuǎn)位時間f2(x)：

假設(shè)從工步oi到oi+1，刀具在3個坐標(biāo)軸方向快速移動到加工區(qū)域所需要的時間ti,i+1，刀具快速移動的時間與刀具移動的距離有關(guān)，f3(x)可以表示為：

優(yōu)化目標(biāo)是尋找一種最優(yōu)的工步順序x*，使

2 加工中心上工步排序問題的約束模型

2.1 建立關(guān)系模型

多色集合理論（Theory of polychromatic Sets，TPS）[4,5]是俄羅斯的Pavlov V.V.教授于1995年提出的。它是一種新的信息處理工具。利用多色集合理論建立零件特征、工步排序的約束規(guī)則與加工工步、面孔屬性之間的關(guān)系模型，如圖1所示；零件特征與工步排序的約束規(guī)則之間的關(guān)系模型，如圖2所示。前者把工步排序中的各個工步、面孔屬性作為多色集合的設(shè)計元素，將加工零件特征和需要添加的約束規(guī)則作為多色集合的統(tǒng)一顏色，后者將工步排序的約束規(guī)則作為多色集合設(shè)計元素，將加工零件特征作為多色集合的統(tǒng)一顏色，建立了工步排序過程的網(wǎng)絡(luò)數(shù)學(xué)模型，形成圍道組成矩陣[A×F(A)]和[F(Ai)×F(Aj)]。

圖1 圍道組成矩陣[A×F(A)]

圖2 圍道組成矩陣[F(Ai)×F(Aj)]

假設(shè)一條加工路線由9個加工工步組成，分別是a1,…,ai,…,a9，面孔屬性分別表示為b1 和b2，集合A數(shù)學(xué)表達(dá)式為：A=(a1,…,ai,…,a9,b1,b2)。

顏色集合F(A)由零件特征和添加的約束規(guī)則組成，假設(shè)某零件由有編號為1～20的特征，每個特征的加工工步鏈如下：通孔1、2、5、8、11、16、19：粗鏜—精鏜；平面4、7、10、13、15、17：粗銑—精銑；螺紋孔系3、6、9、12、14 、18、20：鉆。

在圖1中表示成ai和Fj對應(yīng)的單元格中為“●”就表示了顏色Fj（A）和元素ai的顏色Fj（ai）?？刹檎?到具有“相鄰約束”的工步類型并以表1的形式彼此之間可能存在約束關(guān)系。

表1 具有“相鄰約束”的工步類型之間的約束關(guān)系

表1中●表示豎列和橫列的工步類型之間存在關(guān)聯(lián)，對應(yīng)的橫列的工步類型在前，豎列的工步類型在后。在表1中可以看到a1和a2之間存在“相鄰約束”關(guān)系；在表中a5和a7也含有“相鄰約束”關(guān)系，但只存在a5a7，并且a5和a7有先后的約束要求，也就說在加工過程中存在工步類型a5要先于a7進(jìn)行加工。

在圖2中， F21、F22、F23表示成工步關(guān)聯(lián)關(guān)系分別為oioj、om^on和(ol,ok)。 oioj表示oi和oj在工步排序中相鄰，om^on表示om和on不相鄰，(ol,ok)表示ol排在ok的前面，ol和ok不相鄰約束。

2.2 基于關(guān)系模型獲得相關(guān)聯(lián)的工步

通過上面建立的關(guān)系模型，找到彼此之間相關(guān)聯(lián)的工步并以布爾矩陣的形式進(jìn)行存儲，過程如下：

1）通過圖2找到約束要求Fj對應(yīng)的特征Fi。

2）通過如圖1所示布爾矩陣找到約束要求Fj對應(yīng)的工步類型ai。

3）通過Fi和ai可以找到工步oi，oi即為含有約束要求Fi的工步，同樣可以找到與oi相關(guān)聯(lián)的工步oj。

3 利用遺傳算法進(jìn)行工步排序

3.1 通過編碼產(chǎn)生初始種群

編碼采用實(shí)數(shù)編碼的方式，通過編碼產(chǎn)生初始種群。設(shè)有n個工步，則基因值為在1～n之間隨機(jī)取值，且每個基因值不同。假設(shè)有u個特征，v種加工方法，w種約束規(guī)則。將類似圖1的數(shù)據(jù)存入二維數(shù)組a[v][u+w]中，具體編碼過程如圖3所示。

圖3 編碼產(chǎn)生初始種群的流程圖

按照圖3進(jìn)行編碼得到的染色體都滿足先粗后精、先面后孔的約束條件，每一條染色體代表一個合理的加工順序。

3.2 交叉操作

設(shè)需要進(jìn)行交叉操作的兩個父代個體為A1、A2，它們交叉之后產(chǎn)生的子代個體為B。隨機(jī)產(chǎn)生兩個交叉位置e1、e2，設(shè)e1

交叉操作是GA產(chǎn)生新個體的主要方法，所以交叉概率一般應(yīng)取較大值。但若取值過大又會破壞群體中的優(yōu)良模式；若取值多小，產(chǎn)生新個體的速度又較慢。一般建議的取值范圍是0.4～0.99。

3.3 變異操作

變異操作采用啟發(fā)式互換式變異，即隨機(jī)選取一個基因位置，判斷該位置的基因能不能與前面或者后面的基因值互換，判斷過程中需要利用約束模型。

變異概率是增加種群多樣性的重要因素，太小則不會產(chǎn)生新個體，太大則使遺傳算法成為隨機(jī)搜索。由于本算法的變異操作具有非強(qiáng)制性，而是滿足相應(yīng)的條件才執(zhí)行，所以變異概率不宜取太小，在0.2～0.9之間為宜。工步數(shù)目較少時，交叉概率和變異概率取較大值；反之，取較小值。

4 實(shí)例

圖4是一個箱體類零件，基于建立的關(guān)系模型利用遺傳算法對箱體零件的加工工步進(jìn)行排序。該箱體零件需要加工20個特征，主要是孔系的加工，方位面分為后面、左面、前面、右面和頂面。

進(jìn)行工步排序前，首先添加約束規(guī)則和參數(shù)的設(shè)置。獲得零件特征所在方位面及對應(yīng)的加工工步，進(jìn)行約束規(guī)則的添加，獲得添加約束的工步。取遺傳算法運(yùn)行參數(shù)的群體大小為101，交叉概率為0.75，變異概率0.85，最大進(jìn)化代數(shù)為120。每次換刀時間為5秒，工作臺轉(zhuǎn)位90°所需時間為2秒，可通過工步排序取得最優(yōu)解。所得結(jié)果滿足工步排序受到的條件約束，即先粗后精、先面后孔，且能較快地得到較優(yōu)的排序結(jié)果，能夠較大程度地實(shí)現(xiàn)方位集中和刀具集中。

圖4 箱體零件模型

5 結(jié)論

本文主要解決數(shù)控加工中心上箱體零件一次裝夾下的工步排序優(yōu)化問題。利用多色集合理論建立了加工中心上工步排序問題的約束模型，在進(jìn)行工步排序過程中，能夠根據(jù)零件的實(shí)際的加工要求靈活的添加約束規(guī)則，利用上述遺傳算法尋求工步順序的近優(yōu)方案。本文所提出的方法同樣可以解決其它零件工藝路線的決策問題。

[1] 蒲建,王先逵,吳丹.工藝規(guī)劃中的組合優(yōu)化問題[J].清華大學(xué)學(xué)報,1997,37(8)：69-71.

[2] 秦寶榮,王寧生.基于遺傳算法的加工中心工步排序優(yōu)化方法[J].中國機(jī)械工程,2002,13(18)：1531-1533.

[3] 秦寶榮,柯文,王寧生.基于遺傳算法的箱體零件加工路線決策方法研究[J].中國機(jī)械工程,2002,13(24)：2071-2075.

[4] 郝建波,李宗斌,趙麗萍.加工中心上工步排序問題的約束模型及其遺傳算法求解[J].西安交通大學(xué)學(xué)報,2008,7(7)：860-864.

[5] 李宗斌.先進(jìn)制造中多色集合理論的研究及應(yīng)[M].北京：中國水利水電出版社,2005.