朱建峰，徐志剛，蘇開遠(yuǎn)

(山東大學(xué) 機(jī)械工程學(xué)院，山東 濟(jì)南 250061)

0 引言

拆卸是在對廢舊產(chǎn)品進(jìn)行生命周期末端處理時的一個關(guān)鍵的預(yù)先處理過程，拆卸過程是從產(chǎn)品中分離出零件，用來實現(xiàn)零件的維修、重用、回收、再制造等[1]。拆卸序列規(guī)劃(Disassembly Sequence Planning, DSP)是指根據(jù)產(chǎn)品內(nèi)部結(jié)構(gòu)、裝配約束關(guān)系以及干涉檢驗等信息，生成可指導(dǎo)實際拆卸過程的拆卸序列[2]。再制造過程中，只有部分零部件可再制造重用，因此選擇性拆卸更加符合再制造的實際。好的拆卸序列規(guī)劃方法能有效提高拆卸效率，降低拆卸成本。

進(jìn)行DSP首先需建立拆卸信息模型，用以表示拆卸約束并產(chǎn)生可行拆卸序列。目前，國內(nèi)外研究中，大多采用連接圖[3]、優(yōu)先關(guān)系圖[4]或鄰接矩陣和優(yōu)先關(guān)系矩陣[5]進(jìn)行拆卸信息建模，這些建模方式方法簡單、建模容易，但得到的可行解空間不完整，在進(jìn)行DSP時可能遺漏更好的可行解。另外，也有許多文獻(xiàn)中采用有向圖[6]、與或圖[7]、Petri網(wǎng)[8]進(jìn)行拆卸建模，上述建模方式雖然能完整表達(dá)DSP問題的可行解空間，但對于較大規(guī)模的DSP問題，生成這類拆卸模型非常困難。本文基于緊固件約束矩陣和結(jié)構(gòu)件約束矩陣進(jìn)行拆卸信息建模，在完整表達(dá)拆卸約束的前提下，區(qū)分了緊固件和結(jié)構(gòu)件，相比于優(yōu)先關(guān)系矩陣，降低了矩陣的維度。

DSP問題的求解是NP-hard問題，其中，基于啟發(fā)式智能優(yōu)化算法的DSP求解方法具有求解速度快、參數(shù)設(shè)置方便、模塊化程度高等優(yōu)點，現(xiàn)已成為求解DSP問題的重要方法，例如，基于遺傳算法[9]、蟻群算法[10]、粒子群算法[11]、人工蜂群算法[12]、花朵授粉算法[13]等DSP方法。上述求解方法未考慮多目標(biāo)優(yōu)化問題，或采用加權(quán)法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，簡化了問題的求解難度，最終只能得到一個最優(yōu)或近似最優(yōu)解，且沒有考慮到多目標(biāo)件選擇性拆卸的情況，具有一定的局限性。

混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)[14]結(jié)合模因演算算法(Memetic Algorithm, MA)和粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法的優(yōu)點，具有概念簡單、參數(shù)少、計算速度快、全局尋優(yōu)能力出色、魯棒性強(qiáng)等特點。SFLA因其獨特的優(yōu)勢已被廣泛應(yīng)用于函數(shù)優(yōu)化[15]、生產(chǎn)調(diào)度[16]、資源網(wǎng)絡(luò)優(yōu)化[17]和圖像處理[18]等方面，同時SFLA在求解旅行商問題[19-20]、背包問題[21]、時間表問題[22]等組合優(yōu)化問題中也表現(xiàn)出優(yōu)異的性能。

但目前已有文獻(xiàn)對多目標(biāo)件的選擇性拆卸序列規(guī)劃(Multi-object Selective DSP, MSDSP)的研究相對較少，且鮮有學(xué)者將SFLA應(yīng)用于DSP問題中。針對上述問題，本文提出基于多目標(biāo)改進(jìn)蛙跳算法(Multi-object Imoroved SFLA, MISFLA)的MSDSP方法，利用Pareto思想構(gòu)建了多目標(biāo)改進(jìn)蛙跳算法，同時構(gòu)建了MSDSP的數(shù)學(xué)模型，通過不同拆卸規(guī)模的拆卸實例，并與多種算法進(jìn)行對比分析，驗證了本文所提方法的可行性與優(yōu)越性，同時將其運用到具體的拆卸實例中。

