郭希旺，劉士新，王大志

(東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng)110819)

?

多目標(biāo)選擇性拆卸序列優(yōu)化問(wèn)題的分散搜索算法

郭希旺，劉士新，王大志

(東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng)110819)

針對(duì)多資源約束下順序依賴(lài)的選擇性拆卸序列優(yōu)化問(wèn)題，建立以最大拆卸收益和最小拆卸時(shí)間為優(yōu)化目標(biāo)的多目標(biāo)數(shù)學(xué)模型，提出了一種多目標(biāo)分散搜索優(yōu)化算法進(jìn)行求解.該算法針對(duì)本文問(wèn)題的特點(diǎn)設(shè)計(jì)了一種保持足夠多樣性的初始解生成方法，滿(mǎn)足拆卸優(yōu)先關(guān)系的交叉組合算子以及改進(jìn)的參考集更新策略.為了進(jìn)一步提高解的質(zhì)量設(shè)計(jì)了一種局域搜索策略，并利用外部存檔方法存放Pareto解集.應(yīng)用多組實(shí)例進(jìn)行計(jì)算實(shí)驗(yàn)，并與其他求解該問(wèn)題的算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明本文算法優(yōu)于對(duì)比算法，證明本文模型和算法求解本類(lèi)問(wèn)題有效.

選擇性拆卸序列優(yōu)化；多資源約束；多目標(biāo)；分散搜索算法

1　引　言

近年來(lái)，由于拆卸序列優(yōu)化問(wèn)題的理論研究和實(shí)際應(yīng)用價(jià)值，已經(jīng)引起了國(guó)內(nèi)外很多學(xué)者的研究和關(guān)注，提出了一些數(shù)學(xué)模型和優(yōu)化算法.文獻(xiàn)[1]提出拆卸可行信息圖描述產(chǎn)品拆卸序列操作信息，拆卸序列規(guī)劃問(wèn)題被映射到拆卸可行信息圖作為一個(gè)路徑搜索問(wèn)題，并采用遺傳算法求解.文獻(xiàn)[2]提出一個(gè)拆卸優(yōu)先圖來(lái)表示產(chǎn)品結(jié)構(gòu)并通過(guò)迭代法求解問(wèn)題.文獻(xiàn)[3]提出分散搜索算法解決復(fù)雜產(chǎn)品拆卸序列優(yōu)化問(wèn)題.文獻(xiàn)[4]提出了基于規(guī)則的目標(biāo)選擇拆卸方法.文獻(xiàn)[5]基于裝配方法建立了與或聯(lián)絡(luò)圖，產(chǎn)生了包含目標(biāo)零部件的全部可能拆卸序列，并利用篩選過(guò)程選擇最優(yōu)序列.文獻(xiàn)[6]采用混合圖對(duì)目標(biāo)拆卸序列進(jìn)行分析，并應(yīng)用遺傳算法進(jìn)行優(yōu)化.文獻(xiàn)[7]考慮了零部件的成批拆卸和工具的可達(dá)性，提出了一種集成的選擇拆卸方法.文獻(xiàn)[8]針對(duì)報(bào)廢產(chǎn)品的選擇性拆卸序列優(yōu)化問(wèn)題提出了一個(gè)進(jìn)化算法.

上述文獻(xiàn)在構(gòu)建模型和算法時(shí)所考慮的目標(biāo)均為單個(gè)目標(biāo)，而實(shí)際的拆卸序列規(guī)劃往往有多個(gè)目標(biāo)，這些目標(biāo)相互制約.此外，現(xiàn)有研究主要集中于無(wú)資源約束的問(wèn)題，在實(shí)際拆卸零部件過(guò)程中，往往受到時(shí)間、勞動(dòng)力、設(shè)備以及資金等多資源的約束.因此，有必要研究多資源約束下多目標(biāo)拆卸序列優(yōu)化問(wèn)題.分散搜索算法在求解組合優(yōu)化問(wèn)題上體現(xiàn)出了良好的優(yōu)化性能，但目前主要應(yīng)用于單目標(biāo)問(wèn)題的求解，多目標(biāo)分散搜索算法的研究相對(duì)較少.

