郭 鈞 王振東 杜百崗 李益兵

1.武漢理工大學(xué)機(jī)電工程學(xué)院，武漢，4300702.武漢理工大學(xué)湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室，武漢，430070

0 引言

拆卸過程作為廢舊(end-of-life，EOL)產(chǎn)品再生過程中的關(guān)鍵步驟，其規(guī)劃問題逐漸受到了人們的廣泛關(guān)注。拆卸序列規(guī)劃(disassembly sequence planning，DSP)是指根據(jù)預(yù)定的評價(jià)指標(biāo)，確定EOL產(chǎn)品中零部件的最佳拆卸順序。在工程實(shí)踐中，EOL產(chǎn)品拆卸過程主要是對高剩余價(jià)值或有害的零部件進(jìn)行提取。選擇性并行拆卸具有拆卸步驟少、拆卸時(shí)間短、拆卸能耗低等優(yōu)點(diǎn)，對提高EOL產(chǎn)品的再生效率具有重要意義。本文針對復(fù)雜EOL產(chǎn)品再生的拆卸過程，研究不定拆卸程度的選擇性異步并行拆卸序列規(guī)劃方法，從而達(dá)到提高拆卸收益及拆卸效率的目的。

近年來，選擇性并行拆卸受到了國內(nèi)外學(xué)者的廣泛關(guān)注。SMITH等[1]利用模塊化理論將產(chǎn)品分組為模塊并通過遞歸規(guī)則進(jìn)行并行拆卸。KIM等[2]建立了成本順序依賴選擇性并行拆卸序列整數(shù)規(guī)劃模型，以拆卸成本最小為優(yōu)化目標(biāo)，用分支定界算法進(jìn)行求解。PISTOLESI等[3]建立了選擇性并行拆卸序列規(guī)劃模型并設(shè)計(jì)了多目標(biāo)張量模因算法進(jìn)行規(guī)劃求解。田永廷等[4]提出了以拆卸總時(shí)間最小為目標(biāo)的基于遺傳算法的選擇性并行拆卸序列規(guī)劃方法。上述文獻(xiàn)考慮的并行拆卸通常為同步并行DSP，將并行任務(wù)分步驟進(jìn)行，每一步的并行任務(wù)必須同時(shí)開始，而在實(shí)際拆卸過程中，在滿足約束關(guān)系的前提下拆卸任務(wù)可無需等待直接開始執(zhí)行。為縮短同步等待時(shí)間，REN等[5]提出了異步并行拆卸的概念，建立了異步并行拆卸序列規(guī)劃模型，并利用遺傳算法進(jìn)行優(yōu)化求解，證明了異步并行拆卸較同步并行拆卸效率更高。鄧明星等[6]在異步并行拆卸的基礎(chǔ)上提出了考慮多目標(biāo)件的異步并行拆卸序列規(guī)劃方法，以拆卸完工時(shí)間最小為優(yōu)化目標(biāo)，利用改進(jìn)的遺傳算法進(jìn)行求解，證明了該方法的可行性與有效性。然而現(xiàn)有的選擇性并行拆卸通常是以目標(biāo)件為出發(fā)點(diǎn)逆向搜索出產(chǎn)品的必拆零件集合，從而將選擇性拆卸序列規(guī)劃問題轉(zhuǎn)化為定拆卸程度的局部完全拆卸序列規(guī)劃問題。該拆卸方式應(yīng)用于EOL產(chǎn)品的再生過程中，忽略了必拆零件集合以外的非必拆零部件的再生收益。因此，本文在此基礎(chǔ)上提出將目標(biāo)件逆向搜索出的必拆零件集合作為EOL產(chǎn)品的最少拆卸件集合，進(jìn)一步考慮EOL產(chǎn)品所有零部件再生收益的不定拆卸程度的選擇性異步并行拆卸方法。

