基于遺傳算法的加工操作排序及優(yōu)化

劉 巖，段國(guó)林，蔡 瑾

(河北工業(yè)大學(xué) 機(jī)械工程學(xué)院，天津 300131)

?

基于遺傳算法的加工操作排序及優(yōu)化

劉 巖，段國(guó)林，蔡 瑾

(河北工業(yè)大學(xué) 機(jī)械工程學(xué)院，天津 300131)

針對(duì)加工操作排序是一個(gè)動(dòng)態(tài)的、多約束的組合優(yōu)化的過程，提出了基于遺傳算法的加工操排序方法。以最小變化機(jī)床、裝夾和刀具次數(shù)為目標(biāo)，構(gòu)建操作排序優(yōu)化模型。根據(jù)加工規(guī)則建立工藝約束關(guān)系，生成操作優(yōu)先關(guān)系矩陣，驗(yàn)證并調(diào)整加工操作確保排序有效。采用雙層編碼遺傳算法將加工資源與操作相關(guān)聯(lián)，分析操作優(yōu)先關(guān)系矩陣劃分加工階段，減少無效解的求解空間。應(yīng)用遺傳算子選擇、交叉和變異，并對(duì)算法進(jìn)行了改進(jìn)，采用進(jìn)化逆轉(zhuǎn)操作提高局部搜索能力，加快收斂速度。最后通過實(shí)例驗(yàn)證該算法的有效性和實(shí)用性。

CAPP; 操作排序；遺傳算法; 操作優(yōu)先關(guān)系矩陣; 工藝路線優(yōu)化

0 引言

目前產(chǎn)品發(fā)展趨勢(shì)是多品種、小批量、客戶個(gè)性化、更新快，需要企業(yè)快速設(shè)計(jì)縮短產(chǎn)品開發(fā)和制造周期。產(chǎn)品實(shí)現(xiàn)過程中工藝設(shè)計(jì)是關(guān)鍵技術(shù)之一，決策和優(yōu)化產(chǎn)品的工藝路線并且保證加工質(zhì)量要求。傳統(tǒng)的工藝設(shè)計(jì)是工藝設(shè)計(jì)人員根據(jù)自己的工作經(jīng)驗(yàn)和工藝知識(shí)，制定一條工藝路線。該方案可以生產(chǎn)出符合加工要求的產(chǎn)品，但結(jié)果可能不是最優(yōu)的，工藝決策過程非常耗時(shí)、費(fèi)力導(dǎo)致工作效率低。當(dāng)加工資源發(fā)生改變，上述的方法也就不再適用，還需要重新設(shè)計(jì)加工路線。所以，采用智能的工藝路線規(guī)劃可快速而準(zhǔn)確地生成符合要求的多條工藝路線，并從中選取最優(yōu)解。研究人員應(yīng)用蟻群算法優(yōu)化工藝路線，以知識(shí)描述加工零件確定加工元，采用加權(quán)海明距離判斷加工元的相識(shí)度[1]。文獻(xiàn)[2]分析箱體加工的典型工藝，采用多色集合理論的層次遞階結(jié)構(gòu)建立加工過程模型，選取零件的最佳工藝路線。而文獻(xiàn)[3]運(yùn)用該理論的合取運(yùn)算對(duì)特征測(cè)量路徑分組以蟻群算法規(guī)劃子路徑。一些研究者通過遺傳算法尋求最優(yōu)解，建立擴(kuò)展加工元優(yōu)先矩陣表示加工順序[4]，加工中心為了減少刀具空走行程，提高孔群的加工效率分別采用遺傳算法優(yōu)化孔群的加工路線[5]和蟻群算法與相鄰排序算法相結(jié)合來規(guī)化鈑金零件上的孔群加工路線[6]。為了提高運(yùn)算速度對(duì)遺傳算法進(jìn)行改進(jìn)，采用自適應(yīng)遺傳算法優(yōu)化加工中心的箱體工步排序[7]并根據(jù)約束規(guī)則描述加工序列的優(yōu)化關(guān)系生成約束矩陣[8]。為了防止陷入局部?jī)?yōu)化，應(yīng)用遺傳算法和模擬退火算法相結(jié)合來優(yōu)化復(fù)雜箱體加工順序[9]。

