王 軍 孟慶智

(燕山大學(xué)機械工程學(xué)院，河北秦皇島066004)

工藝路線的優(yōu)化是CAPP(計算機輔助工藝過程設(shè)計)系統(tǒng)的關(guān)鍵技術(shù)與難點之一，是衡量CAPP系統(tǒng)智能化和實用化的一個重要標(biāo)志，它在很大程度上決定了CAPP系統(tǒng)的應(yīng)用水平［1］。其主要任務(wù)是按照工藝約束規(guī)則和一定的優(yōu)化目標(biāo)，對工件所有加工特征的加工方法進(jìn)行排序，將得到的最優(yōu)加工序列作為工件的工藝路線［2－3］。

工藝路線優(yōu)化問題與其他優(yōu)化問題不同，它求解的不是值優(yōu)化而是排序優(yōu)化，而且排序過程與機床、刀具、夾具、約束之間存在各種可能的聯(lián)系，這使得工藝路線排序成為一個極其復(fù)雜的組合優(yōu)化問題，其優(yōu)化目標(biāo)和約束條件都難以用明確的解析式表達(dá)，因此工藝路線的決策和優(yōu)化問題很難用傳統(tǒng)的優(yōu)化算法來解決［4－5］。本文采用遺傳算法進(jìn)行工藝路線的優(yōu)化決策。它以優(yōu)化變量的某種形式的遺傳編碼為運算對象，以基因交叉重組和變異為基礎(chǔ)進(jìn)行全局搜索，不僅并行性高、魯棒性強，而且個體的適應(yīng)度評價也可以不依賴于目標(biāo)函數(shù)的恰好估值。

本文在對工藝路線優(yōu)化問題進(jìn)行分析的基礎(chǔ)上，建立工藝決策的數(shù)學(xué)模型，并利用約束矩陣來描述工藝約束關(guān)系，而且約束矩陣由系統(tǒng)自動生成，設(shè)計了用于保證加工元序列的滿足約束關(guān)系的算法，對基于遺傳算法的工藝路線優(yōu)化決策方法進(jìn)行了研究。

1 工藝路線優(yōu)化決策的問題描述

進(jìn)行工藝設(shè)計，首先要根據(jù)工件各特征的加工屬性(形狀、尺寸、公差和表面粗糙度)確定其加工方法，然后對所有特征的加工方法進(jìn)行組合排序，這個過程就是工藝路線的優(yōu)化過程。為了方便工藝路線的描述和遺傳操作，將工件特征的某個加工操作定義為加工元，由加工元編號、加工特征、加工方法，以及所使用的機床、刀具、裝夾方案組成。將加工元表示為

Op=(ID，F(xiàn)eature，Process，Machine，Tool，Setup)

其中:ID、Feature、Process、Machine、Tool、Setup 分別為加工元編號、加工特征、加工方法、所需的機床、刀具和裝夾方案。

設(shè) O={Op1，Op2，…，Opn}為完成工件加工的所有加工元的集合。把工件某一工藝路線表示為

其中:{Opa(1)，Opa(2)，…，Opa(n)}={Op1，Op2，…，Opn}，x為以O(shè)pa(1)開始、Opa(n)結(jié)束的加工元序列。

工藝路線優(yōu)化的過程實際上就是根據(jù)當(dāng)前生產(chǎn)環(huán)境，生成一個最優(yōu)化或接近最優(yōu)化的加工元序列的過程。在生產(chǎn)過程中，常根據(jù)實際需要確定目標(biāo)函數(shù)，例如生產(chǎn)成本最低、加工時間最短等，對工藝路線進(jìn)行評價，那么可以確定目標(biāo)函數(shù)的形式為minF(xi)，其中，F(xiàn)(xi)為xi這一工藝路線的優(yōu)化評價函數(shù)。

在工藝路線的優(yōu)化決策過程中，還必須滿足工藝約束，主要指對優(yōu)化排序具有重要影響的加工方法之間的優(yōu)先關(guān)系約束。將約束信息用矩陣A［n］［n］表示。

所謂最優(yōu)工藝路線是指在滿足工藝約束的條件前提下，目標(biāo)函數(shù)值最優(yōu)的工藝路線。其中工藝約束主要是指對工藝路線的優(yōu)化排序具有重要影響的加工方法之間的優(yōu)先關(guān)系約束。在本文中將工藝約束信息用矩陣 A［n］［n］表示。

基于以上分析，工藝路線優(yōu)化問題的數(shù)學(xué)模型可描述為:對于工件的加工元集合 O={Op1，Op2，…，Opn}，尋找一條加工工藝路線 x=＜Opa(1)，Opa(2)，…，Opa(n)＞，使其滿足工藝約束 A［n］［n］，且目標(biāo)函數(shù)值最優(yōu)，即minF(x)。