本文研究了多資源約束下順序依賴(lài)的選擇性拆卸序列多目標(biāo)優(yōu)化問(wèn)題(multi-objective multi-resourceconstrained sequence-dependent selective disassembly sequence optimization problems，MMSSDSOP).建立了以最小拆卸時(shí)間和最大拆卸收益為目標(biāo)的多目標(biāo)優(yōu)化模型，根據(jù)模型特點(diǎn)設(shè)計(jì)了分散搜索(scatter search，SS)優(yōu)化算法，算法可以針對(duì)本文問(wèn)題求得高質(zhì)量的Pareto解集.

2　問(wèn)題描述及模型

2.1問(wèn)題描述

MMSSDSOP可描述如下：在擬拆卸產(chǎn)品中，包含著J個(gè)零部件，每個(gè)零部件都用整數(shù)1，2，...，J來(lái)標(biāo)記.以圖1[9]中某產(chǎn)品的結(jié)構(gòu)圖為例，圖中零部件的總數(shù)為8，實(shí)線(xiàn)箭頭代表零部件之間的優(yōu)先關(guān)系，箭頭的指向?yàn)樵摿悴考仨氃诩擦悴考鹦逗蟛拍軌蜻M(jìn)行拆卸.相鄰兩個(gè)零部件拆卸成本和時(shí)間隨著拆卸先后順序的改變而改變.例如，圖中零部件1必須在所有零部件前進(jìn)行拆卸，零部件5和6必須在零部件8前進(jìn)行拆卸.圖中虛線(xiàn)箭頭代表零部件之間的拆卸順序依賴(lài)，指拆卸一個(gè)零部件時(shí)會(huì)受到另外一個(gè)零部件的阻礙.虛線(xiàn)箭頭的指向?yàn)樵摿悴考鹦稌r(shí)受到虛線(xiàn)根部零部件阻礙.本文使用拆卸順序依賴(lài)時(shí)間增量的概念[9]，如果零部件j在零部件k之前進(jìn)行拆卸，零部件j在零部件k的影響下拆卸時(shí)間產(chǎn)生增量(被迫延長(zhǎng)).當(dāng)一個(gè)零部件拆卸受到其他零部件拆卸順序依賴(lài)時(shí)，該零部件的總的拆卸時(shí)間為拆卸該零部件所消耗的時(shí)間和受到其他零部件拆卸順序依賴(lài)時(shí)間增量的總和.圖中圓括號(hào)中的數(shù)字代表虛線(xiàn)弧的箭尾零部件對(duì)箭頭指向零部件的拆卸順序依賴(lài)時(shí)間.例如，對(duì)于一個(gè)給定的拆卸序列1，2，3，6，5，8，7，4，零部件2被拆卸在零部件3的前面，拆卸零部件2時(shí)受到零部件3的影響，其拆卸順序依賴(lài)時(shí)間增量為四個(gè)時(shí)間單位.圖中方括號(hào)[]里的數(shù)字代表拆卸該零部件所需要的資源數(shù)量，拆卸過(guò)程需要多種資源，拆卸方案必須滿(mǎn)足各種資源的可用量約束限制.例如，圖1描述的問(wèn)題僅涉及1種資源，拆卸零部件1所需要的資源數(shù)量為[3]，拆卸零部件2所需要的資源數(shù)量為[4].求解MMSSDSOP同時(shí)確定每個(gè)零部件是否拆卸以及拆卸順序.

圖1　產(chǎn)品結(jié)構(gòu)圖Fig.1 The structure diagram of product

MMSSDSOP的特點(diǎn)和難點(diǎn)如下：1)拆卸過(guò)程受到多種資源約束限制；2)拆卸過(guò)程中零部件之間存在相互依賴(lài)關(guān)系約束；3)該問(wèn)題是一類(lèi)排序與選擇混合的復(fù)雜整數(shù)規(guī)劃問(wèn)題；4)具有兩個(gè)優(yōu)化目標(biāo)，屬于多目標(biāo)優(yōu)化問(wèn)題.隨著零部件、零部件間相互依賴(lài)的數(shù)量的增加、決策變量和約束的數(shù)量將迅速增加，計(jì)算和求解過(guò)程變得更加困難.因此，本文設(shè)計(jì)了求解該類(lèi)問(wèn)題的SS算法，以便求得高質(zhì)量的Pareto解集.

2.2模型

基于上述問(wèn)題描述，本文針對(duì)MMSSDSOP建立如下數(shù)學(xué)模型：

1)輸入條件(問(wèn)題參數(shù))

