基于遺傳算法的拆卸序列規劃研究

劉 奧，周重威，李明宇

（1.華中科技大學機械科學與工程學院，湖北武漢430074；2.寧波賽維思機械有限公司，浙江寧波315135）

拆卸是采用一定的工具和手段，解除對零件造成約束的各種聯接，將產品零部件逐個分離的過程。拆卸序列規劃，本質上是一個NP 難題，當裝配體中零件數量增加時，可拆卸序列的數量也會呈現出指數級的增長。

在解決拆卸序列規劃問題時，大多數學者利用網絡圖結合圖論和相關搜索方法，來處理此類問題。

Veerakamolmal 和Gupta 于1997年提出通過產品的模塊化的特點以最小化拆裝時間和費用，得出一個高效的拆裝序列[1]。

Gungor 和Gupta 提出一個拆裝的啟發式算法[2]。

Moore 等用Petri 網對復雜產品優先關系建模來進行拆裝過程規劃[3]。

在國內，江吉彬、劉志峰等，提出一種基于工程語義信息的規劃算法，解決拆卸序列規劃理論算法存在的求解空間過大的問題[4]。

趙樹恩和李玉玲采用將模糊推理Petri 網與矩陣運算相結合的形式化推理算法，實現產品拆卸序列決策[5]。

為得到滿足產品要求的拆卸序列，且提高拆卸序列規劃的效率及實用價值，本文依據關聯矩陣和干涉矩陣，產生滿足幾何約束、且經初次優化的裝配序列。其后，應用遺傳算法優化上述初次優化的裝配序列，以得到滿足生產實際的拆卸序列規劃。

1 拆卸序列優化模型

1.1 簡化拆卸優化模型

本文主要從3個方面簡化拆卸模型。

（1）緊固件及其附件的簡化。在裝配或拆卸的過程中，緊固件及其附件，可以看成普通零件之間的約束。當完成約束或解除約束時，緊固件及其附件即完成拆除。為保證零件間的約束關系完全，將部分標準件消隱，且部分標準件與相接觸的零件相固連。

（2）裝配體子裝配的分離。對子裝配體的定義，直接影響到子裝配體的分離。對子裝配體的定義如下：

子裝配體中零件之間的聯接關系，使子裝配體成為一個不可自發分離的子結構，即子裝配體為穩定結構；

子裝配體中零件裝配完畢后,不影響原裝配體中其余零件的裝配。

（3）基礎件的選擇。基礎件作為最后拆卸的零件，對其優先選擇，可以縮小搜索空間。但是基礎件仍然參與聯接矩陣與干涉矩陣的生成，會對拆卸產生約束作用。

1.2 聯接矩陣

產品是通過零件以一定的裝配關系聯接而成的具有穩定結構的裝配體。本文主要討論兩類基本約束關系：接觸關系與可拆卸聯接關系。

設裝配體P 由N個零件組成，用

來表示所有零件的集合，

W={w1，w2，…wm…wN|wm綴P，且wm互異}

表示一條拆卸序列。

用布爾量B =(pi,pj)表示零件pi與零件pj的聯接關系。

對于B=(pi,pj)有如下的約定：

1.3 干涉矩陣

干涉是拆卸過程中零件之間的空間制約關系及其相關性的反應。當拆卸方向選擇與笛卡兒直角坐標系相同時，零件的拆卸干涉關系，指的是若產品中零件pi對零件pj的拆卸在 K（K =±X，±Y，±Z）方向上形成干涉關系，則表示在零件pi拆卸完成前，零件pj無法沿K方向拆卸。干涉關系可用干涉矩陣G 來表示，即：

其中，

gijk表示零件pi對零件pj在K方向拆卸的干涉情況。

gijk=0表示無干涉，gijk=1表示干涉存在。

規定當gijk中i=j 時，gijk=0。

由于gijk在某個坐標軸正方向與gjik相同坐標軸反方向有相同值。

1.4 拆卸序列的生成

滿足幾何約束的拆卸序列流程圖，如圖1所示。通過識別標準緊固件，可獲得各零件間的可拆卸聯接關系。

圖1 序列生成流程圖

本文中，當存在可拆卸緊固聯接時，必須保留標準緊固件（如螺栓）而消隱其附件（如螺帽、墊圈等）,且將標準緊固件與其后拆除的第一個零件視為一個零件。

拆卸序列生成時，參考遺傳算法中輪盤賭的方式，優先選取與被拆零件有聯接關系的零件作為后續拆卸對象。其中可拆卸聯接關系作為第一選擇，接觸聯接關系作為第二選擇，無接觸聯接關系作為第三選擇，通過依次選擇滿足要求的零件，可保證拆卸序列得到優化。