1 多目標(biāo)件選擇性拆卸序列規(guī)劃數(shù)學(xué)模型

1.1 問題描述及拆卸信息表達(dá)

MSDSP是指在滿足拆卸優(yōu)先關(guān)系約束的前提下，為拆卸所有目標(biāo)零部件，以拆卸時間最小化和拆卸收益最大化為目標(biāo)，確定最優(yōu)(近似最優(yōu))的可行拆卸序列。

本文在文獻(xiàn)[23]的基礎(chǔ)上，對其拆卸信息表達(dá)方法進(jìn)行補充和優(yōu)化，提出利用緊固件約束矩陣和結(jié)構(gòu)件約束矩陣構(gòu)建產(chǎn)品的拆卸信息模型。

本文對產(chǎn)品拆卸建模作如下說明：

(1)結(jié)構(gòu)件指除緊固件以外最小的拆卸單元；緊固件指用來固連兩個或多個結(jié)構(gòu)件的機(jī)械部件，例如螺栓、螺釘、螺柱等。

(2)緊固件與結(jié)構(gòu)件之間的約束關(guān)系作為已知條件，通過用戶輸入方式獲得。

(1)緊固件約束矩陣定義

緊固件約束矩陣表示拆卸產(chǎn)品中緊固件和結(jié)構(gòu)件之間的約束關(guān)系，其中矩陣的行序號表示緊固件序號，列序號表示結(jié)構(gòu)件序號，緊固件約束矩陣

(1)

式中coij,i=1,2,…,m,m為待拆卸產(chǎn)品中存在的緊固件數(shù)量；j=1,2,…,n，n為待拆卸產(chǎn)品中存在的結(jié)構(gòu)件數(shù)量。且緊固件i與結(jié)構(gòu)件j存在一定的約束關(guān)系。對coij進(jìn)行如下定義：

(2)結(jié)構(gòu)件約束矩陣定義

結(jié)構(gòu)件約束矩陣表示結(jié)構(gòu)件與結(jié)構(gòu)件之間的約束關(guān)系，其中矩陣的行序號和列序號都表示結(jié)構(gòu)件序號，結(jié)構(gòu)件約束矩陣

(2)

如圖1所示為某待拆卸產(chǎn)品的拆卸模型示例圖，該產(chǎn)品由5個緊固件和4個結(jié)構(gòu)件裝配而成，由于圖例為二維裝配圖且產(chǎn)品底端固定，只考慮3個拆卸方向：+X、-X、+Y，由上述緊固件約束矩陣和結(jié)構(gòu)件約束矩陣的建立方法可得該產(chǎn)品的緊固件約束矩陣G1和結(jié)構(gòu)件約束矩陣G2，分別如下所示：

1.2 數(shù)學(xué)模型的建立

為便于數(shù)學(xué)模型的建立，對MSDSP進(jìn)行如下假設(shè)：①所有零部件均可拆卸；②考慮到再制造拆卸實際中，只有部分零部件可再制造重用，本文在拆卸收益計算時只考慮所有目標(biāo)件的價值。

描述MSDSP模型用到的符號及其定義如下：

(1)N為待拆卸產(chǎn)品中零部件的數(shù)量，N=n+m,其中：n為所有結(jié)構(gòu)件的數(shù)量，m為所有緊固件的數(shù)量。

(2)i為所有零部件的編號,i∈{1,2,…,N}。

(3)P為所有結(jié)構(gòu)件編號的集合，P={1,2,…,n}。

(4)J為所有緊固件編號的集合，J={n+1,n+2,…,n+m}。

(5)Ng為拆除所有目標(biāo)零部件需要的拆卸操作數(shù)量。

(6)j為拆卸操作的編號，j∈{1,2,…,Ng}。

(8)coij為緊固件約束矩陣G1中的元素。

(10)Dj為執(zhí)行拆卸任務(wù)時被干涉的拆卸方向數(shù)，0≤Dj≤s。

(11)Td(x)為拆卸方向變換消耗的時間。

(12)Tt(x)為拆卸工具變換消耗的時間。

(13)Tc(x)為移除時緊固件與結(jié)構(gòu)件的切換消耗的時間。

(14)Tp(x)為移除結(jié)構(gòu)件時額外消耗的時間。

(15)Tb(x)為移除零部件的基本拆卸時間。

(16)V(x)為零部件可再利用價值指數(shù)。

(17)E(x)為零部件回收收益。