J為產(chǎn)品中零部件個(gè)數(shù)，j，k=1，2，...，J代表零部件編號(hào)；

Rj為拆卸零部件j的收益；

DCj為拆卸零部件j的成本；

DTj為拆卸零部件j的時(shí)間；

rrjk為拆卸零部件j后拆卸零部件k的轉(zhuǎn)換消耗資源r的數(shù)量，r=1，2，...，R；

srj為拆卸零部件j消耗資源r的數(shù)量，r=1，2，...，R；

Cr為資源r的最大可用量，r=1，2，...，R；

Cjk為拆卸零部件j后拆卸零部件k的轉(zhuǎn)換成本；

ctjk為拆卸零部件j后立刻拆卸零部件k的轉(zhuǎn)換過(guò)程需要的時(shí)間；

stjk為拆卸零部件k時(shí)零部件j對(duì)其的拆卸順序依賴(lài)時(shí)間增量；

2)輸出條件(決策變量)

3)約束條件：在拆卸零部件時(shí)受到一些條件的限制，以下是本文的約束條件.

其中式(1)代表變量之間的關(guān)聯(lián)關(guān)系；式(2)代表拆卸一個(gè)產(chǎn)品受到資源的限制；式(3)代表兩個(gè)相鄰零部件最多只能執(zhí)行一次轉(zhuǎn)換；式(4)代表決策變量的取值范圍.

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

式(5)代表拆卸一個(gè)產(chǎn)品所獲得的收益；式(6)代表拆卸一個(gè)產(chǎn)品所需要的時(shí)間.決策的目的是最大化拆卸收益，最小化拆卸時(shí)間.

3　求解算法

SS算法是一種元啟發(fā)式算法，已被證明是求解復(fù)雜組合優(yōu)化問(wèn)題的有效方法.與其他元啟發(fā)式算法一樣，在應(yīng)用中首先需要對(duì)解進(jìn)行編碼，然后按照算法實(shí)現(xiàn)步驟進(jìn)行計(jì)算.SS算法基本流程主要由多樣性初始解產(chǎn)生方法、子集產(chǎn)生方法、子集合并方法、解改進(jìn)方法以及參考集更新方法5個(gè)部分組成[10].在SS基本流程基礎(chǔ)上根據(jù)求解問(wèn)題的不同可以采用不同的實(shí)現(xiàn)方式，這使得該算法具有很好的靈活性.

本文SS算法流程如下：

大量研究針對(duì)SS算法中的各組成部分作了很多有益的改進(jìn)，對(duì)求解速度和求解效果有了很大的提高[11].下面介紹SS算法中的初始解集的產(chǎn)生、參考解集、組合算子、局域搜索算子和參考集更新五部分，它們是算法的核心.為了保證在求解過(guò)程中產(chǎn)生一個(gè)高質(zhì)量的Pareto解集，采用外部存檔管理方法[12].外部存檔的主要目的是在搜索過(guò)程中記錄存儲(chǔ)每一個(gè)非支配個(gè)體.本文SS算法采用最大代數(shù)作為停止準(zhǔn)則.

3.1解的編碼和解碼

MMSSDSOP是一類(lèi)排序與選擇混合的優(yōu)化問(wèn)題，因此，本文采用雙鏈表結(jié)構(gòu)對(duì)解進(jìn)行編碼.記個(gè)體sol=(sols，solx)，其中sols=(s1，s2，...，sJ)表示拆卸零部件順序，solx=(x1，x2，...，xJ)，xi代表第i個(gè)零部件是否拆卸.以圖1中的產(chǎn)品為例說(shuō)明編碼方式及目標(biāo)函數(shù)的計(jì)算過(guò)程如下：圖1所示產(chǎn)品包含八個(gè)零部件，各零部件的收益、拆卸成本、拆卸時(shí)間、每個(gè)零部件拆卸需要的資源數(shù)量和兩個(gè)相鄰零部件之間拆卸的轉(zhuǎn)換時(shí)間和轉(zhuǎn)換成本如表1，表2和表3所示.零部件拆卸時(shí)總的資源數(shù)量Cr=50，對(duì)該問(wèn)題隨機(jī)選擇一個(gè)個(gè)體，sols=(1，2，3，5，6，8，7，4)，solx=(1，1，1，1，1，1，1，1)，解碼后得目標(biāo)函數(shù)值Z1=30，Z2=114.

