融合帝國(guó)競(jìng)爭(zhēng)與遺傳算法的零件加工工藝排序方法＊

李書涵 周學(xué)良 冷杰武

（①湖北汽車工業(yè)學(xué)院機(jī)械工程學(xué)院，湖北 十堰 442002；②廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣東 廣州 510006）

隨著經(jīng)濟(jì)社會(huì)的快速發(fā)展，多品種、智能化、用戶需求多樣化以及產(chǎn)品更新?lián)Q代速度快成為企業(yè)面對(duì)的重要形勢(shì)。在傳統(tǒng)工藝設(shè)計(jì)中，通常需要工藝人員依靠自身的操作實(shí)踐和技術(shù)理論知識(shí)來(lái)確定工序路線，才能制造出滿足設(shè)計(jì)生產(chǎn)需要的加工制品，在針對(duì)不同結(jié)構(gòu)的傳統(tǒng)零部件生產(chǎn)中，加工工序數(shù)越多，排序范圍越廣，在設(shè)計(jì)生產(chǎn)過(guò)程中所遇到的技術(shù)問(wèn)題就越多，生產(chǎn)效率越低。當(dāng)工藝設(shè)計(jì)條件改變后，又必須更改加工工藝路線，因此僅靠以往設(shè)計(jì)生產(chǎn)中的經(jīng)驗(yàn)難以得出最優(yōu)的排序路線，而且在不同機(jī)床上加工，傳統(tǒng)零部件生產(chǎn)長(zhǎng)期存在的主要困難是裝夾數(shù)量多、工作效率低下，同時(shí)面對(duì)復(fù)雜零件且需更換多種刀具，所以選擇采用智能的加工工藝路徑規(guī)劃，迅速而精確地得到滿足設(shè)計(jì)生產(chǎn)需要的多條工藝路線，并從中選取最優(yōu)加工路線是很有必要的。劉勇通過(guò)運(yùn)用蟻群算法優(yōu)化工藝路線，選擇利用知識(shí)描述方法對(duì)加工單元的確定[1]。王春梅采用蟻群算法對(duì)子路徑進(jìn)行了規(guī)劃并選擇合取運(yùn)算方法進(jìn)行分類特征測(cè)量路徑[2]。袁青等研究者建立和推廣了加工單元優(yōu)先矩陣[3]來(lái)表示加工順序，針對(duì)在加工中心中減少刀具空走行程的問(wèn)題，采用遺傳算法優(yōu)化加工路線[4],以及針對(duì)鈑金零件上的孔群加工路線選擇蟻群算法和相鄰排序算法相混合進(jìn)行求解[5]。鄭永前采用自適應(yīng)遺傳算法解決箱體加工工步排序問(wèn)題[6]。Leung C W采用基于個(gè)體的蟻群優(yōu)化算法的自催化過(guò)程對(duì)工藝規(guī)劃進(jìn)行求解[7]。徐立云針對(duì)復(fù)雜結(jié)構(gòu)的箱體零件，采用模擬退火以及遺傳相混合對(duì)加工序列進(jìn)行尋優(yōu)來(lái)避免計(jì)算結(jié)果陷入局部最優(yōu)[8]。由于每種算法都有其相應(yīng)的技術(shù)特點(diǎn),針對(duì)工藝路線的尋優(yōu)問(wèn)題，為了進(jìn)一步提升加工排序的尋優(yōu)效果，將每種算法之間的優(yōu)劣特性進(jìn)行相互彌補(bǔ)，盡可能取得最理想的尋優(yōu)效果。

本文針對(duì)零件加工工藝排序問(wèn)題，以最小化機(jī)床、裝夾以及刀具更換次數(shù)最小為目標(biāo)，構(gòu)建零件加工工藝排序的數(shù)學(xué)模型，并提出融合帝國(guó)競(jìng)爭(zhēng)與遺傳算法的求解方法，將帝國(guó)競(jìng)爭(zhēng)算法輸出的較優(yōu)加工序列作為遺傳算法的初始種群，通過(guò)融合帝國(guó)競(jìng)爭(zhēng)算法不受初始種群影響的特性和遺傳算法的快速收斂能力，提升工藝規(guī)劃的效率和質(zhì)量。

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