工藝路線的優(yōu)化過程實際上就是將約束逐個作用到加工元集合上，使得加工元在一定的排列順序下，目標(biāo)函數(shù)值最優(yōu)。

2 工藝約束及其處理方法

2.1 工藝約束的描述

制定合理的工藝路線必須考慮工件加工特征之間和加工方法之間的優(yōu)先關(guān)系約束，主要包括以下幾個方面:

(1)先粗后精 對于每個特征，粗加工工序應(yīng)安排在精加工工序之前進(jìn)行;對于整個工件，所有的粗加工工序應(yīng)安排在所有精加工工序之前進(jìn)行。

(2)先主后次 即先安排工作表面和裝配表面的加工，后安排次要表面的加工，而且次要表面安排在最后精加工或光整加工之前。

(3)先基準(zhǔn)后其他 作為基準(zhǔn)的特征應(yīng)先加工，然后才加工其他表面。如當(dāng)兩個特征之間存在形位公差時，包含基準(zhǔn)的加工特征應(yīng)當(dāng)首先加工;加工階梯軸時，端面特征作為測量基準(zhǔn)優(yōu)先于外圓面加工。

(4)非破壞性約束 保證后面的加工不會破壞在前面加工過程中產(chǎn)生的屬性。例如在一個圓柱上加工螺紋和倒角時，倒角應(yīng)先于螺紋加工。

(5)依賴約束 若某一特征的存在依賴于另一特征，則另一特征先于此特征加工。例如在一個平面上有一個孔特征，那么面特征要先于孔特征加工。

工藝路線必須滿足上述約束規(guī)則。在約束規(guī)則的作用下，加工元之間的優(yōu)先關(guān)系約束表現(xiàn)為執(zhí)行的先后次序。由于定性的、描述性的約束信息在計算機處理時比較復(fù)雜，不便于計算機的底層推理和簡化計算，本文通過工藝約束矩陣的方式描述加工元之間的優(yōu)先關(guān)系約束，將定性的優(yōu)先關(guān)系約束信息轉(zhuǎn)化為定量的、數(shù)字化的矩陣。

約束矩陣用A［n］［n］來表示，n表示加工元的個數(shù)。矩陣中元素aij代表兩加工元之間的先后關(guān)系，元素值按以下規(guī)則進(jìn)行轉(zhuǎn)換:

2.2 約束矩陣的自動生成

系統(tǒng)根據(jù)優(yōu)先關(guān)系約束原則，并結(jié)合加工元中的特征信息、加工方法信息、裝夾方案等信息，對加工元進(jìn)行分類，屬于不同類別間的加工元具有相應(yīng)的優(yōu)先關(guān)系，系統(tǒng)按照約束矩陣轉(zhuǎn)換原則將矩陣中相應(yīng)的元素賦值為1。

以先粗后精原則為例，首先遍歷所有加工元，根據(jù)各加工元的加工方法，將屬于粗加工階段、半精加工階段和精加工階段的加工元劃分到其相應(yīng)集合;由先粗后精原則，有粗加工階段加工元集合中的元素優(yōu)先于半精加工階段加工元集合中的元素，半精加工階段集合中的元素優(yōu)先于精加工階段加工元集合中的元素;最后，根據(jù)約束矩陣轉(zhuǎn)換原則將以具有優(yōu)先關(guān)系的兩個加工元為下標(biāo)的元素賦值為1。在處理完由所有原則產(chǎn)生的加工元之間的優(yōu)先關(guān)系后，工藝約束矩陣自動生成。

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

3.1 基因編碼

基因編碼是應(yīng)用遺傳算法的第一步，常用的二進(jìn)制編碼無法表達(dá)工藝路線的排序優(yōu)化問題。本文采用自然數(shù)字鏈進(jìn)行基因編碼。為便于遺傳操作和約束矩陣的生成，將每一個基因?qū)?yīng)工件加工元集合中的一個加工元，因此每個基因由6部分組成，分別對應(yīng)加工元的6個組成部分。在程序中基因用如下的結(jié)構(gòu)體來描述。其中加工元編碼與自然數(shù)字鏈一一對應(yīng)，它是區(qū)分加工元的標(biāo)志，代表加工元進(jìn)行遺傳操作;基因中其他部分代碼也都用兩位十進(jìn)制數(shù)表示，程序運行過程中需要根據(jù)這些代碼確定加工元間的優(yōu)先關(guān)系和計算染色體的適應(yīng)度值。

3.2 初始種群的產(chǎn)生