表1　例1中的問(wèn)題參數(shù)Table 1 Problem parameters in example 1

表2　例1中的轉(zhuǎn)換成本Table 2 Transform cost in example 1

表3　例1中的轉(zhuǎn)換時(shí)間Table 3 Transform time in example 1

3.2初始解集的產(chǎn)生

本文設(shè)置初始種群規(guī)模為P，根據(jù)雙鏈表結(jié)構(gòu)的編碼，初始解的產(chǎn)生方法如下：1)隨機(jī)產(chǎn)生一個(gè)滿(mǎn)足優(yōu)先關(guān)系的零部件拆卸序列sols=(s1，s2，...，sJ)，即為初始解的sols鏈表；2)按照零部件si在sols中所處的位置，依次將與之對(duì)應(yīng)的xi元素放置到solx中，xi是在0，1中隨機(jī)產(chǎn)生的，形成solx鏈表；3)由于零部件拆卸過(guò)程中的依賴(lài)關(guān)系，經(jīng)過(guò)過(guò)程1)，2)產(chǎn)生的個(gè)體不一定可行，針對(duì)不可行個(gè)體按如下方式修改solx鏈表：一旦某個(gè)零部件si在solx中的值為“1”，那么零部件si的所有前驅(qū)節(jié)點(diǎn)值也為“1”；一旦某個(gè)零部件si在solx中的值為“0”，那么零部件si的所有后繼節(jié)點(diǎn)的值要為“0”.重復(fù)1)～3)過(guò)程P次，可以產(chǎn)生初始種群.

3.3參考解集

參考集是高質(zhì)量的解和多樣性的解的集合.因本文問(wèn)題優(yōu)化目標(biāo)有兩個(gè)，因此，本文設(shè)計(jì)的參考集由3部分構(gòu)成：1)在初始解集中選擇b1個(gè)目標(biāo)函數(shù)值Z1最大的解作為參考集中b1個(gè)高質(zhì)量解；2)選擇b2個(gè)目標(biāo)函數(shù)值Z2最小的解作為參考集中b2個(gè)高質(zhì)量解；3)為了產(chǎn)生b3個(gè)多樣性解，本文定義了兩個(gè)個(gè)體之間的距離，即

記Ref為當(dāng)前參考集，soli/∈Ref，定義soli和Ref的距離為

參考集中多樣性解的產(chǎn)生方法就是從初始解中逐個(gè)地選擇出b3個(gè)距離當(dāng)前參考集Ref距離最大的解.

3.4組合算子

由于子集中的解來(lái)源于參考集Ref，因此，組合算子是將參考集中的優(yōu)質(zhì)解和多樣性解組合成新解，合理設(shè)計(jì)組合算子既可以保證解的優(yōu)質(zhì)性又可以保證解的多樣性.針對(duì)個(gè)體的雙鏈表結(jié)構(gòu)，本文基于PPX機(jī)制[13]設(shè)計(jì)如下組合算子：記參與PPX交叉運(yùn)算的兩個(gè)個(gè)體分別為組合生成的子代個(gè)體為，則組合算子流程如下：

3.5局域搜索算子

在SS算法中，經(jīng)過(guò)組合算子生成的子代個(gè)體都將作為起始解經(jīng)局域搜索算子進(jìn)行改進(jìn).本文設(shè)計(jì)的局域搜索算子包含以下四個(gè)步驟：

步驟1針對(duì)個(gè)體的sols進(jìn)行操作.在子代個(gè)體中隨機(jī)選擇兩個(gè)個(gè)體，一個(gè)作為初始解另一個(gè)作為向?qū)Ы?，交換鄰域從i=1開(kāi)始，比較兩個(gè)解訪(fǎng)問(wèn)的零部件是否相同，如果，繼續(xù)訪(fǎng)問(wèn)下一個(gè)零部件；如果訪(fǎng)問(wèn)的零部件不相同，在起始解尋找與向?qū)Ы庠L(fǎng)問(wèn)相同的零部件，即，找到確定該位置j，然后將交換，其他零部件的訪(fǎng)問(wèn)順序不變.i←i+1，開(kāi)始下一階段掃描；

步驟2針對(duì)個(gè)體的solx操作.對(duì)相應(yīng)位值進(jìn)行改變，如二進(jìn)制編碼中“0”變?yōu)椤?”，“1”變?yōu)椤?”.進(jìn)而形成新的個(gè)體

