基于改進遺傳算法的異步并行拆卸序列規(guī)劃

孫嫻靜，唐秋華，鄧明星

(武漢科技大學 1.冶金裝備及其控制教育部重點實驗室；2.機械傳動與制造工程湖北省重點實驗室；3.汽車與交通工程學院，湖北 武漢 430081)

拆卸是將產(chǎn)品或裝配體進行拆解，獲取目標零部件的過程。與焚燒、掩埋等其他報廢產(chǎn)品處理方法相比，通過拆卸來獲取可直接重用或可修復的零部件，實現(xiàn)資源的再利用，故而拆卸具有顯著的經(jīng)濟和環(huán)境優(yōu)勢，在報廢產(chǎn)品的再利用和再制造過程中具有重要的地位。

拆卸序列規(guī)劃是指根據(jù)產(chǎn)品中零部件之間的幾何結構、功能等一些預定的性能指標探索確定合理可行的拆卸序列，并從中選擇最優(yōu)的序列以指導產(chǎn)品的拆卸，達到預期的拆卸目標。根據(jù)拆除零部件的邏輯順序，拆卸可以分為兩大類：順序拆卸和并行拆卸。因此，拆卸序列規(guī)劃也可以分為順序拆卸規(guī)劃和并行拆卸規(guī)劃。并行拆卸分為同步并行拆卸和異步并行拆卸。

到目前為止，已經(jīng)有很多學者對順序拆卸規(guī)劃問題進行了研究，開發(fā)出許多模型和方法。但隨著技術的發(fā)展，對拆卸時效的要求逐漸提高，并行拆卸序列規(guī)劃問題越來越受到學者的關注與研究。Zhang等[1]針對性地建立拆卸混合圖模型來解釋4種不同的零部件之間的結構連接，然后提出協(xié)同拆卸層次樹的生成方法，通過一種基于兩用戶定義變量的分支定界算法計算出并行拆卸序列規(guī)劃的最小工作時間。隨后，Zhang等[2]基于模糊粗糙集，定義和推導了裝配約束因子、拆卸優(yōu)先因子、拆卸時間因子、拆卸工具因子和組合類型因子等5個拆卸因子，建立了并行拆卸的模糊?粗糙集映射模型，利用模糊?粗糙集映射模型生成最優(yōu)的并行拆卸序列。Smith等[3]利用模塊化設計理論將待拆卸的零件轉化為模塊，并根據(jù)遞歸規(guī)則生成可行的拆卸序列，然后利用遺傳算法尋找最優(yōu)的并行拆卸序列。Ren等[4]創(chuàng)建拆卸層次樹形圖來描述并行拆卸過程，并提出一種多目標離散人工蜂群算法，使求得的并行拆卸序列規(guī)劃的拆卸時間最小化，利潤最大化。

然而，以上文獻主要針對同步并行拆卸序列規(guī)劃，要求操作者同時開始拆卸操作，從而導致空閑時間多，作業(yè)效率低。因此，本文針對異步并行拆卸序列規(guī)劃問題，提出改進遺傳算法進行求解。

1 異步并行拆卸序列規(guī)劃

異步并行拆卸是并行拆卸方式中的一種。異步并行拆卸是指允許操作者完成當前拆卸任務后，在不違背相關約束的情況下即時開始下一個拆卸任務，不必等待所有操作者都完成任務[5]。在并行拆卸序列規(guī)劃中，操作者開始執(zhí)行拆卸操作的時間也尤為重要，會對產(chǎn)品拆卸的完成時間以及拆卸成本產(chǎn)生不小的影響。異步并行拆卸節(jié)省了部分操作者等待其他拆卸任務完成的空閑時間，減少了完成拆卸所需要的時間以及相關成本，更具有研究價值。

1.1 優(yōu)先關系約束

