基于遺傳算法的加工工藝規(guī)劃研究

李梅竹

(陜西廣播電視大學(xué)工程管理系， 陜西 西安 710119)

0 引 言

隨著CAD技術(shù)的大量推廣和應(yīng)用以及制造業(yè)信息化工程的推進(jìn)，制造業(yè)中越來越多的企業(yè)迫切地需要借助于CAPP來提高工藝設(shè)計(jì)的效率和水平，建立包括產(chǎn)品工藝信息在內(nèi)的完整的企業(yè)產(chǎn)品信息，以提高自身快速反應(yīng)市場的能力和競爭力.作為設(shè)計(jì)和制造的中間環(huán)節(jié)，CAPP系統(tǒng)的研制和開發(fā)工作并不順利.究其原因，CAPP面臨的困難與工藝設(shè)計(jì)的特點(diǎn)是分不開的[1].

本文致力于工藝規(guī)劃系統(tǒng)的研究，建立了典型加工特征的工藝路線選取規(guī)則，對零件單個(gè)特征進(jìn)行了工藝路線選擇，再運(yùn)用全局優(yōu)化思想，考慮具體加工過程，對整個(gè)零件加工進(jìn)行了工藝規(guī)劃，實(shí)現(xiàn)了工藝排序關(guān)鍵技術(shù).

在本文中應(yīng)用遺傳算法建立了零件加工方案組合優(yōu)化的數(shù)學(xué)模型，并將該方法應(yīng)用到具體零件的工藝排序決策過程中，通過編碼、雜交、復(fù)制、變異等得到了滿足零件要求的最優(yōu)或接近最優(yōu)的工藝路線[2].

1 零件典型特征加工方法

機(jī)械零件的結(jié)構(gòu)形狀是多種多樣的，但它們都是由平面、外圓柱面、內(nèi)圓柱面或曲面、成形面等基本特征組成的.每一種特征都有多種加工方法，具體選擇時(shí)應(yīng)根據(jù)零件的加工精度、表面粗糙度、材料、結(jié)構(gòu)形狀、尺寸及生產(chǎn)類型等因素，選用相應(yīng)的加工方法和加工方案.

進(jìn)行零件工藝規(guī)劃，首先要確定零件主要特征最終工序的加工方法.下面先詳細(xì)介紹一下平面這種典型特征的加工方法的選擇[3-6].

平面的主要加工方法有銑削、刨削、車削、磨削和拉削等，精度要求高的還需要經(jīng)過研磨或刮削加工.常見平面加工方式如下圖1所示，其中尺寸公差等級(jí)是指平行平面之間距離尺寸的公差等級(jí).

2 基于圖的加工方法選擇

圖是一種比線性表和樹更為復(fù)雜的非線性結(jié)構(gòu).在線性結(jié)構(gòu)中，結(jié)點(diǎn)之間存在一對一的線性關(guān)系.在樹形結(jié)構(gòu)中，樹中結(jié)點(diǎn)之間存在著明顯的一對多的層次關(guān)系.而在圖結(jié)構(gòu)中，對結(jié)點(diǎn)(圖中常稱為頂點(diǎn))的前驅(qū)和后繼個(gè)數(shù)都是不加限制的，即任意兩個(gè)結(jié)點(diǎn)之間均有可能相關(guān)，結(jié)點(diǎn)間可以存在多對多的關(guān)系[7,8].

圖1 常見平面的加工方案

由于圖的結(jié)構(gòu)比較復(fù)雜，任意兩個(gè)頂點(diǎn)之間都可能存在聯(lián)系，因此很難用順序存儲(chǔ)結(jié)構(gòu)來存放圖.在實(shí)際應(yīng)用中，是根據(jù)具體的圖來設(shè)計(jì)適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu).常用的存儲(chǔ)方法有兩種：鄰接矩陣表示法和鄰接鏈表表示法[9].鄰接表表示法是使用基本鏈表來鏈接每個(gè)頂點(diǎn)的鄰接頂點(diǎn)的.每個(gè)頂點(diǎn)的結(jié)構(gòu)如圖2所示.

圖2 鄰接表結(jié)點(diǎn)結(jié)構(gòu)