步驟3可行化處理：根據(jù)問(wèn)題的假設(shè)和模型的約束條件，經(jīng)過(guò)步驟1和步驟2變換后的解不一定是可行解，因此，需要對(duì)每次迭代得到的新個(gè)體進(jìn)行可行性判定，若可行則過(guò)程繼續(xù)，否則需要進(jìn)行解的可行化處理.處理的方法是，一旦某個(gè)零部件i在變換過(guò)程中solx的值由“0”變?yōu)椤?”，那么零部件i的所有前驅(qū)節(jié)點(diǎn)值也要為“1”；一旦某個(gè)零部件i在變換過(guò)程中solx的值由“1”變?yōu)椤?”，那么零部件i的所有后繼節(jié)點(diǎn)的值要為“0”；

步驟4支配測(cè)試：對(duì)原個(gè)體和改進(jìn)后的新個(gè)體進(jìn)行一個(gè)支配測(cè)試，檢查兩個(gè)個(gè)體是否是支配的或者是非支配的.如果原個(gè)體支配新個(gè)體，新個(gè)體將被廢除；如果新個(gè)體支配原個(gè)體，新個(gè)體將替換原個(gè)體；如果它們兩個(gè)都是非支配，并且新個(gè)體都沒(méi)有被外部存檔所支配，新個(gè)體將被放到外部存檔中，而原個(gè)體保持不變.

3.6更新參考集

參考集更新方法利用改進(jìn)的新解不斷地更新參考集，使參考集中始終保持高質(zhì)量解和多樣性解[14].

針對(duì)本文的3.3節(jié)，更新參考解集的過(guò)程如下：記sol?為一個(gè)新解，算法將Ref中的b1個(gè)最好解按照目標(biāo)函數(shù)值Z1從大到小進(jìn)行排序.如果目標(biāo)函數(shù)Z1(sol?)大于Ref中的第b1個(gè)最好解，則淘汰當(dāng)前Ref中的第b1個(gè)最好解，并根據(jù)目標(biāo)函數(shù)值Z1(sol?)將sol?插入到合適的位置.將Ref中的b2個(gè)最好解按照目標(biāo)函數(shù)值Z2從小到大進(jìn)行排序，如果目標(biāo)函數(shù)Z2(sol?)小于Ref中的第b2個(gè)最好解，則淘汰當(dāng)前Ref中的第b2個(gè)最好解，并根據(jù)目標(biāo)函數(shù)值Z2(sol?)將sol?插入到合適的位置.如果這個(gè)新解sol?在兩個(gè)目標(biāo)函數(shù)Z1(sol?)和Z2(sol?)中都是最優(yōu)的，則保留sol?在b1中位置，不和Ref中的b2個(gè)最好解進(jìn)行比較.如果D(sol?，Ref)值大于Ref中的第b3個(gè)最好解，則淘汰當(dāng)前Ref中的第b3個(gè)最好解，并根據(jù)距離值D(sol?，Ref)將sol?插入到合適的位置.

4　算法的驗(yàn)證與分析

4.1算法的驗(yàn)證

為測(cè)試本文提出方法的有效性，實(shí)驗(yàn)中首先引用文獻(xiàn)[9]中的一個(gè)案例進(jìn)行驗(yàn)證，該實(shí)例包含25個(gè)零部件(不包括虛節(jié)點(diǎn)0)，產(chǎn)品結(jié)構(gòu)如圖2所示，問(wèn)題參數(shù)根據(jù)本文問(wèn)題定義進(jìn)行了修改如表4所示.

表4　問(wèn)題參數(shù)Table 4 Problem parameters

算法應(yīng)用JAVA語(yǔ)言編寫(xiě)，運(yùn)行在使用Windows XP操作系統(tǒng)的Pentium IV(2.66GHz/2.0G)PC機(jī)上.零部件相互間的拆卸順序依賴(lài)時(shí)間增量如圖2所示，轉(zhuǎn)換成本Cjk的取值在[1，10]范圍內(nèi)隨機(jī)取值，轉(zhuǎn)換時(shí)間ctjk在[1，10]范圍內(nèi)隨機(jī)取值，轉(zhuǎn)換資源rrjk在[1，10]范圍內(nèi)隨機(jī)取值，總資源數(shù)Cr=200，表5所示為本算法迭代100次搜索到的Pareto解集.