優(yōu)先關系表示產(chǎn)品零部件之間的拆卸先后順序，根據(jù)邏輯關系對其進行劃分，可以分為“與優(yōu)先”關系和“或優(yōu)先”關系?！芭c優(yōu)先”關系指只有拆除所有緊前優(yōu)先零部件，零件i才能被拆除。若同時有多個零部件對零件i具有優(yōu)先關系，拆除其中某一個零部件，零件i即可拆卸，則零件i與其緊前優(yōu)先零部件構成“或優(yōu)先”關系[6-7]。

圖1為某產(chǎn)品的優(yōu)先關系示意圖。其中，i={1,2,···,10}表示待拆卸任務，每個拆卸任務表示要拆卸的零部件，其優(yōu)先關系由優(yōu)先級高的零件指向優(yōu)先級低的零件。在圖中，用有向點虛線邊連接的任務2、3與任務1、8、9、10之間構成 “或優(yōu)先”關系。若零部件2被拆卸，零部件1、3、8、9、10均可被拆卸。其余有向實邊接連的拆卸任務接觸約束關系為“與優(yōu)先”關系。

圖1 某待拆卸產(chǎn)品的優(yōu)先關系示意圖Figure 1 Schematic diagram of the priority relationship of a product to be disassembled

通常，在某一拆卸方向上的各零部件之間的優(yōu)先約束關系總是嚴格對接的，當出現(xiàn)“或優(yōu)先”關系則說明要想拆卸某一產(chǎn)品，至少有2種不同的拆卸方式，即至少有2種不同的拆卸方向。因此，在含有“或優(yōu)先”關系的情況下，可以不用考慮產(chǎn)品的拆卸方向，在一定程度上簡化了問題。

1.2 工作區(qū)域沖突約束

在異步并行拆卸序列規(guī)劃中，通常是多個操作者共同拆卸一個產(chǎn)品，由于各零部件間存在復雜的裝配關系，會存在當某個操作者拆卸某一零件時會占用另一個操作者的拆卸工作區(qū)域，使得另一個操作者的拆卸工作無法進行的問題。這時，2個操作者無法同時完成各自的拆卸任務，這種情況稱為2個零部件之間存在工作區(qū)域沖突關系。

為了方便表達，可以像優(yōu)先關系矩陣一樣構造一個沖突矩陣C來描述。

2 加入路徑重連的改進遺傳算法

2.1 編碼

由于異步并行拆卸序列規(guī)劃問題不僅涉及到每個任務之間的約束關系，與操作者也相關，因此采用雙向量列表結構編碼更加合適，個體v由拆卸任務向量v1和 操作者向量v2組成。拆卸任務向量v1={i1,i2,···,ik}，向量中每個元素代表一個待拆卸任務，由1到K的整數(shù)表示，K為待拆卸產(chǎn)品的零部件總數(shù)。操作者向量v2={r1,r2,···,rN}，向量中每個元素代表執(zhí)行向量v1中對應的拆卸任務的操作者，由1到N的整數(shù)表示，N為操作者數(shù)量。

在確定遺傳算法的編碼方式之后，需要根據(jù)問題特點生成初始化種群，以本文1.1節(jié)中提出的問題為例進行說明。拆卸任務向量v1只與待拆卸產(chǎn)品的各零部件有關。為方便解碼，需要在種群初始化時保證向量v1的可行性，即嚴格遵循各零件之間的優(yōu)先關系約束。由優(yōu)先關系矩陣可知，當優(yōu)先關系矩陣P中 第j列中的元素均為0時，待拆卸任務j當前可拆卸，不受其余零件的優(yōu)先約束。將得到的可拆卸任務依次存入向量v1，不斷循環(huán)直至找出所有拆卸任務，此時可得到拆卸任務向量v1，操作者向量v2可以由操作者數(shù)量通過隨機程序獲得。初始化種群具體步驟如下。

步驟 1輸入優(yōu)先關系矩陣P，創(chuàng)建空向量v1和空集合t1。