初始種群是根據(jù)工件加工元集合隨機生成的一組確定數(shù)量的加工元序列。初始種群中可能存在無效的即不滿足優(yōu)先關(guān)系的加工元序列，需通過約束矩陣和加工元序列調(diào)整算法將它們轉(zhuǎn)化為有效的加工元序列，從而使初始種群中的染色體均符合優(yōu)先關(guān)系約束。

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

在工藝設(shè)計中，工藝路線一般是通過加工成本最低、加工時間最短等作為評價指標(biāo)。本文以加工成本最小作為工藝路線的優(yōu)化目標(biāo)。加工成本包括機床成本、刀具成本、機床變換成本、刀具變換成本和裝夾變換成本。對一個工件的工藝過程來說，在確定各特征的加工方法及其使用的制造資源后，機床成本和刀具成本對每一種加工元序列都是一樣的。對不同的加工元序列，加工成本的不同主要體現(xiàn)在機床變換成本、刀具變換成本和裝夾變換成本。因此本文以總變換成本最小作為工藝路線的優(yōu)化目標(biāo)?？傋儞Q成本C、機床變換成本CM、刀具變換成本CT和裝夾變換成本CS分別表示如下

其中，N 表示加工元集合中加工元的個數(shù);M［i］［i+1］、S［i］［i+1］、T［i］［i+1］分別表示某一加工元序列中第 i個加工元與第i+1個加工元的機床變換成本、裝夾變換成本和刀具變換成本，在本文中設(shè) M［i］［i+1］、S［i］［i+1］、T［i］［i+1］分別為 20、8、1;mi、si、ti分別表示第 i個加工元中所使用的機床、裝夾方案和刀具。對于以上各式有

最優(yōu)的工藝路線是具有最小變換成本的加工元序列，而遺傳算法是根據(jù)適應(yīng)度對個體進(jìn)行評價的，適應(yīng)度值越大者為較優(yōu)的個體，因此有必要建立適應(yīng)度函數(shù)與目標(biāo)函數(shù)的映射關(guān)系:

其中:Lj為第j條染色體，Cmax為工藝路線總變換成本的理論最大值，Cj為第j條工藝路線的總變換成本。

3.4 選擇

采用排序選擇算法和最佳個體保護(hù)策略相結(jié)合的選擇方法。排序選擇算子，即對種群中的個體按照適應(yīng)度值的大小進(jìn)行排序，然后基于一定的比例，將排在前面具有較高的適應(yīng)度值的個體復(fù)制2份，中間具有稍高適應(yīng)度值的染色體復(fù)制1份，排在最后適應(yīng)度值較低的個體不復(fù)制，所有復(fù)制得到的個體構(gòu)成交配池。排序選擇法保證了參與后代的繁衍和進(jìn)化的是種群中的優(yōu)良個體［6］。

采用最佳個體保護(hù)策略，是為了防止進(jìn)化過程中最優(yōu)個體由于參與交叉和變異而被破壞。即每次計算的最優(yōu)個體除作為交配池的種子之外，還直接作為子代個體。最佳個體保護(hù)策略保證了每次計算結(jié)果至少不會比上一次差，使進(jìn)化的方向總是向著最優(yōu)值的方向逼近。

3.5 交叉

為保證交叉后的染色體有效，采用兩點交叉的方式進(jìn)行交叉運算。具體步驟如下:

(1)首先在交配池中隨機選取兩個個體作為父代染色體P1、P2，并隨機生成兩個交叉點，這樣父代染色體被分為左半部分、中間部分和右半部分。

(2)將P1的左半部分和右半部分分別復(fù)制到子代染色體C1的左右兩半部分。

(3)在P2中劃掉與P1的左半部分和右半部分完全相同的基因，將P2中剩余的基因按照它們原來的順序依次復(fù)制到C1的中間部分，這樣就形成C1。

(4)采用同樣方法得到子代染色體C2。圖1為交叉過程。

由于父代染色體是有效的染色體，采用兩點交叉方法生成的子代染色體也是滿足優(yōu)先約束的，因此不需要調(diào)整加工元序列。

3.6 變異

本文采用隨機交換染色體中的2個基因代碼的位置的變異運算。即在一定的變異率下，選擇一部分染色體，在單個染色體內(nèi)部隨機進(jìn)行2個基因的交換形成新的個體，如圖2所示。

表1 基因編碼

由于交換2個基因后，可能會出現(xiàn)無效的即違反優(yōu)先關(guān)系約束的染色體，因此，變異運算完成后，要判斷新生成的個體是否有效。如果無效，則需通過調(diào)整算法將其轉(zhuǎn)化為有效的染色體。在這里，只需調(diào)整兩個交換點之間的基因序列，因為交換位置以外的基因序列本身就滿足優(yōu)先關(guān)系約束，只要保證交換點之間序列的有效性，就能保證整條染色體的有效性。