基于以上定義，以拆卸過程中拆卸時間最小化和拆卸收益最大化為目標(biāo)，構(gòu)建以下數(shù)學(xué)模型:

各決策變量的定義及表達(dá)式如下：

Td(xj+1)=

Tt(xj+1)=

Tc(xj+1)=

優(yōu)化目標(biāo)函數(shù)：

(3)

(4)

約束條件：

(5)

(6)

(7)

(8)

j∈{1,2,…,Ng}。

(9)

其中：式(3)和式(4)分別表示最小化拆卸時間和最大化拆卸收益的目標(biāo)函數(shù)；式(5)表示緊固件i能被拆卸的約束條件；式(6)表示已拆除相關(guān)緊固件的結(jié)構(gòu)件i能被拆卸的約束條件；式(7)為拆除所有目標(biāo)件所拆卸的所有零部件均屬于待拆卸產(chǎn)品中的部件；式(8)表示包括目標(biāo)件在內(nèi)，每個零部件只能被拆卸一次；式(9)表示每執(zhí)行一次拆卸操作，必須且只能拆掉一個零部件。

2 多目標(biāo)改進(jìn)蛙跳算法的求解方法

本文通過多目標(biāo)優(yōu)化理論設(shè)計基于多目標(biāo)改進(jìn)蛙跳算法(MISFLA)，主要包括青蛙個體編碼與可行解構(gòu)造、蛙群分組、局部搜索及全局信息混合等部分。

2.1 青蛙個體編碼與可行解構(gòu)造

MISFLA的青蛙個體結(jié)構(gòu)與多目標(biāo)件選擇性DSP問題的解的表現(xiàn)形式相對應(yīng)，即每一個青蛙個體表示為一個可行的拆卸序列。青蛙個體編碼結(jié)構(gòu)定義如下：

青蛙個體Frog采用三段式編碼，總體包括偽碼fv、實碼fr及目標(biāo)碼fob，數(shù)學(xué)表達(dá)式如下：

Frog={{fv}1×N|{fob}|{fr}1×Ng}。

(10)

式中：fv為基于拆卸信息模型G1和G2產(chǎn)生的可行串行完全拆卸序列；fob為待拆卸目標(biāo)件的集合；fr為fv中包含所有目標(biāo)件的最短可行拆卸子序列，即一條可行的選擇性序列。

可行解的具體構(gòu)造規(guī)則如下：

(1)定義可拆卸零部件集合為A，目標(biāo)件集合為B，可行完全拆卸序列的解為X，選擇性序列的解為X1，令A(yù)=?，B=?,X=?,X1=?。

(2)初始狀態(tài)下，根據(jù)G1和G2，由式(5)與式(6)搜索所有可拆卸的緊固件或結(jié)構(gòu)件，并將其放入A中，將待拆卸目標(biāo)件放入集合B中，定義臨時變換矩陣G3和G4，使G3=G1,G4=G2。

(3)從A中隨機(jī)選擇一個元素a，放入X最左端，并在A中刪除元素a；然后判斷元素a的類型，若元素a為緊固件，轉(zhuǎn)步驟(4)，若元素a為結(jié)構(gòu)件，則轉(zhuǎn)步驟(5)。

(4)更新G3(刪除G3中a所在行的所有元素)，然后根據(jù)G1，對于a所連接的每一個結(jié)構(gòu)件，在G4中由式(6)判斷其是否可拆，若可拆，則將相應(yīng)結(jié)構(gòu)件編號放入A中。

(5)更新G3(刪除G3中a所在行的所有元素)，同時更新G4(刪除G4中a所在行與列的所有元素)，然后根據(jù)G1，對a所阻擋的每一個緊固件，在G3中由式(5)判斷其是否可拆，若可拆，則將相應(yīng)緊固件放入a中；同時，根據(jù)G2，對結(jié)構(gòu)件a在任一拆卸方向所阻擋的每一個結(jié)構(gòu)件，在G4中由式(6)判斷其是否可拆，若可拆且該結(jié)構(gòu)件不在X中，則將相應(yīng)結(jié)構(gòu)件放入A中。

(6)判斷產(chǎn)品中所有緊固件和結(jié)構(gòu)件是否已被拆除，若已完成，則輸出解X，否則轉(zhuǎn)步驟(3)。

(7)將X中的元素依次放入X1，直至X1中包含集合B中所有元素。