1.1 問(wèn)題描述

工藝排序是在明確零件全部待加工特征和加工方法后，對(duì)工藝路線進(jìn)行合理排序的過(guò)程。在進(jìn)行工藝決策之前，通過(guò)查詢工藝手冊(cè)或運(yùn)用相關(guān)經(jīng)驗(yàn)可以確定各個(gè)特征的加工工步，將特征的每個(gè)加工工步定義為特征加工單元fi（簡(jiǎn)稱“特征元”）[9]。一條完整的工藝路線由零件中每個(gè)特征加工單元按照一定的順序排列所組成，可以描述為S={f1,f2,f3···,fn}。

在復(fù)雜零件的加工特征集合中包含了各種不同的約束關(guān)聯(lián)，在這些約束下，特征元之間存在著不同的關(guān)聯(lián)性和先后順序，確保零件能夠逐步按設(shè)計(jì)要求生產(chǎn)出來(lái)。因此，在加工工藝排序路線中也必須滿足各種約束條件。根據(jù)技術(shù)要求和實(shí)際生產(chǎn)中的作業(yè)條件不同，可將約束分為工藝約束和最優(yōu)性約束兩類。工藝約束為在加工工藝過(guò)程中表現(xiàn)為先后順序的約束，在加工工藝路線排序中這是必須考慮的因素[10]。需要考慮的約束關(guān)系有：

（1）先基準(zhǔn)，后其他，即先加工基準(zhǔn)特征再加工其他特征。

（2）先粗后精，即先進(jìn)行粗加工，后進(jìn)行半精加工和精加工。

（3）先加工面后加工孔，先加工面后加工鍵槽。

（4）先主后次。先加工主特征后加工輔助特征。

（5）非破壞性約束關(guān)系。后加工的特征屬性不能破壞前操作所產(chǎn)生的特征屬性。

（6）可訪問(wèn)性約束。為確保每個(gè)特征可以訪問(wèn)，某些特征的加工只能在其他特征之后進(jìn)行。

最優(yōu)性約束是指滿足后能都達(dá)到更好的經(jīng)濟(jì)性或質(zhì)量等效益的約束。由于在實(shí)際生產(chǎn)中存在各種技術(shù)差異和困難，導(dǎo)致很難滿足所有約束。因此，在工藝排序中工藝約束必須滿足，最優(yōu)性約束則盡量滿足。

引入1個(gè)n階的方陣Y來(lái)存儲(chǔ)特征元中的工藝約束關(guān)系。如果2個(gè)特征元之間存在工藝約束，特征元i必須在特征元j之前加工，則元素yij的值為1，如不存在工藝約束，則yij的值為0。即

工藝路線排序優(yōu)化的本質(zhì)是在滿足工藝約束集的前提下，對(duì)各個(gè)特征元進(jìn)行排列，形成一條具有可操作性的加工工藝路線，一般采用迭代求解。問(wèn)題的解空間可以定義 Ω ={S1,S2,S3,···Sk,Sm}，其中Sk={fk1,fk2,···,fki,···,fkn}為任意一個(gè)滿足工藝約束的備選解。工藝路線排序的求解過(guò)程就是在整個(gè)搜索區(qū)間尋找1個(gè)特征元序列 Sk∈Ω，使其在滿足工藝約束的前提下實(shí)現(xiàn)效率、效益等指標(biāo)最優(yōu)。

1.2 工藝路線評(píng)價(jià)模型

工藝路線評(píng)價(jià)是利用計(jì)算機(jī)進(jìn)行加工工藝排序優(yōu)化的關(guān)鍵問(wèn)題之一。按照工序集中原則，在符合工藝約束的前提下，以機(jī)床、裝夾和刀具更換次數(shù)最小為優(yōu)化目標(biāo)，采用加權(quán)法定義工藝路線評(píng)價(jià)模型工藝序列的評(píng)價(jià)函數(shù)，將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題，如式（2）所示。

式中：fm、fs、ft分別表示1個(gè)工步序列中相鄰特征元之間機(jī)床、裝夾和刀具的總更換次數(shù)；wm、ws、和wt分別表示機(jī)床、裝夾和刀具變換次數(shù)的權(quán)重系數(shù)；Mi、Si、Ti，分別為第i個(gè)工步所需要使用的機(jī)床、夾具和刀具。函數(shù)t(x,y)的形式為