圖2　產(chǎn)品結(jié)構(gòu)圖Fig.2 The diagram of product structure

表5　求解結(jié)果Table 5 Computational results

為了驗(yàn)證本文算法的有效性，和文獻(xiàn)[15]中線(xiàn)性加權(quán)法進(jìn)行對(duì)比驗(yàn)證.為了公平的比較，兩種算法使用相同的編碼方式、解碼規(guī)則、重組算子以及解的改進(jìn)過(guò)程.文獻(xiàn)[15]解決的是在沒(méi)有資源約束情況下完全拆卸序列多目標(biāo)優(yōu)化問(wèn)題，所提方法為線(xiàn)性加權(quán)法把多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解，在測(cè)試過(guò)程中，根據(jù)本文問(wèn)題對(duì)文獻(xiàn)[15]算法進(jìn)行修改，將本文中Z1，Z2兩個(gè)優(yōu)化目標(biāo)轉(zhuǎn)化為Z=w1Z1+w2Z2單目標(biāo)進(jìn)行試驗(yàn)(其中w1，w2為目標(biāo)權(quán)重系數(shù))與本文算法進(jìn)行比較.兩種算法參數(shù)設(shè)置為：最大迭代代數(shù)100，初始解種群P的大小為100，參考集規(guī)模b=20，對(duì)于文獻(xiàn)[15]中的算法取b1=b2=10.對(duì)于本文算法取b1=b2=5，b3=10.文獻(xiàn)[15]中的算法求解結(jié)果如表6所示.

通過(guò)對(duì)比表5與表6可以看出，本文搜索得到的六個(gè)Pareto解中拆卸時(shí)間最小為159 s，拆卸收益最大為5 475，說(shuō)明本文所提算法在迭代次數(shù)相同可以得到較好的解.由于多目標(biāo)分散搜索算法可在一次運(yùn)算后求得若干Pareto解，求解效率較高，并且為決策者提供了較大的選擇空間，從表5可以看出，若考慮拆卸收益最大，可選擇方案1；若考慮拆卸時(shí)間最小，可選擇方案3.

表6　分散搜索算法求解結(jié)果Table 6 Results of the scatter search algorithm

4.2與其它算法的對(duì)比

為了進(jìn)一步測(cè)試本文算法的有效性，采用NSGA-II算法[16]和本文算法進(jìn)行對(duì)比驗(yàn)證.實(shí)驗(yàn)中對(duì)文獻(xiàn)[9]中的例子進(jìn)行擴(kuò)展，生成了7組不同的測(cè)試實(shí)例，相關(guān)參數(shù)均取整數(shù)形式，參數(shù)設(shè)置如表7所示，零部件數(shù)量分別為(50，80，100，150，200，250，300).資源種類(lèi)數(shù)R=2，資源可用量C1=C2取值在[80，1 000]之間隨機(jī)選取.

表7　不同的參數(shù)和取值范圍Table 7 Different parameters and value range

本文SS算法參數(shù)設(shè)置如下：最大迭代代數(shù)100，初始解種群規(guī)模P=100，參考集規(guī)模b=35，b1= b2=10，b3=15.算法和NSGA-II算法采用相同的編碼方式、解碼規(guī)則.NSGA-II算法參數(shù)設(shè)置如下：最大迭代代數(shù)100，群體規(guī)模P=100，交叉概率為pc=0.6，變異概率為pm=0.005.選擇算子采用輪盤(pán)賭方法，交叉算子采用3.4節(jié)中的PPX交叉.

本文SS算法和NSGA-II算法的結(jié)果評(píng)價(jià)標(biāo)準(zhǔn)如下[17].

1)間距評(píng)估S：用來(lái)測(cè)度所得Pareto前沿上相鄰解間距離的變化情況.其定義為

2)最大散布范圍評(píng)估D：用來(lái)測(cè)度目標(biāo)空間中的兩個(gè)極值解的距離.定義為

D的值越大，表明算法所獲得的散布范圍更廣[17].