(8)可行青蛙個體構(gòu)造完成。

2.2 目標(biāo)函數(shù)計算與蛙群分組

DSP的目的是為了獲取拆卸時間最短和拆卸經(jīng)濟(jì)效益最好的可行拆卸序列。本文的優(yōu)化目標(biāo)函數(shù)如式(3)和式(4)所示，拆卸時間包括零部件拆卸方向變換消耗的時間、拆卸工具變換消耗的時間、基本拆卸時間、移除結(jié)構(gòu)件時額外消耗的時間、拆除時緊固件與結(jié)構(gòu)件的切換消耗的時間，拆卸收益包括零部件可再利用價值指數(shù)及回收收益，各目標(biāo)函數(shù)值依據(jù)實碼fr進(jìn)行計算。

因為本文涉及多個目標(biāo)的協(xié)同優(yōu)化，無法簡單地對解的優(yōu)劣性進(jìn)行排序，所以引入Pareto最優(yōu)解集理論和NSGA-Ⅱ中的快速非支配排序及擁擠距離比較思想進(jìn)行蛙群分組。

青蛙個體支配關(guān)系，即任意兩個具有k個子目標(biāo)的青蛙個體Frog1和Frog2，若滿足式(11),則稱Frog1支配Frog2，記為Frog1?Frog2。

(11)

若同時存在某目標(biāo)i,使得fi(Frog1)優(yōu)于fi(Frog2),以及目標(biāo)j,使得fj(Frog1)優(yōu)于fj(Frog2),則兩青蛙個體互不支配，F(xiàn)rog1和Frog2對應(yīng)的解互為非支配解或Pareto解。若在決策空間中不存在某個青蛙支配當(dāng)前青蛙，則當(dāng)前青蛙個體對應(yīng)的解為Pareto最優(yōu)解，多目標(biāo)優(yōu)化問題會產(chǎn)生一組Pareto最優(yōu)解，即Pareto最優(yōu)解集，所有Pareto最優(yōu)解對應(yīng)目標(biāo)值的連線構(gòu)成Pareto最優(yōu)前沿。

基于快速非支配排序及擁擠度比較思想的蛙群分組方式如下：

(1)計算種群中每個青蛙個體的目標(biāo)函數(shù)值f1和f2，定義集合L(l),用以存放不同非支配等級的Pareto解，l表示非支配等級，l越小，等級越高。為種群中所有青蛙個體定義兩個參數(shù)nF和SF,分別表示種群中Frog支配個體的個數(shù)和被Frog支配的個體的集合。

(2)種群分級。計算每個青蛙個體的nF和SF，將種群中所有nF=0的個體保存到L(1)中，對于L(1)中L(1)的每個個體i，遍歷其所支配個體集合SFi中的每個個體j,執(zhí)行nFj=nFj-1，若nF=0，則將該個體j保存到L(2)中，依此類推，直至整個種群被分級。

(3)擁擠度計算。設(shè)共有k個目標(biāo)函數(shù)，依照每個優(yōu)化目標(biāo)函數(shù)值fj，將種群中所有個體進(jìn)行升序排列，令邊界的兩個個體擁擠度為∞，其他個體i的擁擠度

(12)

(4)青蛙個體排序。首先根據(jù)非支配等級l進(jìn)行排序，l越小，青蛙個體越優(yōu)秀，對于相同等級的個體再依照擁擠度進(jìn)行排序，擁擠度越大，個體越優(yōu)秀，最終將所有個體從優(yōu)到劣進(jìn)行排序。

(5)依照排序排名，第i個青蛙子群體Yi的分組公式如下：

Yi={Frogi+qsp(j-1)|1≤j≤qsf},1≤i≤qsp。

(13)

式中：qsp為青蛙子群體數(shù)量；qsf為每個子群體中的青蛙個體數(shù)量；i,j為整數(shù)。

2.3 改進(jìn)的蛙群局部搜索策略

由于標(biāo)準(zhǔn)混合蛙跳算法的局部搜索策略不適用于DSP問題的求解，本文引入調(diào)節(jié)因子和調(diào)節(jié)序的思想優(yōu)化設(shè)計局部搜索策略。