2 融合帝國(guó)競(jìng)爭(zhēng)算法與遺傳算法的求解方法

工藝排序優(yōu)化問(wèn)題屬于有約束TSP問(wèn)題，難以采用解析法精確求解。采用融合帝國(guó)競(jìng)爭(zhēng)算法與遺傳算法的方法進(jìn)行求解，利用帝國(guó)競(jìng)爭(zhēng)算法在全局搜索時(shí)不受初始種群影響的特性和遺傳算法的快速收斂能力，將帝國(guó)競(jìng)爭(zhēng)算法的較優(yōu)輸出的加工序列作為遺傳算法的初始種群，提升算法的尋優(yōu)能力。具體流程如圖1所示。

圖1 基于混合算法的工藝排序優(yōu)化流程圖

混合算法的運(yùn)算步驟如下。

步驟一：計(jì)算開始之初設(shè)定所需要的各個(gè)數(shù)據(jù)；

步驟二：初始化帝國(guó)競(jìng)爭(zhēng)算法種群；

步驟三：以設(shè)置的起始算法的最大迭代次數(shù)為界限，判斷起始算法是否完成迭代，且是否連續(xù)100代最優(yōu)解無(wú)變化或者變化不大；若達(dá)到規(guī)定的迭代次數(shù)目標(biāo)，若未達(dá)到設(shè)置的迭代次數(shù)，則繼續(xù)運(yùn)行帝國(guó)競(jìng)爭(zhēng)算法，若未達(dá)到，則從起始算法所輸出的較優(yōu)序列中，選取λ個(gè)的序列個(gè)體參與下面遺傳算法的運(yùn)行，λ取值需大于編碼長(zhǎng)度；

步驟四：同樣根據(jù)混合算法有無(wú)完成開始所設(shè)置的混合算法最大迭代次數(shù)來(lái)界定是否完成計(jì)算，且是否連續(xù)幾代最優(yōu)解無(wú)變化或者變化不大，如果兩種條件都滿足的前提下，即視為該算法完成迭代計(jì)算，將最優(yōu)值進(jìn)行輸出，若未完成，在滿足結(jié)束條件前繼續(xù)執(zhí)行迭代。

2.1 個(gè)體編碼及適應(yīng)度函數(shù)

帝國(guó)競(jìng)爭(zhēng)算法中的國(guó)家和遺傳算法中的染色體均代表迭代計(jì)算過(guò)程的個(gè)體解，采用自然數(shù)進(jìn)行編碼。1個(gè)特征元由1個(gè)自然數(shù)表示，個(gè)體編碼長(zhǎng)度即為特征元個(gè)數(shù)，編碼順序即表示零件的工步順序。

個(gè)體解的適應(yīng)度函數(shù)定義如下：

式 中 ：Sk表 示 第k個(gè) 個(gè) 體 解 ，wm、wt、wi和wp分 別 表示Sk中機(jī)床、裝夾、刀具變換次數(shù)和懲罰函數(shù)的權(quán)重系數(shù)；n表示特征元數(shù)目；fm,k′，fs,k′，ft,k′分別表示Sk中機(jī)床、刀具和裝夾更換次數(shù)歸一化處理結(jié)果；fp為懲罰函數(shù)，表示對(duì)違反工藝約束的解進(jìn)行懲罰，a表示加工序列違反工藝約束的數(shù)量，cur_gen表示為當(dāng)前的迭代計(jì)算代數(shù)，max_gen表示為設(shè)置的最大迭代次數(shù)。

求解過(guò)程的優(yōu)化目標(biāo)是全局范圍內(nèi)搜索1個(gè)能最大限度滿足排序問(wèn)題約束的特征元集合，使Feval(Sk)的值最大化。即

2.2 基于帝國(guó)競(jìng)爭(zhēng)算法的較優(yōu)工藝序列求解

用帝國(guó)競(jìng)爭(zhēng)算法中的一個(gè)國(guó)家表示1個(gè)工步序列，每個(gè)國(guó)家的編碼序列對(duì)應(yīng)1個(gè)工步序列。假設(shè)該零件特征工步有n步，其可表達(dá)為