并行拆卸序列規(guī)劃問題復(fù)雜，隨著EOL產(chǎn)品零件數(shù)量增加，拆卸序列解空間呈指數(shù)增長，傳統(tǒng)的拆卸序列規(guī)劃方法已無法滿足復(fù)雜產(chǎn)品拆卸需求。于是許多學(xué)者利用智能算法來解決該問題。目前應(yīng)用到DSP問題上的智能算法有遺傳算法[7]、蟻群算法[8]、人工魚群算法[9]、人工蜂群算法[10]、花朵授粉算法[11]等。生物地理學(xué)優(yōu)化(biogeography-based optimization，BBO)算法是由SIMON[12]受到生物地理學(xué)理論的啟發(fā)而提出的，該算法借鑒生物地理學(xué)中的物種遷移模型來求解優(yōu)化問題，具有算法結(jié)構(gòu)簡單、局部開發(fā)能力強(qiáng)等諸多優(yōu)勢，目前BBO算法在工程優(yōu)化[13]、車間調(diào)度[14]等領(lǐng)域取得了明顯的效果，具有十分廣闊的應(yīng)用前景。DSP問題是一個(gè)NP-hard問題[15]，目前將BBO算法用于求解DSP問題還鮮有報(bào)道。

綜上所述，本文基于異步并行拆卸概念，提出了一種全面考慮廢舊產(chǎn)品所有零部件再生收益的不定拆卸程度的選擇性異步并行拆卸序列規(guī)劃方法。針對該問題通過目標(biāo)件逆向搜索確定最小拆卸程度，以拆卸時(shí)間最小與利潤最大為優(yōu)化目標(biāo)，構(gòu)建多目標(biāo)異步并行拆卸序列規(guī)劃數(shù)學(xué)模型。結(jié)合DSP問題特點(diǎn)，將原適用于解決連續(xù)優(yōu)化問題的BBO算法進(jìn)行離散化，并采用基于隨機(jī)拓?fù)浣Y(jié)構(gòu)的遷移操作提高算法搜索能力，設(shè)計(jì)了多目標(biāo)隨機(jī)拓?fù)浣Y(jié)構(gòu)生物地理學(xué)優(yōu)化(multi-objective random topology biogeography-based optimization，MRTBBO)算法進(jìn)行求解。最后通過實(shí)例驗(yàn)證不定拆卸程度選擇性異步并行拆卸方法的優(yōu)越性及MRTBBO算法求解該模型的有效性。

1 模型的構(gòu)建

1.1 不定拆卸程度選擇性異步并行拆卸問題描述

EOL產(chǎn)品再生的拆卸過程目的是在盡可能少的時(shí)間內(nèi)獲取EOL產(chǎn)品中盡可能多的價(jià)值?？紤]到有害零部件的強(qiáng)制拆卸處理以及擁有高剩余價(jià)值的零部件的拆卸需求，需將這些零部件作為選擇性拆卸中的目標(biāo)件。而傳統(tǒng)的選擇性拆卸多是指定程度的拆卸序列規(guī)劃問題，圖1中紅色圓代表目標(biāo)件，黃色圓代表目標(biāo)件逆向搜索出的優(yōu)先拆卸件。圖1a所示為將其轉(zhuǎn)化為定拆卸程度的局部完全性拆卸。而不定拆卸程度的選擇性拆卸的拆卸程度在一個(gè)范圍之間，如圖1b所示，其中虛線圍住部分代表最小拆卸件集合，實(shí)線圍住部分為其最大拆卸件集合。

(a)定拆卸程度 (b)不定拆卸程度圖1 選擇性拆卸的拆卸范圍對比Fig.1 Comparison of disassembly range forselective disassembly

圖1示例零件的拆卸時(shí)間與收益見表1。在異步并行拆卸模式下，圖1示例的定拆卸程度的選擇性拆卸與不定拆卸程度的選擇性異步并行拆卸的解如圖2、圖3所示，圖中M1、M2表示EOL產(chǎn)品。在考慮EOL產(chǎn)品每個(gè)零部件的拆卸時(shí)間與拆卸收益的情況下，對比圖2、圖3a，不定拆卸程度選擇性異步并行拆卸能在相同的拆卸時(shí)間8.5 s下比定拆卸程度的選擇性異步并行拆卸多拆卸2、3號零件，從而獲得更多收益，或進(jìn)一步延長拆卸時(shí)間至9 s(圖3b)，執(zhí)行更多的拆卸操作，獲取更大的收益。

表1 拆卸時(shí)間與收益

圖2 定拆卸程度的選擇性異步并行拆卸Fig.2 Selective asynchronous parallel disassemblywith a certain degree of disassembly

(a)拆卸時(shí)間8.5 s(b)延長拆卸時(shí)間至9 s圖3 不定拆卸程度選擇性異步并行拆卸Fig.3 Selective asynchronous parallel disassemblysolution set with indeterminate degree of disassembly