步驟 2若矩陣P為空矩陣，則轉到Step7，否則執(zhí)行Step 3。

步驟 3找出矩陣P中 元素全為0的列，將列對應的拆卸任務存入集合t1中。

步驟 4從集合t1中隨機選擇一個待拆卸任務放入到向量v1最左端中。

步驟 5更新矩陣P，將已拆卸任務的行與列刪除，若刪除的元素中包含“或優(yōu)先”關系，則同時對與之關聯(lián)的其他“或優(yōu)先”關系元素進行修改。

步驟 6將集合t1中已拆卸任務刪除，返回Step 2。

步驟 7根據(jù)操作者數(shù)量隨機生成向量v2。

步驟 8輸出向量v1和 向量v2。

2.2 解碼

在本文研究的異步并行拆卸序列規(guī)劃問題中，拆卸的目標為拆卸完成時間最小，即最小化最大拆卸完成時間，類似于JSP問題的最大完工時間。與JSP問題不同，在異步并行拆卸序列規(guī)劃問題中還要考慮“與/或優(yōu)先”關系和操作者的拆卸工作區(qū)域沖突問題。 “或優(yōu)先”關系存在不定向性，在未開始拆卸之前，多個具有“或優(yōu)先”關系的待拆卸任務具有同樣的拆卸優(yōu)先級，無法選擇哪個任務先進行拆卸。

因此，在解碼開始之前，要將拆卸任務之間的“或優(yōu)先”關系解除。仍以1.1節(jié)中的問題為例，通過編碼，該產(chǎn)品所有拆卸任務的拆卸順序已經(jīng)出來，可以修改優(yōu)先關系矩陣P，解除拆卸任務之間的“或優(yōu)先”關系。 假設個體編碼v1={3,9,2,10,8,4,7,1,5,6}，則可以看作拆卸任務3對任務1、8、9、10具有“與優(yōu)先”關系約束，任務2不再對后續(xù)任務具有“或優(yōu)先”關系約束。對應的，優(yōu)先關系矩陣可以修改為P21，P28，P29，P2,10為 0；P31，P38，P39，P3,10為1，其余保持不變。

解碼是根據(jù)種群個體編碼計算出每個個體對應拆卸序列的最大完成時間。首先，創(chuàng)建存放所有待拆卸任務開始拆卸時間的矩陣 st和所有待拆卸零件結束時間的矩陣 ft 。 按照編碼v1的順序對每個待拆卸零件進行拆卸，將拆卸開始時間存入矩陣 st中對應的位置，拆卸結束時間存入矩陣 ft中對應的位置。當遇到某一具有前序拆卸任務的拆卸任務時，比較其前序任務的結束時間，與所在并行序列的上一個任務結束時間，取較大值為該任務的開始時間。當計算完時間后，還需要判斷當前任務是否存在工作區(qū)域沖突，若存在，則對該個體進行懲罰，若不存在則繼續(xù)計算下一個任務。

判斷零部件之間是否存在工作區(qū)域沖突主要有3個判斷標準：1) 兩任務之間是否還存在優(yōu)先關系；2) 兩任務中某一任務是否還有前序任務未執(zhí)行；3) 兩個任務的執(zhí)行時間是否重疊。若2個具有工作區(qū)域沖突關系的拆卸任務同時不滿足以上3個條件，則它們之間會產(chǎn)生工作區(qū)域沖突，該解為不可行解。

2.3 遺傳算子設計

遺傳算法中的選擇操作是對種群進行選擇，從而使優(yōu)秀基因遺傳到下一代。本文采用輪盤賭選擇方法。

遺傳算法中的交叉操作是對種群中被選擇的兩個個體的編碼片段進行部分交叉，從而產(chǎn)生兩個新個體的過程。本文對向量v1采用優(yōu)先保存交叉(precedence preservation crossover, PPX)方法[8-9](圖2)。PPX可以將父代的優(yōu)先關系傳遞給新的子代，從而保證子代的可行性；對向量v2采用單點交叉方法，在向量的長度范圍內(nèi)隨機選擇一個交叉點，將兩個個體的向量v2從交叉點初斷開，并互換前半部分，即可獲得兩個新的子代v2。