每個(gè)國(guó)家的勢(shì)力大小則用適應(yīng)度函數(shù)來(lái)描述，如

（1）初始化帝國(guó)

首先在全局范圍的搜索區(qū)間內(nèi)，由算法隨機(jī)產(chǎn)生N個(gè)國(guó)家，按照權(quán)勢(shì)大小將這N個(gè)國(guó)家分為Nimp個(gè)帝國(guó)和Ncol個(gè)殖民地[11]。

將計(jì)算得到的帝國(guó)勢(shì)力值用于計(jì)算帝國(guó)的標(biāo)準(zhǔn)勢(shì)力，得

根據(jù)每個(gè)帝國(guó)的標(biāo)準(zhǔn)勢(shì)力，計(jì)算初始每個(gè)帝國(guó)擁有多少個(gè)殖民地，如

式中：Nci是i號(hào)帝國(guó)擁有的殖民地個(gè)數(shù)。Ncol是殖民地的總數(shù)，round定義為取整函數(shù)。

（2）殖民地同化操作

殖民地同化的本質(zhì)是使殖民地位置能向帝國(guó)靠近。采用雙點(diǎn)交叉法進(jìn)行同化操作，在帝國(guó)工步序列中隨機(jī)選取2個(gè)交叉點(diǎn)，將2個(gè)交叉點(diǎn)之間的工步編碼復(fù)制到新殖民序列相應(yīng)位置，最后將殖民地序列中未被復(fù)制的工步編碼按順序依次復(fù)制到新殖民地序列，形成新的殖民地序列。如圖2所示，假設(shè)1個(gè)零件的特征有8個(gè)加工單元，首先隨機(jī)生成2個(gè)交叉位置點(diǎn)2、5，將帝國(guó)序列中位置3、4、5上的編碼“5”、“4”、“8”進(jìn)行復(fù)制，然后從殖民地序列中未被復(fù)制的編碼“2”、“3”、“1”、“1”、“6”、“7”按順序依次復(fù)制到其他編碼位，形成新殖民地。

圖2 基于雙點(diǎn)交叉法的殖民地同化示意圖

（3）殖民地革命操作

殖民地革命的過(guò)程類似于遺傳算法中的變異操作，隨機(jī)對(duì)某個(gè)殖民地采用交換工步操作或移動(dòng)工步操作。交換工步的原理如圖3所示，隨機(jī)選擇兩個(gè)位置點(diǎn)，并將相應(yīng)位置點(diǎn)的工步內(nèi)容進(jìn)行交換生成新的加工序列。移動(dòng)工步的原理如圖4所示，隨機(jī)選擇2個(gè)位置點(diǎn)，將其中1個(gè)位置點(diǎn)的工步編碼移動(dòng)插入到另1個(gè)位置點(diǎn)之前。殖民地革命后，如果新殖民地代價(jià)值比其所屬帝國(guó)小，則革命成功，交換兩個(gè)國(guó)家的地位。

圖3 交換工步示意圖

圖4 移動(dòng)工步示意圖

（4）帝國(guó)競(jìng)爭(zhēng)操作

帝國(guó)競(jìng)爭(zhēng)的對(duì)象是最弱帝國(guó)的最弱殖民地。首先需要計(jì)算1個(gè)帝國(guó)的綜合勢(shì)力，包括其自身勢(shì)力與全部殖民地勢(shì)力的總和。帝國(guó)的總勢(shì)力值為

式中：Tci表示第i個(gè)帝國(guó)集團(tuán)的總勢(shì)力；impi表示第i個(gè)帝國(guó)集團(tuán)中的帝國(guó)；colij表示由第i個(gè)帝國(guó)統(tǒng)治的第j個(gè)殖民地；ζ為正數(shù)，表示殖民地對(duì)整個(gè)帝國(guó)勢(shì)力的影響程度，取值一般在[0.1，0.5][12]。

將1個(gè)勢(shì)力最小的帝國(guó)集團(tuán)中的殖民地視為各個(gè)帝國(guó)之間競(jìng)爭(zhēng)的目標(biāo)，勢(shì)力越大的國(guó)家則越有機(jī)會(huì)獲得這些殖民地。各帝國(guó)獲得該最弱殖民地概率是