圖1所示的加工方案圖是有向圖，按照圖的存儲(chǔ)結(jié)構(gòu)，把它們分別轉(zhuǎn)化成鄰接表表示形式，見表1.

表1 常見平面加工方案鄰接表

圖 3 VertexInfo類的UML定義 圖4 Digraph類的UML定義

想要存儲(chǔ)這些頂點(diǎn)的信息，就要定義一個(gè)向量v[1]，v[2]，…，v[n]，每個(gè)元素對應(yīng)加工方案圖中的一個(gè)頂點(diǎn).每個(gè)v[i]存儲(chǔ)頂點(diǎn)i中的數(shù)據(jù)以及一個(gè)鏈表包含所有鄰接于頂點(diǎn)i的頂點(diǎn)編號(hào).而對于每個(gè)v[i]將采用一個(gè)類結(jié)構(gòu)來對其定義，相關(guān)定義如下：

class VertexInfo

vector v

其中類VertexInfo用來存儲(chǔ)單個(gè)頂點(diǎn)信息，向量v用來存儲(chǔ)所有頂點(diǎn)信息.對類VertexInfo采用UML建模，如圖3所示.

這樣采用鄰接表表示法的加工方案圖中信息的存儲(chǔ)就轉(zhuǎn)化成用程序?qū)Τ橄蟪鰜淼男畔⒌淖x取，把類VertexInfo實(shí)例化為一個(gè)對象vi，頂點(diǎn)的相關(guān)信息(加工類型、鄰接點(diǎn)、粗糙度等)存入相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中，再把vi壓入類向量v中，如此反復(fù)，直到把所有的頂點(diǎn)信息全部讀完.

加工方案鄰接表建立以后，首先要對加工方案進(jìn)行遍歷，對已存在的各種加工方案的加工類型、鄰接點(diǎn)以及所能達(dá)到的粗糙度進(jìn)行存儲(chǔ)，以備后期操作的選取.

為了完成這項(xiàng)工作，定義了一個(gè)模板類Digraph，采用UML建模，如圖4所示.

3 基于遺傳算法的工藝路線生成

工藝路線設(shè)計(jì)是指擬定將毛坯制成所需零件的整個(gè)加工路線，是制定工藝規(guī)程的總體布局.在工藝路線設(shè)計(jì)時(shí)，應(yīng)提出幾個(gè)設(shè)計(jì)方案，從中加以分析比較，最后確定一個(gè)最為合理的方案.在本文中將采用自適應(yīng)全局優(yōu)化概率搜索算法——遺傳算法來進(jìn)行工藝路線生成的研究.

復(fù)雜零件的工藝特征之間存在著各種約束關(guān)系，按照實(shí)際要求的不同，可以將它們分為強(qiáng)制性約束和最優(yōu)性約束.將強(qiáng)制性約束集記為Ra，最優(yōu)性約束集記為Rb.

強(qiáng)制性約束集Ra在工藝實(shí)踐中的表現(xiàn)為先后順序上的約束，這是工藝路線中最重要的約束條件.必須考慮的幾類關(guān)系有：(1)先基準(zhǔn)面后其它.(2)先面后孔，先面后鍵槽.(3)先主后次.(4)非破壞性約束關(guān)系.(5)可訪問性約束.(6)特征屬性自身的嚴(yán)格的先后順序[10].

最優(yōu)約束集Rb一般出于對加工時(shí)間、精度和成本的考慮，通常包括：(1)盡量減少裝夾次數(shù),(2)盡量減少換刀次數(shù),(3)聚類約束[10].

GA主要操作包括編碼解碼、適應(yīng)度計(jì)算、遺傳算子設(shè)計(jì).首先確定求解問題的數(shù)學(xué)模型，生成原始種群，對種群個(gè)體進(jìn)行編碼和解碼，然后對各代群體中個(gè)體的適應(yīng)度進(jìn)行計(jì)算，然后使用遺傳算子完成選種、交叉和變異，繁衍后代種群，直至滿足收斂條件，求得所需的最優(yōu)解[11,12].圖5是其基本工作流程.

圖5 基于遺傳算法的排序工作過程

3.1 編碼