實(shí)驗(yàn)中采用3種評(píng)估標(biāo)準(zhǔn)對(duì)本文SS算法和NSGA-II算法進(jìn)行評(píng)估，分別為Pareto解集中解的個(gè)數(shù)、間距評(píng)估和最大散布范圍評(píng)估.為了評(píng)估SS算法和NSGA-II兩種算法的性能，將7組不同的算例求解結(jié)果進(jìn)行比較，實(shí)驗(yàn)中應(yīng)用SS算法和NSGA-II算法對(duì)每個(gè)問(wèn)題實(shí)例求解10次，統(tǒng)計(jì)每個(gè)實(shí)例的Pareto解集中平均解的個(gè)數(shù)Navg，平均解的間距Savg，平均解的最大散布范圍Davg以及算法運(yùn)行10次的平均運(yùn)行時(shí)間(s)，如表8所示.

圖3和圖4為SS算法和NSGA-II算法對(duì)算例1和算例3兩個(gè)算例求解結(jié)果的比較圖.由圖3和圖4可知，SS算法搜索到的解優(yōu)于NSGA-II算法搜索到的解.圖5為兩種算法在七組算例中平均計(jì)算時(shí)間的比較圖，由圖5可知，SS算法的CPU運(yùn)行時(shí)間比NSGA-II算法的少.

通過(guò)分析圖3、圖4、圖5和表8中的實(shí)驗(yàn)數(shù)據(jù)，可以發(fā)現(xiàn)，1)在相同的參數(shù)下，隨著問(wèn)題規(guī)模的增大，相應(yīng)的每個(gè)平均目標(biāo)值也隨著增大；2)算法對(duì)不同的問(wèn)題規(guī)模進(jìn)行求解會(huì)得到不同的近似有效解集，SS算法求解的結(jié)果優(yōu)于NSGA-II算法；3)SS算法的CPU運(yùn)行時(shí)間比NSGA-II算法的少；4)本文算法獲得的Pareto解的數(shù)量多，間距小以及散布的范圍廣.由上可知，針對(duì)以上算例，本文算法求解結(jié)果比NSGA-II更加理想.

圖3　50個(gè)零部件兩種算法求解結(jié)果的比較圖Fig.3 Comparison graph of two algorithms on 50 components

圖4　100個(gè)零部件兩種算法求解結(jié)果的比較圖Fig.4 Comparison graph of two algorithms on 100 components

圖5　兩種算法計(jì)算時(shí)間的比較圖Fig.5 Comparison graph of two algorithms on computing time

表8　兩種算法在間距及最大散布范圍上的比較Table 8 Comparison of the two algorithm on spacing and maximum spread on the range

5　結(jié)束語(yǔ)

本文針對(duì)MMSSDSOP建立了多目標(biāo)整數(shù)規(guī)劃模型.在分散搜索算法基本框架的基礎(chǔ)上，開(kāi)發(fā)了該問(wèn)題的多目標(biāo)SS算法.該算法產(chǎn)生了多樣性好的初始解，并應(yīng)用了參考集更新方法，子集產(chǎn)生方法，子集合并方法和解改進(jìn)方法等來(lái)實(shí)現(xiàn)優(yōu)化求解.對(duì)拆卸問(wèn)題實(shí)例進(jìn)行仿真分析，通過(guò)與NSGA-II算法進(jìn)行比較，表明了提出的SS算法能夠有效求解此模型，獲得多目標(biāo)拆卸序列優(yōu)化問(wèn)題的滿(mǎn)意解.

[1]Wang H，Xiang D，Duan G H.A genetic algorithm for product disassembly sequence planning.Neurocomputing，2008，71(13)：2720-2726.

[2]Lambert A J D.Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs.Omega：Journal of Internationnal Management Science，2006，34(6)：538-549.

[3]Gonzáleza B，Adenso-Díazb B.A scatter search approach to the optimum disassembly sequence problem.Computers Operations Research，2006，33(6)：1776-1793.

[4]Smith S S，Chen W H.Rule-based recursive selective disassembly sequence planning for green design.Advanced Engineering Informatics，2011，25(1)：77-87.

[5]Kara S，Pomprasitpol P，Kebemick H.A selective disassembly methodology for end-of-life products.Assembly Automation，2005，25(2)：124-134.

[6]Wang J F，Liu J H，Li S Q.Intelligent selective disassembly using the ant colony algorithm.Artificial Intelligence for Engineering Design Analysis and Manufacturing，2003，17(4)：325-333.

[7]Chung C，Peng Q J.An integrated approach to selective disassembly sequence planning.Robotics and Computer Integrated Manufacturing，2005，21(4/5)：475-485.