綜上可見，在EOL產(chǎn)品再生過程的拆卸中，有必要在考慮拆卸目標(biāo)件的基礎(chǔ)上進(jìn)一步考慮EOL產(chǎn)品的所有零部件拆卸收益，建立以拆卸時(shí)間最小、拆卸收益最大為目標(biāo)的不定拆卸程度選擇性異步并行拆卸模型。

1.2 拆卸混合圖模型

圖4 拆卸混合圖示例Fig.4 Example of disassembling hybrid diagram

拆卸混合圖是用來描述產(chǎn)品零部件之間的連接關(guān)系以及約束關(guān)系的表達(dá)模型，能充分表達(dá)出產(chǎn)品的拓?fù)浣Y(jié)構(gòu)。本文采用拆卸混合圖來表達(dá)待拆卸產(chǎn)品的信息。如圖4所示，將拆卸混合圖定義為G={V,UE,DE,IE}，其中，V為拆卸混合圖的最小拆卸單元的集合，UE為拆卸混合圖的無向邊集合，DE為有向?qū)嵕€邊集合，IE為有向虛線邊集合。V={v1,v2,…,vn}，n為最小拆卸單元個(gè)數(shù)；UE={u1,u2,…,um}，m為無向邊的總數(shù)，無向邊表示兩最小拆卸單元之間存在接觸關(guān)系；DE={d1,d2,…,dk}，k為有向?qū)嵕€邊的總數(shù)，有向?qū)嵕€邊表示兩最小拆卸單元之間既存在接觸關(guān)系又存在拆卸優(yōu)先關(guān)系；IE={i1,i2,…,ih}，h為有向虛線邊的總數(shù)，有向虛線邊表示兩最小拆卸單元之間只存在拆卸優(yōu)先關(guān)系。

為便于計(jì)算機(jī)對拆卸混合圖模型進(jìn)行表達(dá)和優(yōu)化分析，將拆卸混合圖做數(shù)字化處理。將拆卸混合圖轉(zhuǎn)化為接觸約束矩陣Mc和優(yōu)先約束矩陣Mp：

則由Mc與Mp的定義可知，任意時(shí)刻拆卸單元i的可拆條件為

(1)

1.3 問題假設(shè)

為了簡化問題，做以下假設(shè)：①假設(shè)零部件基本拆卸時(shí)間與拆卸收益為定值，不受質(zhì)量狀態(tài)影響，即本文不考慮不確定質(zhì)量狀態(tài)所帶來的基本拆卸時(shí)間與收益的波動(dòng)；②假設(shè)拆卸資源充足且不存在拆卸過程中的空間干涉問題。

1.4 模型相關(guān)參數(shù)及說明

模型相關(guān)參數(shù)定義見表2。

目標(biāo)函數(shù)為

(2)

(3)

約束條件為

(4)

(5)

(6)

xi=1 ?i∈Cm

(7)

(8)

(9)

(10)

(11)

目標(biāo)函數(shù)式(2)為拆卸過程總時(shí)間，即并行拆卸過程中最后一個(gè)零件的拆卸結(jié)束時(shí)間；目標(biāo)函數(shù)式(3)為拆卸過程總收益，其中包含零部件的預(yù)期再生收益以及與并行數(shù)和總時(shí)間相關(guān)的拆卸成本；約束式(4)表示零件i的開始拆卸時(shí)間為

表2 符號定義

其直接優(yōu)先零件集合拆卸結(jié)束時(shí)間與零件i執(zhí)行單元M當(dāng)前拆卸結(jié)束時(shí)間之間的最大值；約束式(5)表示零件i的直接優(yōu)先零件集合的拆卸結(jié)束時(shí)間為其優(yōu)先零件拆卸結(jié)束時(shí)間中的最大值；約束式(6)表示拆卸零件i的執(zhí)行單元M的當(dāng)前結(jié)束時(shí)間為拆卸其前一零件ei的結(jié)束時(shí)間；約束式(7)表示最小必拆零件集合中的零件必須拆卸；約束式(8)表示總的拆卸零件數(shù)量大于或等于最小必拆零件的數(shù)量；約束式(9)表示若零件i需拆卸，則其直接優(yōu)先零件集合中的零件也需拆卸；約束式(10)表示零件i的拆卸結(jié)束時(shí)間需大于拆卸開始時(shí)間；約束式(11)用于計(jì)算拆卸序列的拆卸程度。