圖2 PPX操作示意圖Figure 2 Schematic diagram of PPX operation

遺傳算法中的變異操作是以一定概率使個體中的基因發(fā)生變異以產(chǎn)生新個體的過程。若在向量v1上進行變異操作，可能會產(chǎn)生不符合優(yōu)先關系約束的不可行解。本文選擇基于向量v2進行一個簡單突變：從向量v2中隨機選擇一個變異點，將其值更換為其他并行序列。

2.4 路徑重連算子設計

路徑重連通過使用在搜索過程中得到的一組不同的高質量解對啟發(fā)式算法實現(xiàn)進一步收斂和優(yōu)化。在每個迭代中，路徑重連應用于全局搜索階段結束時找到的解決方案和從精英集中隨機選擇的解決方案，返回與這兩個解決方案相似但可能更好的新解決方案[10]。

2.4.1 路徑距離計算

在算法開始前，定義以下參數(shù)[11]。MoS為個體S中分配給拆卸任務o的操作者；LSM為個體S中分配給操作者的拆卸任務數(shù)；為o在操作者MoS上的位置。若兩個個體中的拆卸任務o被分配給同一個操作者進行拆卸，則定義兩個個體之間o的距離為

若兩個個體中的拆卸任務o被分配給不同的操作者進行拆卸，定義兩個個體之間o的距離為

個體S1和S2之間的距離定義為

2.4.2 重連策略

在遺傳算法每次迭代完成后，選取出最優(yōu)的部分個體組成精英集，并隨機選擇出兩個個體，一個作為初始解Si，一個作為引導解Sg進行路徑重連。設Sc為 當前解決方案(Sc初 始化為Si)。

首先，構造路徑重連過程中得到的解集N：對于Sc中 的每個拆卸任務oi依 次進行判斷，若oi在解Sc和 解Sg中分別位于不同操作者上，將Sc中的oi移動到Sg中的操作者上(位置不變)。比較移動前后解Sc和Sg中oi的距離，選擇其中較短的存放入解集N中；若oi在 解Sc和 解Sg中同一操作者的不同位置上，改變解Sc中oi的位置，并將改變后的解存入解集N中。然后，刪除解集N中的不可行解，以及到Sg的路徑距離大于初始路徑距離(解Sc到Sg的距離)的解，計算剩余解的拆卸完成時間。然后，對于N中剩下的解S，按拆卸完成時間大小進行升序排列，從中選擇拆卸完成時間最小的解作為路徑上的下一個Sc。若該解的最小完成時間優(yōu)于初始解的拆卸完成時間,則同時將其存儲在優(yōu)解集合Path中。重復以上步驟直到無法再得到更優(yōu)的解。最后，返回優(yōu)解集合Path中完工時間最短的解Sr。

3 實驗分析

3.1 案例說明

在1.1節(jié)的案例中，令操作者(并行序列)的數(shù)量為2，運行程序，結果如圖3所示。

圖3 程序運行結果Figure 3 Results on program running

圖3中的柱形表示每個操作者進行操作的拆卸任務，各個任務從甘特圖最左邊開始依次被操作者進行拆卸，柱形上的數(shù)字對應的是正在拆卸的任務的序號。

從圖3中可以發(fā)現(xiàn)，各操作者在零件拆卸過程中無空閑時間，最大化利用了資源，證明本文所述程序有效。

3.2 路徑重連性能分析

3.2.1 參數(shù)校驗