本文將工藝知識(shí)和遺傳算法相結(jié)合，在加工操作排序過程中引入熱處理工序，有效的將加工操作分段，減少求解空間中的無效解。同時(shí)為了適應(yīng)加工環(huán)境的動(dòng)態(tài)變化，采用雙層編碼遺傳算法，在加工操作編碼時(shí)也考慮加工資源如機(jī)床，準(zhǔn)確地從全局角度表達(dá)了問題的求解。在滿足工藝約束的條件下，應(yīng)用選擇、交叉、變異等操作，優(yōu)化工藝方案，將加工規(guī)則轉(zhuǎn)換為操作優(yōu)先關(guān)系矩陣，以最小機(jī)床、裝夾和刀具的更換次數(shù)建立目標(biāo)函數(shù)對(duì)加工操作排序及優(yōu)化，快速選出適應(yīng)產(chǎn)品的最優(yōu)加工路線。

1 工藝排序優(yōu)化問題的數(shù)學(xué)模型

工藝排序優(yōu)化過程是將所有操作構(gòu)成了整個(gè)求解空間的解，滿足一定的工藝約束條件下，確定每個(gè)操作的加工先后順序，構(gòu)成了一系列有效的加工序列。根據(jù)生產(chǎn)需要設(shè)置目標(biāo)值最小，得到最優(yōu)加工操作排序。排序問題的約束條件不能由具體的解析式表達(dá)，是一個(gè)非線性規(guī)劃的函數(shù)尋優(yōu)，其數(shù)學(xué)模型如下：

其中x∈X，f(x)為目標(biāo)函數(shù)，gi(x)和hj(x)是約束條件，x*=為滿足工藝約束的有效加工操作的最優(yōu)解。

2 工藝路線優(yōu)化模型的建立

工藝優(yōu)化過程是在一定的加工原則下，具有約束條件的多目標(biāo)排序問題也是一個(gè)典型組合優(yōu)化問題。加工操作需要符合工藝加工規(guī)則，如先基準(zhǔn)、先粗后精和先主后輔等原則，確保求解的有效性[10]。

2.1 工藝約束及表達(dá)

工藝約束是滿足加工規(guī)則的一種優(yōu)先關(guān)系，是一個(gè)復(fù)雜的網(wǎng)狀結(jié)構(gòu)，同時(shí)加工元間的優(yōu)先關(guān)系是有方向的，并且不可逆。加工質(zhì)量要求較高或復(fù)雜零件的工藝路線需要?jiǎng)澐旨庸るA段，在各個(gè)階段按照?qǐng)D紙精度要求安排加工操作順序。而熱處理工序能夠改善材料的加工切削性能和金屬組織、消除內(nèi)應(yīng)力提高零件表面硬度，在加工階段的劃分起著重要的作用，粗加工在熱處理前，半精加工等精度高的加工在其后[10]。在加工操作中引入熱處理工序會(huì)節(jié)省很大求解空間，提高收斂速度。

為了確保加工排序合理性，以關(guān)系矩陣的方式來表達(dá)工藝規(guī)劃中約束即工藝規(guī)則。例如完成零件的加工需要有n個(gè)加工操作，根據(jù)零件圖中的技術(shù)要求和材料屬性得知是否需要熱處理工序，若需要設(shè)置為n+1道工序，生成操作優(yōu)先關(guān)系矩陣A。設(shè)置該零件關(guān)系矩陣大小為A(n+1)(n+1)其中aij為矩陣A的元素，當(dāng)aij=1時(shí)操作ai優(yōu)先于aj。零件操作約束函數(shù)流程步驟如下：

Step1: 生成操作優(yōu)先關(guān)系矩陣A(n+1)(n+1)。

Step2:根據(jù)矩陣A并對(duì)隨機(jī)生成的染色體S劃分操作階段。

1)判斷列全為0的操作，該操作為加工的開始，而機(jī)械加工的開始工序通常為粗加工階段。假設(shè)為m個(gè)，將操作依次識(shí)別并放入S(n+1)的前m位置；

2)判斷行全為0的操作，該操作通常為該特征加工的結(jié)束即在其后沒有對(duì)該特征的加工操作。也為一些輔助特征如倒角、鉆孔等操作，假設(shè)為d個(gè)將其識(shí)別放入一個(gè)存儲(chǔ)空間S(n+1)的末端；

(3)插入熱處理工序，設(shè)置為第(m+1)道工序。

Step3：根據(jù)優(yōu)先矩陣的A,從i=(m+2)依次開始判斷加工序列S(n+1)的有效性，若S(i)=b，則調(diào)用矩陣A，若abj=1，ab優(yōu)先aj,且aj=r；若S(i)=b

Step4:i=i+1,直至i=n結(jié)束，生成的染色體S符合加工優(yōu)先順序。加工操作排序是否合理的驗(yàn)證過程如圖1所示。