2 基于多目標(biāo)隨機(jī)拓?fù)浣Y(jié)構(gòu)生物地理學(xué)求解算法

BBO算法通過模擬島嶼之間的物種遷徙從而達(dá)到生態(tài)平衡的遷移機(jī)制與棲息地自然災(zāi)害的突變機(jī)制來求解優(yōu)化問題。棲息地適應(yīng)物種生存的程度用適應(yīng)度指數(shù)(habitat suitability index，HSI)來衡量。高HSI值的棲息地?fù)碛休^高的遷出率與較低的遷入率，而低HSI值的棲息地?fù)碛休^低的遷出率與較高的遷入率。棲息地物種的遷入遷出機(jī)制使HSI值較低的棲息地可通過獲得HSI值高的棲息地提供的優(yōu)秀物種變量(suitability index variables，SIV)改善自身。此外，BBO算法的突變機(jī)制使棲息地上的SIV發(fā)生突變，從而使得BBO算法具有一定的防止陷入局部最優(yōu)的能力。

原始的BBO算法是用來解決連續(xù)優(yōu)化問題的，本文針對問題模型將BBO算法離散化加以改進(jìn)從而提出了MRTBBO算法，以解決本文所提的不定拆卸程度的選擇性異步并行拆卸問題。

2.1 待拆卸零件搜索算法

本文在目標(biāo)驅(qū)動(dòng)推理法[16]的啟發(fā)下提出一種待拆卸零件搜索算法。通過拆卸混合圖的約束關(guān)系，輸入目標(biāo)件進(jìn)行逆向遞歸搜索待拆卸零件集合。算法具體步驟如下：

(1)初始化搜索集合St1、被動(dòng)件集合St2、待拆卸零件集合F為空，加載目標(biāo)件集合S，加載接觸約束矩陣Mc、優(yōu)先約束矩陣Mp。

(2)將S中所有拆卸零件放入搜索集合St1與待拆卸零件集合F。

(3)判斷搜索集合St1是否為空，為空則跳轉(zhuǎn)至步驟(5)；若St1不為空則以搜索集合St1中的零件作為主動(dòng)件(被約束節(jié)點(diǎn))，依據(jù)可拆條件式(1)逆向推理出搜索集合St1中所有零件的被動(dòng)件(直接優(yōu)先約束節(jié)點(diǎn))并放入St2。

(4)判斷St2是否為空，為空則跳轉(zhuǎn)至步驟(5)；否則將St2去重后添加到待拆卸零件集合F中，并用St2替換搜索集合St1使之成為新的搜索集合St1，返回步驟(3)。

(5)將待拆卸零件集合F去重后輸出。

2.2 棲息地編碼

有效的編碼方式可以減少算法中的不可行個(gè)體的生成，從而避免算法中對不可行個(gè)體的篩選與轉(zhuǎn)化。本文結(jié)合不定拆卸程度選擇性異步并行拆卸序列規(guī)劃的特點(diǎn)，采用三層鏈表結(jié)構(gòu)的編碼方式：P={PRw,PRx,PRm}，第一層PRw采用長度為n的1～n之間隨機(jī)不重復(fù)整數(shù)序列來表示零件的拆卸權(quán)重，即PRw={w1,w2,…,wn}，wi(i=1,2,…,n)代表零件i的拆卸權(quán)重。第二層PRx由長度為n的隨機(jī)0-1二進(jìn)制序列來代表是否拆卸，即PRx={x1,x2,…,xn}，xi(i=1,2,…,n)為1表示零件i需拆卸，為0則表示不拆卸。第三層PRm由1～P之間的隨機(jī)可重復(fù)整數(shù)來表示執(zhí)行該零件拆卸的執(zhí)行單元序號，即PRm={M1,M2,…,Mn}，Mi(i=1,2,…,n)代表零件i由拆卸執(zhí)行單元Mi執(zhí)行拆卸操作。P為并行拆卸的并行數(shù)。圖4示例的拆卸并行數(shù)為3的一段隨機(jī)初始化編碼見表3。

表3 棲息地初始化編碼示例

2.3 棲息地解碼

假定圖4所示拆卸示例的目標(biāo)件為{8}，配合表3所示初始化編碼，PRx中需拆卸的零件{3,7}與目標(biāo)件{8}取并集為{3,7,8}。通過待拆卸件搜索算法獲取最終需拆卸零件集合Df={1,3,5,6,7,8}。將初始棲息地編碼的第二部分PRx序列進(jìn)行調(diào)整，調(diào)整結(jié)果見表4，具體步驟如下：