應(yīng)用GA首先要對問題中的變量進(jìn)行編碼，編碼的形式?jīng)]有限制.常用的是二進(jìn)制碼鏈.對于工藝排序問題，自變量為特征加工單元，問題是求解特征加工單元排序問題，采用二進(jìn)制編碼不能解決.因此，在本文中選用自然數(shù)編碼方式，基因編碼如表2所示.

表2 基因編碼

3.2 始群體的產(chǎn)生

一般采用隨機(jī)方法產(chǎn)生一系列初始碼鏈，構(gòu)成原始群體.GA的任務(wù)是從這些原始群體出發(fā)，模擬進(jìn)化過程，汰劣存優(yōu)，最后得出優(yōu)秀的群體與個(gè)體，滿足優(yōu)化的要求.

3.3 適應(yīng)度計(jì)算

遺傳算法中以個(gè)體適應(yīng)度的大小來評(píng)定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳機(jī)會(huì)的大小.

設(shè)計(jì)適應(yīng)度函數(shù)時(shí)，主要考慮裝夾次數(shù)、換刀次數(shù)和聚類是否滿足這3方面因素，因此適應(yīng)度函數(shù)定義為：F=a1×Score1+a2×Score2+a3×Score3，其中，Score1、Score2和Score3分別表示裝夾得分、換刀得分和聚類得分，每部分滿分均為100，a1、a2和a3分別表示3部分的權(quán)重，取值：a1=0.5，a2=0.3，a3=0.2，適應(yīng)度滿分也為100.

(1)裝夾得分(n個(gè)特征，k種裝夾類型，Ns次裝夾)

(1)

(2)換刀得分(n個(gè)特征，l種刀具，Nt次換刀)

(2)

(3)聚類得分.設(shè)存在k個(gè)聚類約束Cluster[1]，Cluster[2]，…，Cluster[k]，對于Cluster[i]，定義如果該約束能夠滿足則Φ(Cluster[i])=1，否則Φ(Cluster[i])=0，可得：

(3)

3.4 選種

選種就是從群體中隨機(jī)的選取一對個(gè)體作為其繁殖后代的雙親.通常根據(jù)個(gè)體適應(yīng)度，按照一定的規(guī)則或者方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中.

3.5 交叉

交叉就是將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對，對每一個(gè)個(gè)體以某種概率(稱為交叉概率)選擇一個(gè)斷點(diǎn)，將雙親的基因碼鏈在斷點(diǎn)處斷開，然后模擬自然交配過程進(jìn)行交換其斷開后的一部分.

3.6 變異

變異操作模擬生物在自然遺傳環(huán)境中由于各種偶然因素引起的基因變異,其方法是以一定概率P(稱為變異概率)從群體中選取若干個(gè)個(gè)體，對所選的每個(gè)個(gè)體隨機(jī)的選取某一位或一些基因值，改變?yōu)槠渌牡任换?

圖6 系統(tǒng)功能圖

4 系統(tǒng)運(yùn)行實(shí)例

本課題所開發(fā)的系統(tǒng)主要分為以下兩個(gè)功能模塊：(1)特征加工方法生成模塊,(2)工藝路線優(yōu)化模塊.圖6所示為整個(gè)系統(tǒng)功能圖.下面就以圖7所示零件的加工實(shí)例來對整個(gè)系統(tǒng)的功能進(jìn)行介紹.

圖7 基于遺傳算法的排序工作過程

該零件有6個(gè)加工特征，包括面(1)，孔(2，3，4)，槽(5，6)，括號(hào)內(nèi)為特征編號(hào).6個(gè)加工特征其粗糙度要求分別為面1為Ra3.2，孔2為Ra12.5，孔3和孔4都為Ra1.6，槽5和槽6都為Ra3.2.參照前面所提供的典型特征加工方案圖和加工方案鄰接表，采用圖結(jié)構(gòu)，可以獲得每個(gè)待加工特征的所有可行加工方法.

圖8 工藝參數(shù)輸入 圖9 孔3加工路線選擇界面

得到零件幾何特征并且通過工藝性評(píng)價(jià)之后，系統(tǒng)采用人機(jī)交互的方式輸入加工工藝參數(shù)，如圖8所示.加工工藝參數(shù)主要包括形狀公差、定位公差、輪廓公差、跳到公差、定向公差和表面粗糙度.