圖1 約束函數(shù)流程圖

2.2 優(yōu)化目標(biāo)函數(shù)

加工資源都已確定的情況下，裝夾、刀具和機(jī)床的頻繁變換，造成了加工效率的降低和加工成本的增加，也不利于保證加工精度[11]。本文以加工過程中最少機(jī)床變化、裝夾和換刀次數(shù)為優(yōu)化目標(biāo)，該函數(shù)由機(jī)床、裝夾和換刀次數(shù)三部分組成，通過權(quán)重分配將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。如公式(1)所示：

ObjV=ω1×f(x1)+ω2×f(x2)+ω3×f(x3)

(1)

式中: ω1，ω2, ω3分別表示加床、夾具和刀具變換次數(shù)的權(quán)重系數(shù)[3]，根據(jù)經(jīng)驗(yàn)分別取ω1=0.5，ω2=0.3, ω3=0.2。

(2)

(3)

(4)

f(x1)f(x2)f(x3)分別為該零件加工時(shí)工序排列的機(jī)床、裝夾和刀具變化次數(shù)。

O.Mi,O.Ft(i),O.Ti為該操作所需要的機(jī)器、夾具和刀具，函數(shù)g(x-y)為判斷函數(shù)。

(5)

為了減少數(shù)據(jù)對(duì)分析結(jié)果的影響，將由公式(2)～(4)計(jì)算得到的數(shù)據(jù)進(jìn)行數(shù)據(jù)歸一化處理，使結(jié)果值映射到[0-1]之間。max為樣本數(shù)據(jù)的最大值，min為樣本數(shù)據(jù)的最小值，current為當(dāng)前值，機(jī)床、裝夾和刀具的變換數(shù)量進(jìn)行轉(zhuǎn)換，如表1所示。

表1 函數(shù)歸一化處理

3 GA的加工操作優(yōu)化排序

遺傳算法是一種全局優(yōu)化智能算法，其原理是模仿生物界的演化法則，將問題參數(shù)編碼形成染色體，利用迭代的方法進(jìn)行選擇、交叉和變異算子來交換染色體信息，最終生成符合優(yōu)化目標(biāo)的染色體[12]。基于遺傳算法的工藝路線優(yōu)化方法的步驟如圖2所示。

圖2 遺傳算法的工藝路線優(yōu)化流程圖

3.1 編碼

由于工藝操作排序是一個(gè)非線性、動(dòng)態(tài)的優(yōu)化問題，采用雙層編碼遺傳算法將染色體分兩層編碼，第一層表示零件加工的工序，第二層表示加工機(jī)床，并采用整數(shù)代碼以解決排序問題。每一條染色體代表了一種工藝方案，其長(zhǎng)度等于加工的操作數(shù)和每個(gè)操作所需的機(jī)床。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)表明染色體或解的優(yōu)劣，是自然選擇的唯一依據(jù)。而遺傳算法中的適應(yīng)度函數(shù)值越大越代表染色體最優(yōu)。適應(yīng)度函數(shù)由目標(biāo)函數(shù)變化得到，而優(yōu)化的目標(biāo)是求最小化問題。所有將式(1)定義的優(yōu)化的目標(biāo)函數(shù)取倒數(shù),使其轉(zhuǎn)化為適應(yīng)度函數(shù)。

3.3 初始化種群

遺傳算法隨機(jī)生成的種群，有可能不符合加工操作優(yōu)先條件，是無效的加工序列。調(diào)用驗(yàn)證程序，驗(yàn)證并調(diào)整不符合要求的序列，直至初始種群中所有染色體都符合要求。該算法中種群數(shù)量是一定的，設(shè)置太小收斂速度快，但是容易出現(xiàn)早熟現(xiàn)象，值太大運(yùn)算效率低。所以根據(jù)經(jīng)驗(yàn)設(shè)置為N=20～100[9]。

3.4 選擇

輪賭盤選擇算子是適應(yīng)度值越大的染色體被選中的概率越大，這樣能使遺傳算法往好的方向進(jìn)化，有助于提高解的質(zhì)量，如公式(6)所示計(jì)算染色體的適應(yīng)度值選中概率。但是該算法不能保證最好的染色體遺傳給下一代，對(duì)其進(jìn)行改進(jìn)使用“精英策略”將當(dāng)前代最高適應(yīng)度的染色體按比例直接選入下一代種群，防止在交叉、變異操作時(shí)將好的個(gè)體破壞。

(6)

3.5 交叉