所有帝國(guó)集團(tuán)獲得該殖民地的概率可表示為P=[p1,p2,…,pNimp]，再構(gòu)造1個(gè)與P同維的隨機(jī)向量R，R=[r1,r2,…,rNimp]，其中r∈U(0,1)。構(gòu)造向量D，D=P-R，選擇向量D中元素最大值的索引為侵占該殖民地的帝國(guó)主義者。

（5）帝國(guó)的滅亡

伴隨著帝國(guó)集團(tuán)之間的競(jìng)爭(zhēng)，勢(shì)力最強(qiáng)的帝國(guó)集團(tuán)最終將所有弱于它們的帝國(guó)以及殖民地侵略攻占完成，最后只存在1個(gè)帝國(guó)主義國(guó)家集團(tuán)，該帝國(guó)集團(tuán)將剩下所有的國(guó)家進(jìn)行統(tǒng)治，該最強(qiáng)的帝國(guó)的位置即為算法計(jì)算得出的最優(yōu)解。

2.3 基于遺傳算法的工藝序列優(yōu)化

從帝國(guó)競(jìng)爭(zhēng)算法求解的結(jié)果中選擇一部分較優(yōu)工步序列作為遺傳算法的初始種群，進(jìn)行進(jìn)一步尋優(yōu)。涉及的相關(guān)算子如下：

（1）選擇

選擇采用輪盤對(duì)賭法進(jìn)行操作，根據(jù)個(gè)體適應(yīng)度值的高低來(lái)計(jì)算選擇概率進(jìn)行染色體篩選，通常而言，染色體適應(yīng)度值越優(yōu)良的，被選擇的概率要更高，其機(jī)理是由于概率不斷累積，適應(yīng)度大的個(gè)體更易于在遺傳過(guò)程中做出正確選擇。

（2）交叉

交叉是指2個(gè)染色體完成交換部分算子的操作，并生成新的染色體的過(guò)程。為了防止在2個(gè)父代染色體組型的交叉操作出現(xiàn)無(wú)效的染色體后代，采用單點(diǎn)交叉進(jìn)行操作，如圖5所示。

圖5 遺傳算法中交叉操作

在2條父代染色體上隨機(jī)產(chǎn)生1個(gè)相同位置的交叉點(diǎn)，將父代染色體p1交叉點(diǎn)左邊部分的工步內(nèi)容及位置復(fù)制進(jìn)子代染色體s1中，將父代染色體p2交叉點(diǎn)右邊部分未復(fù)制的工步按順序進(jìn)行復(fù)制，形成新的染色體s1，子染色體s2構(gòu)造原理與s1相同。

（3）變異

在遺傳算法求解過(guò)程中，為避免目標(biāo)陷入局部最優(yōu)且能保持染色體序列的多樣化，一般采用突變操作來(lái)產(chǎn)生新的染色體種群。任意挑選染色體及位置發(fā)生基因突變，將變異點(diǎn)位的2個(gè)工步算子內(nèi)容及位置進(jìn)行交換，產(chǎn)生新的染色體，保證其求解過(guò)程中的全面性。具體操作如圖6所示。

圖6 遺傳算法中變異操作

3 實(shí)例分析

以萬(wàn)向節(jié)滑動(dòng)叉為實(shí)例進(jìn)行分析，毛坯種類為鍛件，材料為45號(hào)鋼，零件三維圖如圖7所示，零件二維圖及基本尺寸如圖8所示。

圖7 萬(wàn)向節(jié)滑動(dòng)叉零件三維圖

圖8 萬(wàn)向節(jié)滑動(dòng)叉二維主視圖

將工件特征進(jìn)行區(qū)分歸類，并將對(duì)應(yīng)特征的加工工藝鏈進(jìn)行分解，構(gòu)成算法可控制的特征加工單元集合，并對(duì)特征加工單元實(shí)行自然數(shù)編碼，如表1所示。

表1 加工特征信息及編碼

當(dāng)裝夾面為FS1時(shí)，定位基準(zhǔn)為左端面、?65外圓面，定位面為FS2時(shí)，定位基準(zhǔn)為右端面、?62外圓面，裝夾面為FS3時(shí)，定位基準(zhǔn)為花鍵孔、右端面。