[8]Elsayed A，Kongar E，Gupta S M.An evolutionary algorithm for selective disassembly of end-of-life products.International Journal of Swarm Intelligence and Evolutionary Computation，2012，22(1)：1-7.

[9]Kalayci C B，Gupta S M.Ant colony optimization for sequence-dependent disassembly line balancing problem.Journal of Manufacturing Technology Management，2013，24(3)：413-427.

[10]Marti R，Laguna M，Glover F.Principles of scatter search.European Journal of Operational Research，2006，169(2)：359-372.

[11]譚園園，魏震，王森等.基于VRPTW-AT模型的鋼包優(yōu)化調(diào)度方法.系統(tǒng)工程學(xué)報(bào)，2013，28(1)：94-100. Tan Y Y，Wei Z，Wang S，et al.Optimization algorithm for ladle scheduling based on the VRPTW-AT.Journal of Systems Engineering，2013，28(1)：94-100.(in Chinese)

[12]NebroAJ，LunaF.AbYSS：Adaptingscattersearchtomultiobjectiveoptimization.IEEETransactionsonEvolutionaryComputation，2008，12(4)：439-457.

[13]Bierwirth C，Mattfeld D C.Production scheduling and rescheduling with genetic algorithms.Evolutionary Computation，1999，7(1)：1-18.

[14]Adenso-Díaz B，Garcia-carbajal S，Lozano S.An empirical investigation on parallelization strategies for scatter search.European Journal of Operational Research，2006，2(1)：490-507.

[15]郭希旺，劉士新，王大志.多目標(biāo)拆卸序列優(yōu)化問(wèn)題的分散搜索算法.東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，3(11)：56-59. Guo X W，Liu S X，Wang D Z.Scatter search for solving multi-objective disassembly sequence optimization problems.Journal of Northeastern University(Natural Science Edition)，2012，3(11)：56-59.(in Chinese)

[16]Kalyanmoy D.A fast and elitist multiobjective genetic algorithm：NSGA-II.IEEE Transactions on Evolutionary Computation，2002，6(2)：182-197.

[17]張勇德，黃莎白.多目標(biāo)優(yōu)化問(wèn)題的蟻群算法研究.控制與決策，2005，20(2)：170-176. Zhang Y D，Huang S B.On ant colony algorithm for solving multiobjective optimization problems.Control and Decision，2005，20(2)：170-176.(in Chinese)

Scatter search algorithm for multi-objective selective disassembly sequence optimization problems

Guo Xiwang，Liu Shixin，Wang Dazhi
(School of Information Science Engineering，Northeastern University，Shenyang 110819，China)

Selective disassembly sequence optimization problem with multi-resource constraints and sequencedependence is considered by establishing a multi-objective model with the objective of maximizing profit and minimizing disassembly time.A multi-objective scatter search(SS)method is put forward to solve this problem.Based on the characteristics of the problem，an initial solution diversification generation method is put forward which satisfies the crossover combination operator，which maintains the disassembly precedence relationship，and improved reference set updating strategy.In order to further improve the quality of the solution，a local search strategy is designed and external archive method is employed to store Pareto solution set.The results of SS and other algorithms in solving several computational experiments are compared，and the experimental results demonstrate the validity of the model and SS algorithm.

selective disassembly sequence optimization；multi-resource constraints；multi-objective；scatter search algorithm

TP18

A

1000-5781(2016)03-0307-10

10.13383/j.cnki.jse.2016.03.003

郭希旺(1981-)，男，遼寧營(yíng)口人，博士生.研究方向：綠色制造，組合優(yōu)化.Email：x.w.guo@163.com；

劉士新(1968-)，男，遼寧調(diào)兵山人，教授，博士生導(dǎo)師.研究方向：生產(chǎn)計(jì)劃與調(diào)度，物流系統(tǒng)建模與優(yōu)化，組合優(yōu)化算法. Email：sxliu@mail.neu.edu.cn；

王大志(1978-)，男，遼寧沈陽(yáng)人，講師，研究方向：智能優(yōu)化算法.Email：wangdazhi1@ise.neu.edu.cn.

2013-08-23；

2014-09-11.

國(guó)家自然科學(xué)基金資助項(xiàng)目(71171038)；中央高?；究蒲袠I(yè)務(wù)費(fèi)資助項(xiàng)目(N110404024).