種群采用整數(shù)交叉法獲得新的染色體，從種群中隨機(jī)選中兩個(gè)染色體a和b，隨機(jī)選中交叉位置r(r1～n-1)，交換該交叉點(diǎn)后的工序。交叉后新生成的染色體a1和b1會(huì)出現(xiàn)工序的缺失和多余，根據(jù)交叉前染色體a和b來調(diào)整使其合理。

3.6 變異

為了保護(hù)群體的多樣性，避免問題局部?jī)?yōu)化，種群通過變異操作獲得新的染色體。從種群隨機(jī)選取變異染色體，選擇變異位置r1和r2，把染色體中兩位置的工序?qū)Q，生成新的染色體，通常變異率為0.01～0.1。

3.7 進(jìn)化逆轉(zhuǎn)操作

為了改善遺傳算法的局部搜索能力，在選擇、交叉、變異后引入連續(xù)多次的進(jìn)化逆轉(zhuǎn)操作，對(duì)遺傳算法改進(jìn)。運(yùn)用進(jìn)化逆轉(zhuǎn)算子過程如圖3所示。從種群中選擇一條染色體，該染色體由10個(gè)基因組成，隨機(jī)生成該個(gè)體的兩個(gè)位置r1和r2,則該兩位置間的基因相互交換。若取r1=4和r2=9，經(jīng)過進(jìn)化逆轉(zhuǎn)操作后生成新的子代染色體。該算子具有單方向性，只有經(jīng)逆轉(zhuǎn)后，適應(yīng)度值有提高的才接受，否則逆轉(zhuǎn)無效。

圖3 進(jìn)化逆轉(zhuǎn)操作后生成子代染色體

4 實(shí)例

以錘式破碎機(jī)錐套零件加工為實(shí)例，如圖4所示。零件錐套是機(jī)械傳動(dòng)連接部件，精度高、結(jié)構(gòu)緊湊，外圓柱面與大皮帶相連接，內(nèi)孔圓錐和軸相連接，傳遞動(dòng)力驅(qū)動(dòng)工件運(yùn)轉(zhuǎn)，所以該工件內(nèi)孔和外圓的加工精度較高。

圖4 錐套零件圖

如表2所示該零件共有13個(gè)特征，包括6個(gè)主特征和7個(gè)輔特征。

表2 零件特征描述

為了減少計(jì)算時(shí)間將孔組合特征如(鉆-絞)進(jìn)行合并處理，該零件包括20個(gè)機(jī)加工操作，根據(jù)零件圖得知需要熱處理工序，設(shè)置為最后一個(gè)操作序號(hào)21，加工操作及遺傳算法的編碼，如表3所示。

表3 加工特征信息及遺傳算法編碼

續(xù)表

特征加工操作操作名稱裝夾面加工設(shè)備刀具編碼F6?1Op16車倒角FS1M2T416F6?2Op17拉內(nèi)孔鍵槽FS3M3T417F2?2Op18鉆?17．5孔FS4M4T818攻絲M4T9F2?3Op19鉆?20孔FS4M4T1019鉆?30孔M4T11锪倒角M4T12F4?2Op20鉆?21×40FS4M4T1320鉆?26×102M4T14攻絲40M4T15Op21熱處理21

通過分析旋轉(zhuǎn)件錐套的特征拓?fù)潢P(guān)系，根據(jù)工藝規(guī)則可以明確加工操作的優(yōu)先加工關(guān)系。將表3中的各個(gè)加工操作處理得到表4的操作優(yōu)先表，生成加工操作優(yōu)先關(guān)系矩陣，用于驗(yàn)證和調(diào)整操作順序以確保加工排序的有效性。

表4 加工操作優(yōu)先表

設(shè)置遺傳算法的初始參數(shù)，初始種群數(shù)量為40，選擇代溝為0.9，交叉率概率為0.95，變異率為0.01，迭代次數(shù)200，運(yùn)算最優(yōu)的結(jié)果如下:

1→3→9→11→6→21→2→4→14→7→12

→10→13→16→5→8→15→18→19→20→17

由此可知該零件加工過程中換機(jī)器變換次數(shù)為 4次，裝夾次數(shù)為6，刀具更換次數(shù)為14,適應(yīng)度值為140，加工操作排序符合實(shí)際加工要求。

5 結(jié)論

