潘玉玲，羅亞波

(武漢理工大學(xué) 機(jī)電工程學(xué)院，武漢 430070)

0 引言

零件的工藝路線是指將毛坯加工到圖紙要求的成品的過程，受工藝約束，加工方法和車間資源的綜合影響，工藝路線的優(yōu)化決策較為復(fù)雜。合理的工藝路線可以縮短生產(chǎn)周期、節(jié)省制造成本、提高產(chǎn)品質(zhì)量，因而受到制造企業(yè)的重視。

由于箱體零件的加工特征多而復(fù)雜，單純依靠經(jīng)驗(yàn)取得可行的工藝方案不僅耗時(shí)較長(zhǎng)，而且難以得到最優(yōu)工藝路線。近年來，眾多學(xué)者針對(duì)工藝優(yōu)化的問題運(yùn)用啟發(fā)式算法，如文獻(xiàn)[1-3]在遺傳算法的基礎(chǔ)上對(duì)工藝路線進(jìn)行優(yōu)化；文獻(xiàn)[4-6]利用混合遺傳—模擬退火算法對(duì)零件的加工排序進(jìn)行優(yōu)化；文獻(xiàn)[7-9]利用蟻群算法優(yōu)化工藝；文獻(xiàn)[10]采用Hopfield神經(jīng)網(wǎng)絡(luò)[11]方法優(yōu)化打磨工藝的工藝路線。但是由于每種算法都有其自身的優(yōu)缺點(diǎn)，針對(duì)工藝路線的優(yōu)化問題，單一的算法具有一定的局限性，達(dá)不到理想的優(yōu)化效果。

針對(duì)復(fù)雜箱體零件的工藝路線的優(yōu)化問題，本文采用一種改進(jìn)算法對(duì)其進(jìn)行優(yōu)化。由于遺傳算法存在后期搜索速度較慢，容易陷入局部最優(yōu)的問題，因此為改善這些問題設(shè)計(jì)一種混合遺傳算法，擴(kuò)大算法的鄰域搜索結(jié)構(gòu)，防止算法在尋優(yōu)過程中“早熟”，并且可以提高算法的效率。

1 問題描述

箱體零件可以看作由一些加工特征組成的集合，可表示如下：

F={f1,f2,f3,,…,fn}

(1)

零件的特征大多都要經(jīng)過多次加工形成特征的加工鏈。有的零件的特征可以一次加工即可達(dá)到設(shè)計(jì)要求，但是對(duì)于特征復(fù)雜的箱體零件來講，加工鏈中的不同操作可能要分不同階段在不同的裝夾中完成。將特征的相關(guān)加工信息定義為特征的加工單元mc(manufacturing cell)，用一個(gè)六元組表示：

mci=(ID,fi,f_name,m,t,cs)

(2)

其中，ID—加工元編碼；fi—加工特征；f_name—加工名稱，如粗車、精車等；m，t，cs分別表示加工特征fi所需的機(jī)床、刀具和裝夾表面。

零件的加工單元所組成的集合即為該零件的加工工藝，表示如下：

MC={mc1,mc,…,mcn}

(3)

零件的任意一條工藝路線可以表示為x=(mc1,mc2,…,mcn)，在實(shí)際生產(chǎn)過程中，零件的工藝路線是加工單元mci在滿足約束條件下的合理排序結(jié)果。

2 數(shù)學(xué)模型

2.1 目標(biāo)函數(shù)

箱體類零件的工藝路線是將其所有特征的加工操作的集合，滿足一定的約束關(guān)系，為達(dá)到特定的目標(biāo)優(yōu)化操作排序的結(jié)果。為了保證加工質(zhì)量和加工精度，本文以機(jī)床、裝夾面和刀具變換次數(shù)最少建立優(yōu)化的目標(biāo)函數(shù)，如下所示：

minf(x)

(4)

f(x)=αf1(x)+βf2(x)+γf3(x)

(5)

(6)

(7)

δ(mciCS,mci+1CS))

(8)

式中，f(x)是目標(biāo)函數(shù)，f1(x)、f2(x)、f3(x)分別為機(jī)床、刀具和裝夾的變換次數(shù)；α、β、γ分別是相對(duì)應(yīng)的權(quán)重系數(shù)，本文根據(jù)經(jīng)驗(yàn)取α=0.45、β=0.3、γ=0.25；mciM、mciT、mciCS分別是機(jī)床、刀具和裝夾表面，δ(a,b)是一個(gè)判斷函數(shù)，φ(c,d)是一個(gè)求和函數(shù)，分別如下所示：

(9)

(10)

2.2 約束條件

為了保證優(yōu)化結(jié)果的合理性，本文中優(yōu)化問題的數(shù)學(xué)模型中以加工操作的優(yōu)先關(guān)系、設(shè)備和刀具加工的唯一性分別建立約束條件，如下所示：

(1)優(yōu)先關(guān)系約束。操作單元的排序必須滿足優(yōu)先關(guān)系約束，即：