(1)更新混合圖模型中的接觸約束矩陣Mc和優(yōu)先約束矩陣Mp。在Mc與Mp中將最終拆卸零件集合Df以外的行與列剔除。

(2)結(jié)合Mc與Mp，依據(jù)可拆卸條件式(1)推斷出當(dāng)前可拆卸零件集合Dk={k1,k2,…,km}。

(3)從Dk中選出拆卸權(quán)重w最大的零件ki，使其在執(zhí)行單元Mki上進(jìn)行拆卸。

(4)更新Mp與Mc，將零件號ki所在列與行的值置0，解除與其相關(guān)的約束。

(5)判斷最終所需拆卸零件集合Df中的零件是否都已拆卸，若未拆卸完則跳轉(zhuǎn)至步驟(2)，否則算法結(jié)束，輸出最終拆卸序列結(jié)果。

表4 棲息地編碼調(diào)整

如表4所示，調(diào)整過后的編碼按上述算法解碼得出的最終拆卸序列結(jié)果為

上式表明3個(gè)并行的拆卸執(zhí)行單元的拆卸任務(wù)序列。

2.4 棲息地遷移機(jī)制

遷移機(jī)制是BBO算法的主要機(jī)制，遷移操作中包括遷入與遷出，該過程依據(jù)個(gè)體的遷入率與遷出率來進(jìn)行選擇并執(zhí)行。遷入遷出率的確定方式不同也會(huì)導(dǎo)致算法性能的差異。

2.4.1計(jì)算遷移率

不同的遷移率模型對算法的優(yōu)化性能產(chǎn)生重要影響，針對DSP問題的特點(diǎn)，本文采用正弦遷移模型來計(jì)算棲息地的遷入遷出概率，其遷入率λi與遷出率μi的計(jì)算公式如下：

(12)

(13)

其中，I為棲息地最大遷入率，E為棲息地最大遷出率，Hi為棲息地i的適應(yīng)度指數(shù)，Hmax為所有棲息地中的最大適應(yīng)度指數(shù)。在本文所提模型中，令I(lǐng)=E=1。

2.4.2遷移過程

確定棲息地的遷移概率后，需依據(jù)遷入遷出率來選擇遷入遷出棲息地并執(zhí)行遷移策略。本文按遷入遷出率的大小采用輪盤賭的方式依次選擇被遷入棲息地Zi與遷出棲息地Zj。本文針對三層鏈表編碼形式分別對權(quán)重序列PRw、是否拆卸序列PRx、執(zhí)行單元序列PRm采取不同的遷移策略。

如圖5所示，對于PRw序列，將零件總數(shù)n以內(nèi)的正整數(shù)隨機(jī)劃分為兩個(gè)集合W1與W2，被遷入棲息地Zi中的PRw序列在W1集合中的元素所在位置保持不變，依次填入臨時(shí)棲息地Zk。然后將遷出棲息地Zj在W2集合的元素按照順序依次填入臨時(shí)棲息地Zk的空位，形成新的P′Rw序列。

圖5 PRw序列的遷移操作Fig.5 PRw sequence migration operation

如圖6所示，對于PRx、PRm序列，首先生成一串長度為n的隨機(jī)0-1數(shù)組作為參照，其中元素為1指示棲息地Zi中對應(yīng)位置的元素填入臨時(shí)棲息地Zk的對應(yīng)位置，元素為0指示棲息地Zj中對應(yīng)位置的元素填入臨時(shí)棲息地Zk的對應(yīng)位置，從而形成新的P′Rx、P′Rm序列。

(a)PRx序列遷移(b)PRm序列遷移圖6 PRx、PRm序列的遷移操作Fig.6 PRx、PRm sequence migration operation

PRw序列、PRx序列、PRm序列的遷移操作分別執(zhí)行完畢后進(jìn)行整合，{P′Rw,P′Rx,P′Rm}成為新棲息地，替換被遷入棲息地Zi，完成一次遷移操作。

2.4.3基于隨機(jī)拓?fù)浣Y(jié)構(gòu)的遷移

BBO算法雖然具有多種優(yōu)良性能，但是BBO算法的全局搜索性能還有所欠缺，容易陷入局部最優(yōu)。為了提高BBO算法的搜索性能，本文采用基于隨機(jī)拓?fù)浣Y(jié)構(gòu)的遷移算子。