3.7 加工元序列有效性檢驗與調(diào)整算法

在初始種群生成和遺傳操作過程中，生成的加工元序列可能會不滿足優(yōu)先關(guān)系約束。為了在遺傳算法運行過程中保證個體的有效性，須根據(jù)工藝約束規(guī)則確定的加工元優(yōu)先關(guān)系約束矩陣對個體進(jìn)行有效性檢驗和調(diào)整。

設(shè)某一個體表示的加工元序列為

圖3為算法流程圖。

步驟1:遍歷加工元序列L，從Opa(1)到Opa(n)，設(shè)i=1，j=i+1;

步驟2:搜索約束矩陣，如果Aji=1，說明加工元Opa(j)優(yōu)先于加工元Opa(i)，應(yīng)互換Opa(i)和Opa(j)，并使j++。否則，直接使j++。

步驟3 判斷是否j≤n，如果真，則轉(zhuǎn)到步驟2;否則令i++，并轉(zhuǎn)到步驟4。

步驟4 如果 i＜n，令j=i+1，轉(zhuǎn)到步驟2，否則結(jié)束。

3.8 終止條件

為保證遺傳算法在保證具有較優(yōu)解的基礎(chǔ)上正確退出，以連續(xù)迭代 1 000次，或最優(yōu)個體的適應(yīng)度值連續(xù)迭代200次保持不變?yōu)榻K止條件。

計算終止后，輸出適應(yīng)度值最大個體對應(yīng)的加工元序列，作為工件的工藝路線。

4 應(yīng)用實例

以圖4所示的花鍵套工件為例來說明該算法的實現(xiàn)過程。

首先在明確各特征及其加工方法、定位基準(zhǔn)和制造資源之后，進(jìn)行基因編碼，如表1所示。

然后根據(jù)特征、加工方法、裝夾方案等信息和優(yōu)先關(guān)系約束原則，確定加工元之間的優(yōu)先關(guān)系，并建立描述優(yōu)先關(guān)系的工藝約束矩陣。

設(shè)種群規(guī)模為80，交叉率為0.8，變異率取0.2，迭代次數(shù)達(dá)到1 000或最高染色體的適應(yīng)度值經(jīng)過200次迭代仍保持不變?yōu)榻K止條件。經(jīng)過1 000次迭代，程序運行停止，得到適應(yīng)度值最高的染色體的適應(yīng)度值為393，其對應(yīng)的工藝路線如表2所示。其中更換機床的次數(shù)為3次，更換夾具的次數(shù)為4次，更換刀具的次數(shù)為16次。該優(yōu)化結(jié)果表明基于遺傳算法和約束矩陣的工藝路線優(yōu)化算法是可行有效的。

表2 最大適應(yīng)度值染色體對應(yīng)的工藝路線

5 結(jié)語

本文提出的基于遺傳算法和約束矩陣的工藝路線排序優(yōu)化方法，是CAPP中解決工藝路線優(yōu)化問題的有效實用方法。利用約束矩陣來描述加工元之間的優(yōu)先關(guān)系，并由系統(tǒng)自動生成約束矩陣，開發(fā)了不依賴于特定規(guī)則的加工元序列有效性檢驗與調(diào)整算法，以總變換成本最小為優(yōu)化目標(biāo)，利用改進(jìn)的遺傳算法對工藝路線排序進(jìn)行啟發(fā)式全局尋優(yōu)，實例驗證了該算法的可行性和有效性。

［1］邵新宇，蔡力鋼.現(xiàn)代CAPP技術(shù)與應(yīng)用［M］.北京:機械工業(yè)出版社，2004.

［2］朱海平，肖詩旺，黃剛.基于遺傳算法的工藝過程排序研究［J］.華中科技大學(xué)學(xué)報:自然科學(xué)版，2006，34(3):50－53.

［3］劉連發(fā)，張振明，田錫天，等.基于遺傳算法的工藝路線優(yōu)化決策方法研究［J］.機械制造，2008，46(526):59－62.

［4］王忠賓，王寧生，陳禹六.基于遺傳算法的工藝路線優(yōu)化決策［J］.清華大學(xué)學(xué)報:自然科學(xué)版，2004，44(7):988－992.

［5］張國輝，蔡力鋼，高亮，等.基于改進(jìn)遺傳算法的工藝路線優(yōu)化［J］.機械設(shè)計與制造，2006(8):14－16.

［6］任慶生，葉中行，曾進(jìn)，等.對常用選擇算子的分析［J］.上海交通大學(xué)學(xué)報，2004，34(4):564 －566.