?h∈H(i),k,l=1,2,3,…,n;k若ki=1,則lh=0

(11)

式中，H(i)表示加工操作i的前序加工操作集合，k，l均表示操作序列位，且序列位k在序列位l前；ki表示加工操作單元mci在工藝路線的排列順序中第k的位置被執(zhí)行。

(2)機(jī)床唯一性約束。每次加工操作只能選取一臺(tái)機(jī)床進(jìn)行加工，即：

(12)

式中，Miu表示操作mci是否選擇機(jī)床Mu進(jìn)行加工，若選擇Mu則取值為1，反之取0；u為可選擇的機(jī)床編號(hào)，m為可選擇的機(jī)床數(shù)目。

(3)刀具唯一性約束。每次加工操作只能選取一種刀具進(jìn)行加工，即：

(13)

式中，Tjv表示操作mcj是否選擇刀具Tv進(jìn)行加工，若選擇Tv則取值為1，反之取0；v為可選擇的刀具編號(hào)，t為可選擇的刀具數(shù)目。

3 基于混合算法的工藝路線優(yōu)化過程

針對(duì)復(fù)雜箱體零件工藝路線優(yōu)化的問題模型，利用遺傳算法的全局搜索能力和變鄰域搜索[12-13](Variable Neighborhood Search,VNS)方法的擴(kuò)大搜索區(qū)域的能力，提出一種混合遺傳—變鄰域的優(yōu)化算法，在執(zhí)行完選擇、交叉和變異的遺傳操作之后，采用4種鄰域結(jié)構(gòu)搜索遺傳操作得到的新個(gè)體，加快遺傳算法收斂速度。該混合算法的具體實(shí)現(xiàn)過程如下所介紹。

3.1 混合遺傳算法

混合遺傳算法的具體實(shí)現(xiàn)步驟如下：

(1)隨機(jī)初始化種群規(guī)模N，并計(jì)算初始種群個(gè)體適應(yīng)度值；

(2)對(duì)初始種群進(jìn)行選擇、交叉、變異等遺傳操作；

(3)對(duì)遺傳操作得到的最佳個(gè)體進(jìn)行變鄰域操作擴(kuò)大搜索范圍尋求另一局部最優(yōu)解；

(4)計(jì)算算法優(yōu)化后的個(gè)體適應(yīng)度值，較優(yōu)化之前大則保留新個(gè)體，否則保留原個(gè)體；

(5)判斷是否滿足停止條件，滿足即輸出最優(yōu)解，算法結(jié)束，否則繼續(xù)優(yōu)化直至滿足條件停止。

上述的混合遺傳算法的流程圖如圖1所示。

圖1 混合算法流程圖

3.2 GA初始種群的創(chuàng)建

種群初始化就是根據(jù)編碼規(guī)則產(chǎn)生一定數(shù)量的種群初始解。在混合遺傳算法的初始種群創(chuàng)建過程中，隨機(jī)產(chǎn)生數(shù)量為N的種群作為工藝路線優(yōu)化問題的初始解。對(duì)于N的取值，目前常常根據(jù)經(jīng)驗(yàn)設(shè)置，常取值為20～100。

3.3 適應(yīng)度函數(shù)的確定

遺傳算法的搜索方向主要是依靠個(gè)體的適應(yīng)度，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)轉(zhuǎn)化而來的。適應(yīng)度函數(shù)值應(yīng)與目標(biāo)函數(shù)只一一對(duì)應(yīng)并且應(yīng)該保持正值，二者還具有相同的極值點(diǎn)。所以本文的適應(yīng)度函數(shù)如下：

F=fmax-f(x)

(14)

式中，fmax是一個(gè)足夠大的常數(shù)，一般取f(x)的最大值。

3.4 選擇

遺傳算法的選擇操作是基于個(gè)體適應(yīng)度的高低對(duì)染色體進(jìn)行操作，本文采用錦標(biāo)賽選擇和最佳個(gè)體保存結(jié)合的方法。最佳個(gè)體保存方法是將種群中適應(yīng)度最高的父代直接復(fù)制到下一代。錦標(biāo)賽選擇的過程如下：

(1)隨機(jī)選出兩個(gè)父代染色體x1、x2，假定適應(yīng)度F(x1)>F(x2)，同時(shí)隨機(jī)生成一個(gè)值r∈(0,1);

(2)R是控制參數(shù)，此處取值0.9。假如r

(3)重復(fù)上述操作直至子代的染色體數(shù)目達(dá)到種群規(guī)模。

3.5 交叉

交叉是指對(duì)兩個(gè)染色體按某種方式交換部分基因，從而形成新的個(gè)體。為了避免兩個(gè)父代染色體執(zhí)行交叉操作后產(chǎn)生不可行的子代，本文提出一種針對(duì)工藝路線優(yōu)化的改進(jìn)的單點(diǎn)交叉方法。