在旅行商問題(Traveling Salesman Problem, TSP)的求解中，調(diào)節(jié)因子用于改變兩個城市的先后訪問順序，調(diào)節(jié)序則是由多個調(diào)節(jié)因子構(gòu)成的有序序列[20]。本文針對DSP問題，借鑒遺傳算法用于離散組合優(yōu)化問題時對優(yōu)先關(guān)系保留交叉算子的相關(guān)處理，提出基于調(diào)節(jié)位置的調(diào)節(jié)序?qū)η嗤軅€體中的偽碼段fv進(jìn)行調(diào)節(jié)。

(1)調(diào)節(jié)因子與調(diào)節(jié)序

已知某拆卸序列fv，定義調(diào)節(jié)因子為Af(α,β)，其作用是將fv中第β個零部件插入到第α個零部件之前，產(chǎn)生一個新序列。假設(shè)某fv=(2,4,6,1,5,3)，調(diào)節(jié)因子為Af(2,4)，則newfv=fv+Af(2,4)=(2,1,4,6,5,3)。

(2)基于調(diào)節(jié)位置的調(diào)節(jié)序

將含有調(diào)節(jié)位置的調(diào)節(jié)序定義為Afs(γ,δ),Afs(γ,δ)=(Af1+Af2+…+Afn)表示含有n個調(diào)節(jié)因子的調(diào)節(jié)序，其中：γ,δ為隨機(jī)產(chǎn)生的調(diào)節(jié)位置，且1≤γ≤δ≤n；Af1,Af2,…,Afn是調(diào)節(jié)因子，它們之間的先后順序是有意義的。調(diào)節(jié)序作用于拆卸序列，也就是依照調(diào)節(jié)序中的調(diào)節(jié)因子依次調(diào)整拆卸序列。設(shè)fv1,fv2為兩個不同的拆卸任務(wù)序列，則Afs(γ,δ)?(fv1Θfv2)表示將fv1中第γ個零部件與第δ個零部件之間的序列按照其在fv2中序列的排列方式進(jìn)行調(diào)整，即

newfv1=fv1+Afs(γ,δ)?(fv1Θfv2)=fv1+(Af1+Af2+…+Afn)=

[(fv1+Af)1+Af2]+…+Afn)。

(14)

調(diào)節(jié)序構(gòu)造算子偽代碼如下：

步驟1確定fv1中第γ個零部件與第δ個零部件之間的零部件在fv2中的位置,設(shè)兩者之間的零部件在fv2中的相對位置為i，則1≤i≤δ-γ+1;在fv1中的位置為j,且γ≤j≤δ;令i=1,j=γ。

步驟2判斷fv2(i)與fv1(j)是否相等，若fv2(i)≠fv1(j)，在fv1中找到零部件位置p使得fv2(i)==fv1(p),由此可得Af(j,p)，則newfv1=fv1+Af(j,p)；若fv2(i)=fv1(j)，轉(zhuǎn)步驟3。

步驟3i=i+1,j=j+1;若i>δ-γ+1，調(diào)節(jié)結(jié)束；否則轉(zhuǎn)步驟2，繼續(xù)執(zhí)行。

設(shè)fv1=(2,5,4,3,1,6)，fv2=(3,2,4,5,6,1)，則Afs(2,5)?(fv1Θfv2)=[Af1(2,4),Af2(3,4)]。

(3)青蛙個體更新策略構(gòu)建

設(shè)當(dāng)前迭代子群體中的最差個體為Frogw、最好個體為Frogb、全局最優(yōu)個體為Frogg，基于上述調(diào)節(jié)序思想構(gòu)建更新策略,對最差青蛙個體Frogw進(jìn)行位置調(diào)整，位置更新公式如下：

s=min{int[r·length(Afs(γ,δ)?

(fvwΘfvb))],smax};

(15)

Afi∈Afs(γ,δ)?(fvwΘfvb)。

(16)

執(zhí)行更新策略(15)和(16)后，依據(jù)fvw更新frw,并計算newFrogw的各個目標(biāo)函數(shù)值，判斷newFrogw的支配個體數(shù)num(SnF)與被支配的個體數(shù)之差nnF是否變大，若變大，則更新Frogw，否則執(zhí)行更新策略(17)和(18),

s=min{int[r·length(Afs(γ,δ)?

(fvwΘfvg))],smax};

(17)

Afi∈Afs(γ,δ)?(fvwΘfvg)。

(18)

執(zhí)行上述更新策略后，若num(SnF)與nnF之差仍沒得到改善，則按照初始青蛙個體的構(gòu)造方法重新構(gòu)造一個newFrogw。