2 基于遺傳算法的拆卸序列優化

本文在遺傳運算的過程中，考慮交叉與變異后拆卸序列的幾何可行性，對于不滿足幾何可行性的拆卸序列，將其舍棄，直到得到足夠數量的滿足幾何可行性的子代。

2.1 適應度函數的構造

拆卸時間的長短，在一定程度上反應出拆卸的效率與拆卸的復雜程度。因此，本文從縮短拆卸時間的目標，來優化拆卸的序列。考慮的主要因子有：拆卸方向變換時間、拆卸工具與夾具變換時間。

（1）拆卸方向變換時間。ot(i,w)表示序列W 中零件pi的重定向時間，定義如下：

其中，t1為拆卸方向旋轉90°時的拆卸方向變換時間。OT(i,w)表示序列w 中前I個零件的重定向時間之和

（2）拆卸工具變換時間。tt(i,w)表示序列W 中拆卸第i個零件時的拆卸工具變換時間。一般而言，工具之間的變換時間，隨著工具的不同而不同。為簡化，本文假定工具間的變換時間相同，為t2，則有

TT(i,w)表示序列W 中前i個零件拆卸時的拆卸工具變換之和

（3）拆卸夾具變換時間。拆卸工具與拆卸夾具基本相同，同理可以定義t3、ct(i,w)、CT(i,w)。

除去零件的基本拆卸時間，拆卸序列W 中前i個零件拆卸所需要的時間為DT(i,w),則有

為保證適應度值隨時間增加而減小，且適應度函數為正值,定義適應度函數為

其中，C為常數，且C叟DT(i,w)。

2.2 優化算法

（1）編碼。本文采用實數編碼的方法，在基因組中表達裝配體中零件的信息，利用4位碼編碼。

（2）選擇操作。本文采用輪盤賭的方式，來執行選擇操作，即適應度較高的拆卸序列被選擇參與交叉與變異的概率較高。

（3）交叉操作與變異操作。為簡化計算，本文利用吳昊所使用的交叉算子[6]與劉誠提出的變異算子[7]完成交差與變異操作。

（4）拆卸序列幾何可行性判斷。利用干涉矩陣，對序列中零件依次檢測其可拆性，若出現某零件與未拆除零件發生干涉，則摒棄此條拆卸序列，重新進行交叉與遺傳操作，直到生成滿足幾何可行性的拆卸序列。

本文遺傳算法的操作流程圖如圖2。

圖2 遺傳算法流程圖

3 實例

圖3是某裝配體的裝配示意圖，該裝配體由11個零件組成，選擇零件11 作為基礎件。

圖3 某產品裝配圖

為優化該裝配體的拆卸序列，給定以下初始條件：

初始種群數popsize為10、交叉概率pc=0.8、染色體內部突變的概率pm=0.05，C=500。

利用聯接矩陣與干涉矩陣，通過Matlab 編程，得到滿足幾何約束的部分拆卸序列如下：

計算得到的每一代的最大適應度值如圖4所示。

圖4 子代中最大適應度值

仿真生成的拆卸序列如表1所示。

表1 拆卸序列規劃結果

4 結束語

本文獲取了聯接矩陣和干涉矩陣，構建了產品拆卸模型。利用干涉矩陣和聯接矩陣，產生滿足幾何約束，且經過初次優化的拆卸序列。利用優化的遺傳算法，對拆卸序列進行了優化。最后，利用一個實例，來驗證了本方法的可行性以及此種遺傳算法的可行性。

[1]Veerakamolmal P，Gupta S M，McLean C R.Disassembly process planning [C].In:First International Conference on Engineering Design and Automation，Bangkok：Thailand,1997.

[2]Gungor A，Gupta SM.An Evaluation Methodology for Disassembly Processes [J].Computers and Industrial Engineering，1997，33(1)：329-332.

[3]Moore K E，Gungor A，Gupta S M.Petri Net Approach to Disassembly Process Planning for Products with Complex AND/OR Precedence Relationships [J].European Journal of Operational Research，2001，135(2)：428-449.

[4]江吉彬，劉志峰，劉光復.基于工程語義信息的拆卸序列規劃算法研究[J].計算機集成制造系統，2006，12(4)：625-629.

[5]趙樹恩，李玉玲.模糊推理Petri 網及其在產品拆卸序列決策中的應用[J].控制與決策報，2005，20(10)：1181-1184.

[6]吳 昊，左洪福.基于改進遺傳算法的產品拆卸序列規劃[J].中國機械工程，2009，20(6)：699-703.

[7]劉 誠，付宜利.引入基因修復技術的產品裝配序列規劃方法[J].哈爾濱工業大學學報，2010，42（1）：79-81.