BBO的遷移算子默認(rèn)是全局拓?fù)浣Y(jié)構(gòu)，即每次遷移操作中的遷出解從全體棲息地中依據(jù)遷出率選擇進(jìn)行遷移，而隨機(jī)拓?fù)浣Y(jié)構(gòu)為每個(gè)棲息地都隨機(jī)生成一個(gè)大小不定的鄰域范圍，為該棲息地選擇遷出棲息地時(shí)遷出解均從中按遷出率進(jìn)行選擇。此外，用平均鄰域大小參數(shù)K來設(shè)置種群中所有棲息地的平均鄰域水平。設(shè)置參數(shù)Nmax為外部檔案集質(zhì)量無改善的迭代次數(shù)上限，當(dāng)算法連續(xù)Nmax次迭代尋優(yōu)后外部檔案集質(zhì)量無改善時(shí)，將種群的隨機(jī)拓?fù)浣Y(jié)構(gòu)進(jìn)行重置。這種機(jī)制有助于算法跳出局部最優(yōu)。

2.5 棲息地突變機(jī)制

自然界中發(fā)生重大災(zāi)害會(huì)導(dǎo)致棲息地的組成和結(jié)構(gòu)發(fā)生急劇變化，BBO算法將該情形模擬成棲息地突變機(jī)制，棲息地的突變機(jī)制也是BBO算法至關(guān)重要的環(huán)節(jié)，可以用來提高種群的多樣性。

2.5.1計(jì)算突變率

棲息地的突變率與棲息地的物種數(shù)量概率成反比，物種數(shù)量較多或較少時(shí)的物種數(shù)量概率都相對較低，而物種數(shù)量為中等水平的概率比較高。結(jié)合拆卸序列規(guī)劃問題，本文提出了一種基于適應(yīng)度指標(biāo)的突變機(jī)制，即在適應(yīng)度較低和較高的棲息地中的突變概率相對較低，而適應(yīng)度接近于平均適應(yīng)度時(shí)的突變概率相對較高。本文的突變概率計(jì)算公式為

(14)

2.5.2突變過程

結(jié)合三層鏈表的編碼方式，拆卸權(quán)重序列PRw與是否拆卸序列PRx及執(zhí)行單元序列PRm分別采取不同的突變方式，如圖7、圖8所示，PRw序列的突變方式是從PRw序列上隨機(jī)選擇一個(gè)位置上的元素插入其他位置；PRx序列的突變方式是從PRx序列上隨機(jī)選擇兩個(gè)位置的元素進(jìn)行二進(jìn)制取反；PRm序列的突變方式是從PRm序列上隨機(jī)選擇兩個(gè)位置的元素隨機(jī)改變成其他執(zhí)行單元序號。

圖7 PRw序列的突變方式Fig.7 Mutation of PRw sequence

(a)PRx序列突變 (b)PRm序列突變圖8 PRx、PRm序列的突變方式Fig.8 Mutation of PRx,PRm sequence

2.6 算法流程

綜上所述，給出的算法流程圖見圖9。

圖9 算法流程圖Fig.9 Algorithm flow chart

3 實(shí)例應(yīng)用

為了驗(yàn)證本文所提模型方法的優(yōu)越性和所提算法求解該模型問題的有效性，利用MATLAB平臺編寫了MRTBBO算法，算法的運(yùn)行環(huán)境為2.6GHz CPU，12G RAM，Windows 10 64位操作系統(tǒng)的個(gè)人計(jì)算機(jī)。

3.1 試驗(yàn)案例

本文分別采用兩種不同規(guī)模大小的試驗(yàn)案例來驗(yàn)證所提模型的優(yōu)越性。案例一是零件數(shù)為23的機(jī)械臂[17]；案例二是零件數(shù)為52的二級圓柱圓錐減速器，其三維模型爆炸圖見圖10，拆卸混合圖見圖11，零件信息表見表5。

圖10 案例二：二級圓柱圓錐齒輪減速器Fig.10 Case 2: two-stage cylindrical bevelgear reducer

圖11 案例二：二級圓柱圓錐齒輪減速器拆卸混合圖Fig.11 Case 2: disassembly hybrid diagram oftwo-stage cylindrical bevel gear reducer

表5 案例二：二級圓柱圓錐齒輪減速器零件信息

3.2 試驗(yàn)結(jié)果分析