圖2所示為青蛙個體執(zhí)行更新策略的一個實例，圖中，調(diào)節(jié)位置(γ,δ)=(4,9)，r=1，由調(diào)節(jié)序構(gòu)造算子可知length(Afs(γ,δ)?(fvwΘfvb))=4，設(shè)smax=5，則具體調(diào)節(jié)過程如下：

由Frogw的進(jìn)化過程可知，F(xiàn)rogw在進(jìn)化過程中始終保持了優(yōu)先約束關(guān)系，從而避免了因驗證青蛙個體是否可行帶來的時間浪費。每一個調(diào)節(jié)因子表示一個青蛙步長，通過smax可有效地控制青蛙個體跳躍的距離，避免因跳躍距離過大而找不到最優(yōu)解或因跳躍距離過小導(dǎo)致移動速度緩慢。同時，在進(jìn)化過程中實現(xiàn)了實碼串frw的長度、零部件優(yōu)先順序的多樣性調(diào)節(jié)，保證了青蛙個體的多樣性。

(4)青蛙個體更新信息源增加

在基本蛙跳算法的子群更新策略中，信息交互的來源只有全局最優(yōu)解、局部最優(yōu)解和局部最劣解，因此本文通過增加信息交互源讓子群內(nèi)鄰域解參與到信息交互中，實現(xiàn)子群內(nèi)部信息的充分交流。具體策略如下：

在每個子群體局部最劣解更新的同時，選擇除局部最劣解以外的4個次劣解構(gòu)成局部次劣域，同時選擇除局部最優(yōu)解以外的4個次優(yōu)解構(gòu)成局部次優(yōu)域，從局部次劣域中隨機(jī)選取2個不同的次劣解Frogw1與Frogw2作為待更新解，從局部次優(yōu)域中隨機(jī)選取2個不同的次優(yōu)解Frogb1與Frogb2分別對Frogw1和Frogw2進(jìn)行更新，次劣域更新公式如下：

s=min{int[r·length(Afs(γ,δ)?

(fvw1Θfvb1))],smax};

(19)

Afi∈Afs(γ,δ)?(fvw1Θfvb1)。

(20)

2.4 改進(jìn)的青蛙全局信息混合策略

基本蛙跳算法在全局混合的過程中只是進(jìn)行了簡單的信息交流，各個子群信息并未進(jìn)行深度挖掘。但是，一味盲目追求交互深度會增加種群的相似性和單一性，導(dǎo)致后續(xù)迭代中蛙群分組的價值降低。針對這一問題，為兼顧信息交互深度和個體多樣性，本文提出一種滿足優(yōu)先約束關(guān)系的三段隨機(jī)交叉和單點變異思想。將qsp個子群的局部最優(yōu)解進(jìn)行隨機(jī)交叉，生成qsp個新解分別代替各子群的局部最劣解，接著再進(jìn)入全局混合，然后對種群所有個體進(jìn)行單點變異。

三段隨機(jī)交叉策略如圖3所示，即隨機(jī)產(chǎn)生4個交叉點1～4，對每兩個交叉點之間的片段，從起始交叉點往后隨機(jī)選取長度為2～5不等的碼段進(jìn)行交叉，將父代P1中1-1′、2-2′、3-3′之間的元素按照父代P2中的相同元素的排列順序進(jìn)行調(diào)節(jié)，并填充到子代C1的相應(yīng)位置，剩下的片段則全部賦值給子代C1。

本文采用單點變異方式構(gòu)建變異算子，如圖4所示，其基本思想如下：首先在P1中產(chǎn)生1個隨機(jī)變異點a，將a點之前的序列賦值給C1,a點之后的序列構(gòu)建步驟如下:①刪除約束矩陣G1和G2中關(guān)于a點之前片段所有元素的優(yōu)先關(guān)系約束；②在新的約束矩陣G1和G2條件下，依據(jù)產(chǎn)生初始解的過程，對a點之后的片段所有元素進(jìn)行隨機(jī)重新排列，完成C1的構(gòu)建。

2.5 MISFLA算法實現(xiàn)步驟

步驟1算法基本參數(shù)設(shè)定(青蛙的種群規(guī)模N、子群體數(shù)qsp、種群迭代次數(shù)Ip、子群體迭代次數(shù)Ic、最大蛙跳步長Smax)。

