融合帝國競爭與遺傳算法的零件加工工藝排序方法＊

李書涵 周學良 冷杰武

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

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

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

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

1.1 問題描述

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

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

（1）先基準，后其他，即先加工基準特征再加工其他特征。

（2）先粗后精，即先進行粗加工，后進行半精加工和精加工。

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

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

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

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

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

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

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

1.2 工藝路線評價模型

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

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

2 融合帝國競爭算法與遺傳算法的求解方法

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

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

混合算法的運算步驟如下。

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

步驟二：初始化帝國競爭算法種群；

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

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

2.1 個體編碼及適應度函數(shù)

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

個體解的適應度函數(shù)定義如下：

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

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

2.2 基于帝國競爭算法的較優(yōu)工藝序列求解

用帝國競爭算法中的一個國家表示1個工步序列，每個國家的編碼序列對應1個工步序列。假設該零件特征工步有n步，其可表達為

每個國家的勢力大小則用適應度函數(shù)來描述，如

（1）初始化帝國

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

將計算得到的帝國勢力值用于計算帝國的標準勢力，得

根據(jù)每個帝國的標準勢力，計算初始每個帝國擁有多少個殖民地，如

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

（2）殖民地同化操作

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

圖2 基于雙點交叉法的殖民地同化示意圖

（3）殖民地革命操作

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

圖3 交換工步示意圖

圖4 移動工步示意圖

（4）帝國競爭操作

帝國競爭的對象是最弱帝國的最弱殖民地。首先需要計算1個帝國的綜合勢力，包括其自身勢力與全部殖民地勢力的總和。帝國的總勢力值為

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

將1個勢力最小的帝國集團中的殖民地視為各個帝國之間競爭的目標，勢力越大的國家則越有機會獲得這些殖民地。各帝國獲得該最弱殖民地概率是

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

（5）帝國的滅亡

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

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

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

（1）選擇

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

（2）交叉

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

圖5 遺傳算法中交叉操作

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

（3）變異

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

圖6 遺傳算法中變異操作

3 實例分析

以萬向節(jié)滑動叉為實例進行分析，毛坯種類為鍛件，材料為45號鋼，零件三維圖如圖7所示，零件二維圖及基本尺寸如圖8所示。

圖7 萬向節(jié)滑動叉零件三維圖

圖8 萬向節(jié)滑動叉二維主視圖

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

表1 加工特征信息及編碼

當裝夾面為FS1時，定位基準為左端面、?65外圓面，定位面為FS2時，定位基準為右端面、?62外圓面，裝夾面為FS3時，定位基準為花鍵孔、右端面。

根據(jù)約束條件來分析強制性約束集合：將不進行加工的?65外圓面為粗基準，先進行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（先孔后花鍵）；特征屬性中嚴格的順序約束如：Op3、Op4、Op5、Op6。

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

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

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

表3 機床集

表4 刀具集

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

圖9為MATLAB仿真結果圖，可以很明顯地得出混合算法在求解加工工藝排序中，僅經(jīng)過119次左右迭代即可完成收斂，且目標函數(shù)值要遠大于只靠單一帝國競爭算法和單一遺傳算法進行求解所得目標函數(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仿真結果圖

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

表5 3種算法結果對比

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

4 結語

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