根據(jù)約束條件來(lái)分析強(qiáng)制性約束集合：將不進(jìn)行加工的?65外圓面為粗基準(zhǔn)，先進(jìn)行Op2；Op17先于 Op4、Op5、Op6、Op7、Op11和 Op12；Op11先于 Op3、Op4、Op5以及 Op6；Op3、Op4、Op5、Op6先于Op12。

Op18、Op19 先于 Op20；Op3、Op4先于 Op7；Op8先于Op9；Op8先于Op10（先孔后螺紋）；Op13、Op14先于Op15、Op16（先面后螺紋）；Op18、Op19先于Op17（先孔后花鍵）；特征屬性中嚴(yán)格的順序約束如：Op3、Op4、Op5、Op6。

根據(jù)工藝約束，建立1個(gè)21×21維的加工序列約束矩陣，如表2所示。

表2 加工優(yōu)先級(jí)矩陣

分析優(yōu)化約束集，機(jī)床和刀具由用戶來(lái)進(jìn)行選擇，機(jī)床類型集以及刀具集由表3、4所示。

表3 機(jī)床集

表4 刀具集

編碼由表得出長(zhǎng)度為21，適應(yīng)度函數(shù)權(quán)重系數(shù)wm=0.4、ws= 0.2、wt=0.1、wp=0.3。設(shè)定帝國(guó)競(jìng)爭(zhēng)算法中，初始國(guó)家數(shù)為50，殖民地影響系數(shù)ζ=0.1，最大迭代次數(shù)為500。遺傳算法中初始種群數(shù)為30，交叉率為0.8，變異率為0.02，最大迭代次數(shù)為500，混合算法設(shè)置最大迭代次數(shù)為1 000。

圖9為MATLAB仿真結(jié)果圖，可以很明顯地得出混合算法在求解加工工藝排序中，僅經(jīng)過(guò)119次左右迭代即可完成收斂，且目標(biāo)函數(shù)值要遠(yuǎn)大于只靠單一帝國(guó)競(jìng)爭(zhēng)算法和單一遺傳算法進(jìn)行求解所得目標(biāo)函數(shù)值。所求得最優(yōu)的加工工步序列如下：2→1→13→14→15→16→18→19→21→20→17→11→3→4→5→6→8→12→7→10→9。

圖9 MATLAB仿真結(jié)果圖

經(jīng)過(guò)該算法運(yùn)行10次，3種算法的適應(yīng)度以及迭代次數(shù)結(jié)果如表5所示。

表5 3種算法結(jié)果對(duì)比

混合算法與單獨(dú)的優(yōu)化算法相比較，明顯收斂更快且最終結(jié)果的適應(yīng)度值要更高，可以證明混合算法在加工工藝排序中的優(yōu)化效果要更好。主要原因在于，混合算法充分發(fā)揮了帝國(guó)競(jìng)爭(zhēng)算法與遺傳算法各自的優(yōu)勢(shì)，將帝國(guó)競(jìng)爭(zhēng)算法不受初始序列影響的快速全局搜索能力以及遺傳算法中種群的多樣性兩者相結(jié)合，達(dá)到優(yōu)化目的且具有較高的優(yōu)化效率。

4 結(jié)語(yǔ)

針對(duì)零件加工工藝排序問(wèn)題，以最小化機(jī)床、裝夾以及刀具變更次數(shù)為優(yōu)化目標(biāo)，構(gòu)建了工藝排序的數(shù)學(xué)模型，提出了融合帝國(guó)競(jìng)爭(zhēng)與遺傳算法的加工工藝序列排序優(yōu)化求解方法。通過(guò)實(shí)驗(yàn)對(duì)比分析，可得出以下結(jié)論：混合算法的收斂速度和所求解的適應(yīng)度值均優(yōu)于各自單獨(dú)的優(yōu)化算法，在尋優(yōu)效率上有很大程度的提升，證明了該優(yōu)化方法的有效性和實(shí)用性。同時(shí)，文中建立的工藝路線評(píng)價(jià)模型未考慮能耗與機(jī)床負(fù)荷等問(wèn)題，有待后續(xù)進(jìn)一步深入研究。