步驟2種群初始化。按照2.1節(jié)所述可行序列的構(gòu)造方法隨機(jī)產(chǎn)生N個可行解，并計算每個青蛙個體的各個目標(biāo)函數(shù)值。

步驟3蛙群分組。根據(jù)2.2節(jié)所述的蛙群分組方法，將種群中所有個體劃分至qsp個子群體中。

步驟4局部搜索。根據(jù)2.3節(jié)所述的青蛙個體更新策略，對每個子群體進(jìn)行局部搜索。

步驟5全局信息交流。根據(jù)2.4節(jié)所述的全局信息混合策略，重新混合所有青蛙個體。

步驟6計算每個青蛙個體的各個目標(biāo)函數(shù)值，并更新種群中的Pareto非支配解集。

步驟7判斷是否滿足算法終止條件，若滿足，則結(jié)束搜索并輸出Pareto非支配解集；否則，轉(zhuǎn)步驟3,繼續(xù)搜索。

MISFLA的算法流程圖如圖5所示。

3 算例分析與實例應(yīng)用

本文基于Visual Studio 2015，采用VC++語言編寫算法程序。運行本應(yīng)用程序的計算機(jī)環(huán)境為：Intel(R)Core(TM)i3-4170 CPU@3.70 GHz 3.70 GHz，內(nèi)存4 GB，Windows 7 64位操作系統(tǒng)。通過求解不同規(guī)模的拆卸實例并與多種算法作對比，說明所提算法MISFLA的可行性與優(yōu)越性。

3.1 算例分析

以文獻(xiàn)[25]中的工業(yè)機(jī)械臂模型為算例求解MSDSP問題，該模型由23個零部件組成，其三維模型如圖6所示，由于原始拆卸模型中部分拆卸信息不全，對其進(jìn)行補充后的拆卸信息如表1所示。

表1 工業(yè)機(jī)械臂拆卸信息表

續(xù)表1

通過正交試驗及統(tǒng)計分析，在綜合考慮解的質(zhì)量與程序運行時間的基礎(chǔ)上，設(shè)置算法參數(shù)如下：

青蛙的種群規(guī)模N=100、子群體數(shù)qsp=10、種群迭代次數(shù)Ip=50、子群體迭代次數(shù)Ic=5、最大蛙跳步長Smax=5；選擇拆卸目標(biāo)件分別為fob1={6,11,12}和fob2={5,6,9,12}，求解結(jié)果如表2所示。

表2 工業(yè)機(jī)械臂在不同拆卸目標(biāo)件下的拆卸結(jié)果

為綜合評價本文所提MISFLA的性能，將本文算法與帶精英策略的快速非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm Ⅱ, NSGA-Ⅱ)[26]、粒子群算法(Particle Swarm Optimization, PSO)[27]和基本蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)進(jìn)行對比，本文均采用C++語言實現(xiàn)上述各算法的編寫，并運行于相同的計算機(jī)環(huán)境中，各算法在目標(biāo)件為fob1和fob2時，求解的Pareto前沿曲線分別如圖7和圖8所示。同時本文采用程序平均運行時間tr、反轉(zhuǎn)世代距離IGD、間距指標(biāo)SP和Pareto非劣解的個數(shù)nump四個指標(biāo)綜合綜合評價各算法，對比結(jié)果如表3所示。其中：IGD用于評價所求Pareto非劣解與真實Pareto的前沿的總體差距，IGD值越小表示所求Pareto前沿的收斂性和分布多樣性越好，即更加逼近真實Pareto前沿；SP用于評價Pareto前沿分布的均勻性，SP越小表示分布均勻性越好。本文計算IGD和SP的公式如下：

(21)

(22)

由圖7和表3可知，當(dāng)拆卸目標(biāo)件為{6,11,12}時，NSGAⅡ的運行時間較好、收斂性及Pareto非劣解的求解能力適中，但其分布均勻性較差；PSO的運行時間及分布均勻性適中，其收斂性及Pareto非劣解的求解能力較差；基本SFLA的運行時間、收斂性、Pareto非劣解的求解能力適中，且分布均勻性較好；MISFLA運行時間稍長，但其在收斂性、Pareto非劣解的求解能力及分布均勻性方面均表現(xiàn)良好。當(dāng)拆卸目標(biāo)件為{5,6,9,12}時，雖然MISFLA的運行時間略長，但在求解質(zhì)量、收斂性方面遠(yuǎn)優(yōu)于其余3種算法，且表現(xiàn)出了良好的分布均勻性。因此，MISFLA的綜合性能優(yōu)于其余3種算法，在求解MSDSP方面具有良好的求解優(yōu)勢。