本文通過正交試驗(yàn)確定MRTBBO算法分別作用在兩個(gè)試驗(yàn)案例上的最優(yōu)參數(shù)。

3.2.1案例一

算法參數(shù)設(shè)置：種群大小Psize=250，迭代次數(shù)Gmax=800，棲息地最大突變率Pmax=0.2，平均鄰域大小K=6，非支配解集無改善迭代次數(shù)上限Nmax=10。針對本文所提不定拆卸程度選擇性異步并行拆卸問題，設(shè)目標(biāo)件Cd={1,6,12}，并行度為3，計(jì)算結(jié)果Pareto解空間分布如圖12所示，其中各個(gè)解的詳細(xì)拆卸序列見表6。作為對比設(shè)置同樣的目標(biāo)件、并行度，傳統(tǒng)定拆卸程度下的選擇性異步并行拆卸優(yōu)化結(jié)果見表7。不定拆卸程度模式非支配解集表6中案例一的拆卸甘特圖見圖13a，定拆卸程度模式最優(yōu)解的拆卸甘特圖見圖13b。

圖12 案例一:Pareto解集空間分布Fig.12 Case1: spatial distribution of Paretosolution set

表6 案例一：不定拆卸程度選擇性異步并行拆卸非支配解集

表7 案例一：定拆卸程度選擇性異步并行拆卸最優(yōu)解

(a)不定拆卸程度選擇性異步并行拆卸非支配解集示例

(b)定拆卸程度選擇性異步并行拆卸最優(yōu)解示例圖13 案例一：Cd={1,6,12},并行度為3時(shí)最優(yōu)解甘特圖Fig.13 Case 1:Gantt chart of optimal solution whenCd={1,6,12}, degrees of parallelism is 3

3.2.2案例二

算法參數(shù)設(shè)置：種群大小Psize=200，迭代次數(shù)Gmax=1000，棲息地最大突變率Pmax=0.1，平均鄰域大小K=12, 非支配解集無改善迭代次數(shù)上限Nmax=20。針對本文所提不定拆卸程度選擇性異步并行拆卸問題，設(shè)目標(biāo)件Cd={1,3,7,14,29}，并行度為3，計(jì)算結(jié)果Pareto解集空間分布如圖14所示，其中詳細(xì)拆卸序列信息見表8。作為對比，設(shè)置同樣的目標(biāo)件、并行度，傳統(tǒng)定拆卸程度下的選擇性異步并行拆卸優(yōu)化結(jié)果見表9。不定拆卸程度模式非支配解集表8中第一個(gè)解方案的拆卸甘特圖見圖15a，定拆卸程度模式最優(yōu)解的拆卸甘特圖見圖15b。

圖14 案例二:Pareto解集空間分布Fig.14 Case 2: spatial distribution of Pareto solution set

表8 案例二：不定拆卸程度選擇性異步并行拆卸非支配解集

表9 案例二：定拆卸程度選擇性異步并行拆卸最優(yōu)解

(a)不定拆卸程度選擇性異步并行拆卸非支配解集示例

(b)定拆卸程度選擇性異步并行拆卸最優(yōu)解示例圖15 案例二：Cd={1,3,7,14,29},并行度為3時(shí)最優(yōu)解甘特圖Fig.15 Case 2:Gantt chart of optimal solution whenCd={1,3,7,14,29}, degrees of parallelism is 3

3.3 實(shí)例對比結(jié)果分析

觀察圖13與圖15可以發(fā)現(xiàn)，本文所提不定拆卸程度選擇性異步并行拆卸能在相同的拆卸時(shí)間內(nèi)充分利用由拆卸優(yōu)先約束造成的等待時(shí)間，進(jìn)一步拆卸了多個(gè)非最小拆卸集合中的零件，從而在相同的拆卸時(shí)間內(nèi)獲取了更多的利潤。

觀察兩個(gè)試驗(yàn)案例的不定程度選擇性異步并行拆卸解集展示表6與表8，與定程度選擇性異步并行拆卸解集展示表7與表9，可以發(fā)現(xiàn)不定拆卸程度選擇性異步并行拆卸為決策者提供了多種不同拆卸程度的決策方案，在實(shí)際應(yīng)用中有較好的實(shí)際意義。

4 算法對比