零件特征的加工路線方法選擇已經(jīng)在前面進(jìn)行了詳細(xì)介紹，在此只給出孔3的加工方法選取作為示例.選擇孔加工，表面粗糙度0.8，加工起點(diǎn)選擇1.進(jìn)入下一步可得到可行加工終點(diǎn)編號(hào)以及對應(yīng)的可行加工路線，如圖9所示，選擇加工終點(diǎn)為8的加工路線來加工孔3，即孔3的加工方法是：鉆孔—粗鉸—精鉸.同理可以獲得其他幾個(gè)加工特征的加工路線.

當(dāng)零件所有特征加工方法選取完畢，如圖10所示，就可以得到零件特征加工鏈.

再為零件的加工選擇合適的機(jī)床，確定加工特征所需要的加工設(shè)備，如刀具、裝夾等,如圖11所示為刀具選擇界面.

圖10 孔3零件特征加工鏈 圖11 刀具選擇

為了驗(yàn)證該系統(tǒng)所采用的遺傳算法的可行性，對加工該零件所需的加工資源進(jìn)行理想化.選用數(shù)控機(jī)床，完成該零件的加工需要裝夾2次，第一次裝夾完成面1上特征的加工，第二次裝夾完成孔2的加工；刀具的選擇：面1、槽5和槽6的加工選擇銑刀；孔的加工分別選用鉆刀和鉸刀.根據(jù)不同的加工階段可能分為粗銑刀、精銑刀等，根據(jù)不同的加工特征又可能分為面銑刀、鍵槽銑刀等.

對特征的加工刀具進(jìn)行合并，例如槽5和槽6，孔3和孔4，分別采用同一刀具進(jìn)行加工，減少換刀次數(shù)，提高加工效率.合并之后總共需要7把刀具，分別用于粗銑面1、粗銑槽5和槽6、精銑面1、精銑槽5和槽6、鉆孔、粗鉸和精鉸.

參照表2的編碼方式進(jìn)行編碼，該零件編碼長度為13.

表3 特征編碼

面1：f1粗銑，f2精銑；孔2：f3鉆孔；孔3：f4鉆孔，f5粗鉸，f6精鉸；孔4：f7鉆孔，f8粗鉸，f9精鉸；槽5：f10粗銑，f11精銑；槽6：f12粗銑，f13精銑.

特征加工單元集合為：F={f1,f2,…,f13}共13個(gè)特征加工單元，采用自然數(shù)實(shí)現(xiàn)編碼，如表3所示.

建立強(qiáng)制約束集Ra：

(1)f1必須首先加工，作為基準(zhǔn)面；

(2)f12必須在f4之前加工，因?yàn)樘卣骺?包含在特征槽6里面；

(3) 特征屬性的嚴(yán)格順序約束，一個(gè)表面的粗加工工序必須在精加工之前.

參照之前給出的理想化加工資源，分2次裝夾和需要7把刀具用于零件的最后加工成型，給出優(yōu)化約束集Rb：

(1) 裝夾類型集：{SU1，SU2}，其中SU1={f1,…,f2,f4,…,f13},SU2={f3}.

(2) 刀具集：{T1，T2，T3，T3，T5，T6，T7},其中T1={f1}，T2={f10,f12}，T3={f2}，T4={f11,f13}，T5={f3,f4,f7}，T6={f5,f8}，T7={f6,f9}.

(3) 聚類約束集.孔3與孔4最好一起加工，槽5與槽6最好一起加工.

Rb用于確定適應(yīng)度函數(shù).F=a1×Score1+a2×Score2+a3×Score3,其中a1=0.5，a2=0.3，a3=0.2，Score1、Score2和Score3分別參照式(1)、式(2)和式(3)可得：

由表3可知該零件基因鏈長度為13位，根據(jù)前面介紹的遺傳算法初始群體的介紹，為了程序能有效的運(yùn)行初始群體數(shù)目的選擇不應(yīng)過多也不能太少，在這里選取種群大小為30.為保證初始群體中的每個(gè)個(gè)體的隨機(jī)性，在程序編制時(shí)，每個(gè)個(gè)體都采用時(shí)間的隨機(jī)函數(shù)產(chǎn)生一組編碼.初始種群隨機(jī)生成后，采用輪盤賭選擇法進(jìn)行選種，初步選取交叉率為0.7，變異率為0.2.