表3 各算法性能對比

3.2 實例應(yīng)用及分析

現(xiàn)以某企業(yè)中的絲桿升降機(jī)拆卸作為拆卸實例進(jìn)行分析。該產(chǎn)品由33個結(jié)構(gòu)件和13個緊固件組成，其爆炸圖如圖9所示[28]，產(chǎn)品的拆卸信息如表4所示。

表4 絲桿升降機(jī)拆卸信息表

續(xù)表4

運用MISFLA算法求解共有46個零部件的絲桿升降機(jī)拆卸實例，算法參數(shù)設(shè)置如下：青蛙的種群規(guī)模N=100、子群體數(shù)qsp=10、種群迭代次數(shù)Ip=50、子群體迭代次數(shù)Ic=10、最大蛙跳步長Smax=10；選擇拆卸目標(biāo)件分別為蝸輪蝸桿類目標(biāo)件集合fob1={7,11,12}和軸承類目標(biāo)件集合fob2={4,13,19,21,29}，求解結(jié)果如表5所示。

表5 絲桿升降機(jī)在不同拆卸目標(biāo)件下的拆卸結(jié)果

續(xù)表5

由表5可知，當(dāng)拆卸目標(biāo)件為fob1={7,11,12}時，共求得4組Pareto非支配解，各目標(biāo)函數(shù)值的變化范圍為f1∈[272,272.8]，f2∈[3.340 37,2.707 38]，運行時間為25.405 s；在fob2={4,13,19,21,29}的情況下，共求得8組Pareto非支配解，f1∈[305.2,343.6]，f2∈[1.539 99,2.010 98]，運行時間為31.504 s。由此可見，MISFLA可在較短的時間內(nèi)求解不同規(guī)模的拆卸目標(biāo)，并且可以為決策者提供多種拆卸方案，使其可根據(jù)實際情況進(jìn)行多樣化的選擇；另外，多目標(biāo)件的選擇性拆卸可使決策者針對某一特定類別的零部件進(jìn)行高效分類拆卸。

4 結(jié)束語

本文在現(xiàn)有拆卸序列規(guī)劃方法的基礎(chǔ)上，針對其不足方面及存在難點，提出基于多目標(biāo)改進(jìn)蛙跳算法的MSDSP方法，具體如下：

(1)提出基于緊固件約束矩陣和結(jié)構(gòu)件約束矩陣的產(chǎn)品拆卸信息建模方法；以拆卸時間最小化和拆卸收益最大化為目標(biāo)，并融入多目標(biāo)件價值因素構(gòu)建全新的多目標(biāo)選擇性序列評價方法，同時構(gòu)建多目標(biāo)件選擇性拆卸序列規(guī)劃數(shù)學(xué)模型。

(2)融入Pareto思想構(gòu)建多目標(biāo)改進(jìn)蛙跳算法，提出三段式青蛙個體編碼結(jié)構(gòu)；采用基于快速非支配排序與擁擠度比較的思想改進(jìn)排序分組策略；提出基于調(diào)節(jié)位置的調(diào)節(jié)序的方法構(gòu)建子蛙群局部搜索策略，并構(gòu)建新的青蛙個體位置更新公式，同時通過構(gòu)建青蛙個體更新次劣域增加信息源以實現(xiàn)子群體充分交流；提出一種新的交叉和變異思想構(gòu)建全局信息交互策略，以此兼顧信息交互深度和多樣。

(3)通過不同規(guī)模的拆卸實例，將改進(jìn)后的多目標(biāo)蛙跳算法與多目標(biāo)算法NSGA-Ⅱ和粒子群算法進(jìn)行多指標(biāo)對比分析，驗證了該算法的可行性與優(yōu)越性，最后將其應(yīng)用到實際的拆卸實例中。

大型復(fù)雜機(jī)械產(chǎn)品的拆卸具有約束關(guān)系復(fù)雜、零件數(shù)量龐大及多人協(xié)作等特點，后續(xù)將繼續(xù)優(yōu)化該算法，研究多人多目標(biāo)件的選擇性異步并行拆卸序列規(guī)劃方法，進(jìn)一步提高拆卸效率。