為證明本文所提MRTBBO算法解決不定拆卸程度的選擇性異步并行拆卸問題的優(yōu)越性，將其與經(jīng)典多目標(biāo)優(yōu)化算法：快速非支配排序遺傳算法(NSGA-Ⅱ)、多目標(biāo)粒子群優(yōu)化算法(MOPSO)、多目標(biāo)生物地理學(xué)優(yōu)化算法(MOBBO)[18]、基于模糊Pareto支配的生物地理學(xué)優(yōu)化算法(FPDCBBO)[19]、多目標(biāo)擾動(dòng)生物地理學(xué)優(yōu)化算法(MDBBO)[20]進(jìn)行對比試驗(yàn)。

采用多目標(biāo)算法的綜合度量指標(biāo)反世代距離(inverted generational distance，IGD)、多樣性度量指標(biāo)間距(spacing，S)和準(zhǔn)確性度量指標(biāo)成功率(success ratio，SR)作為算法性能評價(jià)指標(biāo)，IGD值越小代表算法的收斂性越好，分布越均勻，S值越小代表算法的多樣性越好，SR值越大說明算法性能越好[21]。

所有算法種群規(guī)模均設(shè)為200，迭代1000次。各算法的參數(shù)設(shè)定如下：MRTBBO的最大變異率為0.1，平均鄰域大小為20，非劣解無改善代數(shù)上限為30；NSGA-Ⅱ的交叉概率為0.9，變異率為0.1；MOPSO的最大慣性權(quán)重為1.2，最小慣性權(quán)重為0.6，個(gè)體因子為0.8，社會(huì)因子為0.8。MOBBO、FPDCBBO、MDBBO的最大變異率均為0.1。將各算法獨(dú)立運(yùn)行20次，取20次結(jié)果的平均值作為最終的測試結(jié)果，各性能指標(biāo)結(jié)果見表10，案例一與案例二中一次運(yùn)算的各算法求得的Pareto解集空間分布圖分別見圖16、圖17。

表10 各算法性能指標(biāo)測試結(jié)果

圖16 案例一：各算法Pareto解集空間分布Fig.16 Case 1:spatial distribution of Pareto solutionset of each algorithm

圖17 案例二：各算法Pareto解集空間分布Fig.17 Case 2:spatial distribution of Pareto solutionset of each algorithm

觀察表10對比結(jié)果與解空間分布圖16及圖17，MRTBBO算法性能指標(biāo)在兩個(gè)案例中均優(yōu)于另5種算法，表明在解決不定程度的選擇性異步并行拆卸問題上，MRTBBO可以在相同的測試條件下更接近真實(shí)Pareto前沿且解的多樣性更好，算法性能更好。依據(jù)本文改進(jìn)的生物地理學(xué)算法MRTBBO與未做改進(jìn)的多目標(biāo)生物地理學(xué)算法MOBBO的數(shù)據(jù)進(jìn)行對比，結(jié)果表明本文采取的基于隨機(jī)拓?fù)浣Y(jié)構(gòu)的遷移策略可以有效提高多目標(biāo)BBO算法的搜索性能。

5 結(jié)論

為了提高廢舊產(chǎn)品再生過程中的再生收益，本文研究了考慮不定拆卸程度的選擇性拆卸問題，建立了以拆卸總時(shí)間最短和拆卸總收益最大為優(yōu)化目標(biāo)的考慮不定拆卸程度的選擇性異步并行拆卸模型；針對該模型特點(diǎn)，提出了一種改進(jìn)的生物地理學(xué)優(yōu)化算法。設(shè)計(jì)了一種三層鏈表的編碼解碼方式來避免不可行拆卸序列的產(chǎn)生，提出了基于隨機(jī)拓?fù)浣Y(jié)構(gòu)的遷移策略以提高算法的搜索性能；通過兩種不同規(guī)模的試驗(yàn)案例驗(yàn)證了不定拆卸程度的選擇性異步并行拆卸序列規(guī)劃模型，能在考慮最小待拆件集合之外，充分利用由拆卸優(yōu)先約束造成的等待時(shí)間，進(jìn)而拆卸更多的零部件，并為決策者提供多個(gè)拆卸方案。最后通過對比算法試驗(yàn)驗(yàn)證了本文所提算法改進(jìn)機(jī)制的合理性，以及解決不定拆卸程度的選擇性異步并行拆卸問題的有效性。未來將進(jìn)一步深入研究考慮廢舊產(chǎn)品質(zhì)量狀態(tài)的拆卸序列規(guī)劃模型與解決方法。