表4 加工碼鏈及計(jì)算結(jié)果

所有參數(shù)確定以后，就可以進(jìn)行遺傳算法排序了.隨機(jī)產(chǎn)生各個(gè)初始碼鏈后，運(yùn)用工藝約束條件產(chǎn)生的加工碼鏈及計(jì)算過程如表4所示.

此時(shí)得到最優(yōu)個(gè)體基因型：[1，10，12，3，4，7，5，8，2，11，13，6，9]，其表現(xiàn)型為{f1，f10，f12，f3，f4，f7，f5，f8，f2，f11，f13，f6，f9}，其中裝夾次數(shù)3，換刀次數(shù)7，滿足聚類約束，其適應(yīng)度為95.5.

把該工藝路線與實(shí)際結(jié)果相比較，發(fā)現(xiàn)基本符合該零件的加工要求，在假定的加工環(huán)境下，滿足特征間的約束關(guān)系，所以說該結(jié)果是合理可行的.

5 結(jié)束語

工藝規(guī)劃即工藝路線設(shè)計(jì)是工藝設(shè)計(jì)過程中最重要內(nèi)容之一.在實(shí)際工藝規(guī)劃中，由于零件特征的多種加工鏈方案中包含的加工方法不同、加工鏈長短不同，直接影響加工路線排序、工序劃分、機(jī)床選擇等決策活動(dòng).本文致力于工藝規(guī)劃系統(tǒng)的研究，建立了典型加工特征的工藝路線選取規(guī)則，對零件單個(gè)特征進(jìn)行工藝路線選擇，再運(yùn)用全局優(yōu)化思想，考慮具體加工過程，采用遺傳算法對整個(gè)零件加工進(jìn)行工藝規(guī)劃，實(shí)現(xiàn)了工藝排序關(guān)鍵技術(shù).

參考文獻(xiàn)

[1〗 王大康,劉永峰,石亞寧.智能化CAPP系統(tǒng)的工藝決策[J].北京工業(yè)大學(xué)學(xué)報(bào)，2003，(2):129-132.

[2] 秦寶榮,姜少飛,王寧生.基于遺傳算法的零件多加工方案組合優(yōu)化方法[J].中國機(jī)械工程，2005,16(12):1 076-1 078.

[3] 徐宏海.數(shù)控加工工藝[M].北京:化學(xué)工業(yè)出版社,2004:78-91,125-132.

[4] 蔡 蘭,王 霄.數(shù)控加工工藝學(xué)[M].北京:化學(xué)工業(yè)出版社,2005:53-57.

[5] 劉長青.機(jī)械制造技術(shù)[M].武漢:華中科技大學(xué)出版社,2005:218-255.

[6] 周世權(quán).機(jī)械制造基礎(chǔ)[M].武漢:華中科技大學(xué)出版社,2005:160-197.

[7] 張 勇,楊喜權(quán),劉君義.數(shù)據(jù)結(jié)構(gòu)[M].北京:中國林業(yè)出版社,北京希望電子出版社,2006.

[8] Ellis Horowitz,Sartaj Sahni,Sanguthevar Rajasekaran.計(jì)算機(jī)算法(C++版)[M].馮博琴,葉 茂,高海昌,等譯.北京:機(jī)械工業(yè)出版社,2006：184-187.

[9] Larry R.,Nyhoff. C++ An Introduction to Data Structures[M].陳佩佩,李東國,黃達(dá)明,譯.北京:清華大學(xué)出版社,2005:516-523.

[10] 徐 正.三維CAPP中零件特征提取及基于遺傳算法的工藝排序研究[D].武漢：華中科技大學(xué)碩士論文,2005:1-5.

[11] Chen,Yuming. Management of water resources using improved genetic algorithms[J].Computer and Electronics in Agriculture,1997,(8):117-127.

[12] Gabor Renner,Aniko Ekart.Genetic algorithms in computer aided design[J]. Computer-Aided Design，2003,(7):709-726.