選擇兩個(gè)個(gè)體p1、p2作為父代染色體，隨機(jī)生成一個(gè)交叉點(diǎn)，將兩個(gè)父代染色體分為左右兩部分。將p1左邊直接復(fù)制給子代c1，將p2未出現(xiàn)在c1左邊基因串中的基因按順序復(fù)制給c1的右邊從而形成子代c1整體；按照相同的方法可生成子代c2整體。其示意圖見圖2。

圖2 交叉算子示意圖

3.6 變異

變異操作發(fā)生在交叉之后，是將個(gè)體染色體編碼中的某些基因用其他等位基因來代替，形成新個(gè)體的過程。本文首先在基因?qū)硬捎没蚧Q操作使染色體基因發(fā)生突變，產(chǎn)生新的加工單元排序序列染色體,具體示意圖如圖3所示；然后在基因內(nèi)部對(duì)加工單元使用的機(jī)床和刀具進(jìn)行變異操作：選擇染色體的一個(gè)基因位，用可替換刀具和機(jī)床的方式進(jìn)行變異操作，機(jī)床位變異的示意圖如圖4所示，刀具位變異的示意圖類似于機(jī)床位變異示意圖，此處不做贅述。

圖3 基因?qū)幼儺愂疽?/p>

圖4 基因?qū)觾?nèi)部機(jī)床變異示意圖

3.7 變鄰域操作

VNS作為一種元啟發(fā)式算法，解決組合優(yōu)化問題的效果較好。為提高GA算法的局部尋優(yōu)能力，本文在遺傳算法進(jìn)化期間混合變鄰域搜索算法，并設(shè)計(jì)了4種鄰域結(jié)構(gòu)[10]，具體示意圖如圖5～圖8所示。

(1)第一鄰域。在工藝路線序列中，隨意選擇一個(gè)加工單元向前插入；

(2)第二鄰域。在工藝路線序列中，隨意選擇一個(gè)加工單元向后插入；

(3)第三鄰域。在工藝路線序列中，隨意選擇多個(gè)加工單元向前插入；

(4)第四鄰域。在工藝路線序列中，隨意選擇多個(gè)加工單元向后插入。

圖5 第一鄰域

圖6 第二鄰域

圖7 第三鄰域

圖8 第四鄰域

4 工藝路線優(yōu)化方法應(yīng)用實(shí)例

用圖9中某企業(yè)中某型號(hào)的發(fā)動(dòng)機(jī)缸體為例驗(yàn)證該混合算法的有效性。

通過分析發(fā)動(dòng)機(jī)缸體的三維模型可知它有42個(gè)加工特征，主要加工特征是缸體的6個(gè)面和面上的孔系，加工這些加工特征需要76個(gè)加工單元。本例中標(biāo)記發(fā)動(dòng)機(jī)缸體頂面、右面、后端面、左面、底面和前端面分別為A、B、C、D、E、F，加工信息和加工資源見表1、表2和表3。

表1 發(fā)動(dòng)機(jī)缸體特征及加工信息表

續(xù)表

表2 可用機(jī)床資源表

表3 可用刀具資源表

圖9 發(fā)動(dòng)機(jī)缸體的三維模型

混合遺傳算法的參數(shù)設(shè)置如下：

種群規(guī)模N=50，最大迭代次數(shù)T=400，交叉概率Pc=0.7,變異概率Pm=0.15,鄰域插入次數(shù)為3次，最大不超過10次。根據(jù)初始化信息和約束條件，用MATLAB編寫相關(guān)程序，運(yùn)行得到了混合遺傳算法和遺傳算法的對(duì)比效果圖如圖10所示。從程序運(yùn)行結(jié)果可以得出混合算法比單純遺傳算法的收斂速度快23.8%，并且混合算法得到的優(yōu)化結(jié)果的目標(biāo)值為28.55，比遺傳算法結(jié)果的29.55小。

得到的優(yōu)化后的工藝路線如表4所示，其中，機(jī)床變換11次，刀具變換71次，裝夾面變換10次。中間插入清洗、試漏、檢驗(yàn)等輔助工序，形成完整的發(fā)動(dòng)機(jī)缸體的工藝路線。

圖10 算法迭代對(duì)比圖

5 結(jié)論

針對(duì)復(fù)雜箱體類零件結(jié)構(gòu)的復(fù)雜性，將箱體類零件的加工路線的優(yōu)化細(xì)化為特征的操作單元的排序優(yōu)化問題；然后分析特征之間存在的約束條件，根據(jù)問題建立相應(yīng)的數(shù)學(xué)模型，采用混合遺傳變鄰域算法進(jìn)行優(yōu)化，利用實(shí)例對(duì)改進(jìn)的算法進(jìn)行驗(yàn)證，證明了優(yōu)化方法的有效性和實(shí)用性。

表4 優(yōu)化后的發(fā)動(dòng)機(jī)缸體工藝路線

續(xù)表