使用田口實驗對精英解個數(shù)、種群大小、交叉概率、變異概率等參數(shù)進行校驗，結果如圖4所示(信噪：望小)。信噪比是質量影響因子的主效應與誤差效應的比值。一般地，信噪比值越大，其穩(wěn)健性越好。由圖4可知，最佳參數(shù)組合：精英解個數(shù)為10，種群規(guī)模為100，交叉概率為0.7，變異概率為0.2。

圖4 平均完成時間的信噪比?主效應圖Figure 4 S/N ratio of average completion time-main effect diagram

3.2.2 路徑重連有效性

為驗證所提路徑重連策略的性能，令多個實際拆卸案例[12-14]采用最佳參數(shù)組合進行運算。為了對多種路徑重連方法進行區(qū)分，將采用精英解與精英解之間進行路徑重連的方法稱為 G A?PR1，劣解向精英解進行路徑重連的方法稱為 G A?PR2。 固定上述算法的CPU運行時間t為N×N×0.01 s，每個案例的3種算法均運行10次。表1展示了相同運行時間下各算法的相對分析誤差(RPD)。

由表1可知，GA-PR1在最小RPD和平均RPD方面的表現(xiàn)均優(yōu)于GA和GA-PR2。此外，繪出3種算法在95%置信區(qū)間下的區(qū)間圖，如圖5所示。結合圖表可得，在相同的CPU運行時間內(nèi)，GA-PR1運行得到的結果更好且更加穩(wěn)定。

圖5 3種算法(GA、GA-PR2和GA-PR1)在95%置信區(qū)間下的區(qū)間圖Figure 5 Interval graphs of the three algorithms (GA, GA-PR2 and GA-PR1) under the 95% confidence interval

表1 GA、GA-PR2和GA-PR1的相對分析誤差Table 1 RPD of GA、GA-PR2 and GA-PR1

3.3 算法性能分析

為分析所提算法的綜合性能，將算法GA-PR1與參考文獻[6]中提出的改進遺傳算法IGA及改進離散蜜蜂算法MDBA[15]進行對比實驗。

通過田口實驗確定各算法的最佳參數(shù)組合(表2)，對21個案例在相同的CPU運行時間分別運行10次，結果如表3所示。根據(jù)表3繪制出3種算法在95%置信區(qū)間下的區(qū)間圖，如圖6所示。

表2 各算法參數(shù)校驗結果Table 2 Verification results of various algorithm parameters

表3 IGA、MDBA和GA-PR1的相對分析誤差Table 3 RPD of the IGA、MDBA and GA-PR1

圖6 3種算法(IGA、MDBA和GA-PR1)在95%置信區(qū)間下的區(qū)間圖Figure 6 Interval graphs of the three algorithms (IGA, MDBA and GAPR1) under the 95% confidence interval

從表3中可知，在平均值方面，相較于IGA，GAPR1獲得了20個較優(yōu)解；相較于 MDBA，GA-PR1獲得了18個較優(yōu)解。在最小值方面，相較于IGA，GAPR1獲得了17個較優(yōu)解；相較于 MDBA，GA-PR1獲得了15個較優(yōu)解。結合表3和圖6可得，對比IGA和MDBA，所提出的GA-PR1具有更好的綜合性能。

4 結論

本文采用加入路徑重連的遺傳算法來解決異步并行拆卸序列規(guī)劃問題，并通過Matlab編程進行實現(xiàn)。所提出的方法具有以下特點。1) 在模型中采用“或優(yōu)先”關系來判斷拆卸方向，對問題進行簡化。2) 采用路徑重連策略，并通過實驗證明其有效性。

雖然本文提出的方法已經(jīng)通過案例進行驗證，但在實際應用中依然存在些許不足。在實際拆卸中，往往不僅關注拆卸完成時間，更要對拆卸成本，資源消耗，拆卸利潤等其他因素進行多方面權衡，尋找最佳方案，但本文所述方法僅考慮拆卸完成時間，略有不足。在以后的研究中，考慮更貼合實際的具體需求，提出更好的方法解決異步并行拆卸序列規(guī)劃問題。