采用遺傳算法以旋轉(zhuǎn)件錐套為例，在工藝約束的優(yōu)先操作關(guān)系矩陣中引入熱處理工序，分隔加工階段減少了無效加工操作排序的求解空間，提高了計(jì)算收斂速度。為了解決隨機(jī)生成工藝過程中選擇、交叉和變異后對(duì)基因的破壞，設(shè)計(jì)驗(yàn)證算法確保工序的有效性。并對(duì)遺傳算法進(jìn)行了改進(jìn)，引入連續(xù)多次的進(jìn)化逆轉(zhuǎn)操作，提高遺傳算法的局部搜索能力，避免陷入局部最優(yōu)解。由于加工制造資源是動(dòng)態(tài)的、不確定的，采用兩層基因編碼考慮加工機(jī)床設(shè)備從全局的角度優(yōu)化加工過程，可以增加生產(chǎn)制造的柔性。在得到次優(yōu)解的同時(shí)還可以得到多種方案的工藝加工路線, 以備工藝人員選擇，該方法非常適應(yīng)于動(dòng)態(tài)的加工環(huán)境。

[1] 劉偉,王太勇,周 明,等. 基于蟻群算法的工藝路線生成及優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng),2010,16(7):1379-1382.

[2] 祝天榮, 徐新盛, 陶西柱. 基于多色集合理論的機(jī)械零件加工路線方法研究[J]. 組合機(jī)床與自動(dòng)化加工技術(shù),2013(9):129-131.

[3] 王春梅,姜騰.基于多色集合的智能三坐標(biāo)測(cè)量路徑規(guī)劃研究[J].組合機(jī)床與自動(dòng)化加工技術(shù),2014(12):88-90.

[4] 袁青,李迎光,王 偉,等. 基于遺傳算法的飛機(jī)結(jié)構(gòu)件加工特征排序[J].機(jī)械科學(xué)與技術(shù),2011,30(1):86-92.

[5] 肖軍民.一種改進(jìn)遺傳算法在孔群加工路徑中的優(yōu)化[J].組合機(jī)床與自動(dòng)化加工技術(shù),2015(2):151-153.

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

[7] 鄭永前, 王 陽. 基于遺傳算法的加工工藝決策與排序優(yōu)化[J].中國(guó)機(jī)械工程,2012,23(1):59-65.

[8] 王軍,孟慶智. 基于遺傳算法與約束矩陣的工藝路線優(yōu)化方法研究[J]. 制造技術(shù)與機(jī)床，2011(8):147-152.

[9] 徐立云,史楠,段建國(guó), 等. 基于特征加工元的復(fù)雜箱體類零件工藝優(yōu)化[J]. 中國(guó)機(jī)械工程, 2013,24(2):201-207.

[10] 李凱嶺. 機(jī)械制造工藝學(xué)[M]. 北京:清華大學(xué)出版社,2014.

[11] 劉連發(fā), 張振明, 田錫天, 等. 基于遺傳算法的工藝過程優(yōu)化決策方法研究[J]. 機(jī)械制造,2008,46(52):59-62.

[12] 玄關(guān)男,程潤(rùn)偉. 遺傳算法與工程優(yōu)化[M]. 北京:清華大學(xué)出版社,2004.

(編輯 李秀敏)

Operation Sequencing and Optimization Based on Genetic Algorithm

LIU Yan, DUAN Guo-lin, CAI Jin

(School of Mechanical Engineering,Hebei University of Technology, Tianjin 300130,China)

Aiming at processing operation sequencing is a dynamic combinatorial optimization problem with multi-constraints, a method based on genetic algorithm is presented. An operation sequence optimization model is built by taking the minimum number of changes machines, setups and cutting tools as the objective. Operation precedence relation matrix is generated according to the rules of process constraint and the process operations are verified and adjusted by using the matrix to ensure the process route is feasible. Hierarchic genetic algorithm was adapted to associate operation with processing resources, dividing the processing stages by analyzing operation precedence relation matrix to reduce invalid solutions. Genetic operators of crossover and mutation are applied and the algorithm was improved by using reverse evolution operator to enhance the local searching ability and accelerated the convergence speed. Finally, an example is given to testify the effectiveness and practicability of this algorithm.

CAPP; operation sequencing; genetic algorithm; operation precedence relation matrix; process route optimization

1001-2265(2016)11-0126-04

10.13462/j.cnki.mmtamt.2016.11.034

2016-01-10；

2016-02-18

河北省自然科學(xué)基金項(xiàng)目(E2010000052)

劉巖(1977—)，女，遼寧葫蘆島人，河北工業(yè)大學(xué)博士研究生，研究方向?yàn)镃AD/CAPP/CAM，(E-mail)lyan092012400900@sina.com。

TH162;TG506

A