朱建峰,徐志剛,蘇開遠(yuǎn)
(山東大學(xué) 機(jī)械工程學(xué)院,山東 濟(jì)南 250061)
拆卸是在對廢舊產(chǎn)品進(jìn)行生命周期末端處理時(shí)的一個(gè)關(guān)鍵的預(yù)先處理過程,拆卸過程是從產(chǎn)品中分離出零件,用來實(shí)現(xiàn)零件的維修、重用、回收、再制造等[1]。拆卸序列規(guī)劃(Disassembly Sequence Planning, DSP)是指根據(jù)產(chǎn)品內(nèi)部結(jié)構(gòu)、裝配約束關(guān)系以及干涉檢驗(yàn)等信息,生成可指導(dǎo)實(shí)際拆卸過程的拆卸序列[2]。再制造過程中,只有部分零部件可再制造重用,因此選擇性拆卸更加符合再制造的實(shí)際。好的拆卸序列規(guī)劃方法能有效提高拆卸效率,降低拆卸成本。
進(jìn)行DSP首先需建立拆卸信息模型,用以表示拆卸約束并產(chǎn)生可行拆卸序列。目前,國內(nèi)外研究中,大多采用連接圖[3]、優(yōu)先關(guān)系圖[4]或鄰接矩陣和優(yōu)先關(guān)系矩陣[5]進(jìn)行拆卸信息建模,這些建模方式方法簡單、建模容易,但得到的可行解空間不完整,在進(jìn)行DSP時(shí)可能遺漏更好的可行解。另外,也有許多文獻(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)點(diǎn),現(xiàn)已成為求解DSP問題的重要方法,例如,基于遺傳算法[9]、蟻群算法[10]、粒子群算法[11]、人工蜂群算法[12]、花朵授粉算法[13]等DSP方法。上述求解方法未考慮多目標(biāo)優(yōu)化問題,或采用加權(quán)法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題,簡化了問題的求解難度,最終只能得到一個(gè)最優(yōu)或近似最優(yōu)解,且沒有考慮到多目標(biāo)件選擇性拆卸的情況,具有一定的局限性。
混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)[14]結(jié)合模因演算算法(Memetic Algorithm, MA)和粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法的優(yōu)點(diǎn),具有概念簡單、參數(shù)少、計(jì)算速度快、全局尋優(yōu)能力出色、魯棒性強(qiáng)等特點(diǎn)。SFLA因其獨(dú)特的優(yōu)勢已被廣泛應(yīng)用于函數(shù)優(yōu)化[15]、生產(chǎn)調(diào)度[16]、資源網(wǎng)絡(luò)優(yōu)化[17]和圖像處理[18]等方面,同時(shí)SFLA在求解旅行商問題[19-20]、背包問題[21]、時(shí)間表問題[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)蛙跳算法,同時(shí)構(gòu)建了MSDSP的數(shù)學(xué)模型,通過不同拆卸規(guī)模的拆卸實(shí)例,并與多種算法進(jìn)行對比分析,驗(yàn)證了本文所提方法的可行性與優(yōu)越性,同時(shí)將其運(yùn)用到具體的拆卸實(shí)例中。
MSDSP是指在滿足拆卸優(yōu)先關(guān)系約束的前提下,為拆卸所有目標(biāo)零部件,以拆卸時(shí)間最小化和拆卸收益最大化為目標(biāo),確定最優(yōu)(近似最優(yōu))的可行拆卸序列。
本文在文獻(xiàn)[23]的基礎(chǔ)上,對其拆卸信息表達(dá)方法進(jìn)行補(bǔ)充和優(yōu)化,提出利用緊固件約束矩陣和結(jié)構(gòu)件約束矩陣構(gòu)建產(chǎn)品的拆卸信息模型。
本文對產(chǎn)品拆卸建模作如下說明:
(1)結(jié)構(gòu)件指除緊固件以外最小的拆卸單元;緊固件指用來固連兩個(gè)或多個(gè)結(jié)構(gòu)件的機(jī)械部件,例如螺栓、螺釘、螺柱等。
(2)緊固件與結(jié)構(gòu)件之間的約束關(guān)系作為已知條件,通過用戶輸入方式獲得。
(1)緊固件約束矩陣定義
緊固件約束矩陣表示拆卸產(chǎn)品中緊固件和結(jié)構(gòu)件之間的約束關(guān)系,其中矩陣的行序號(hào)表示緊固件序號(hào),列序號(hào)表示結(jié)構(gòu)件序號(hào),緊固件約束矩陣
(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)系,其中矩陣的行序號(hào)和列序號(hào)都表示結(jié)構(gòu)件序號(hào),結(jié)構(gòu)件約束矩陣
(2)
如圖1所示為某待拆卸產(chǎn)品的拆卸模型示例圖,該產(chǎn)品由5個(gè)緊固件和4個(gè)結(jié)構(gòu)件裝配而成,由于圖例為二維裝配圖且產(chǎn)品底端固定,只考慮3個(gè)拆卸方向:+X、-X、+Y,由上述緊固件約束矩陣和結(jié)構(gòu)件約束矩陣的建立方法可得該產(chǎn)品的緊固件約束矩陣G1和結(jié)構(gòu)件約束矩陣G2,分別如下所示:
為便于數(shù)學(xué)模型的建立,對MSDSP進(jìn)行如下假設(shè):①所有零部件均可拆卸;②考慮到再制造拆卸實(shí)際中,只有部分零部件可再制造重用,本文在拆卸收益計(jì)算時(shí)只考慮所有目標(biāo)件的價(jià)值。
描述MSDSP模型用到的符號(hào)及其定義如下:
(1)N為待拆卸產(chǎn)品中零部件的數(shù)量,N=n+m,其中:n為所有結(jié)構(gòu)件的數(shù)量,m為所有緊固件的數(shù)量。
(2)i為所有零部件的編號(hào),i∈{1,2,…,N}。
(3)P為所有結(jié)構(gòu)件編號(hào)的集合,P={1,2,…,n}。
(4)J為所有緊固件編號(hào)的集合,J={n+1,n+2,…,n+m}。
(5)Ng為拆除所有目標(biāo)零部件需要的拆卸操作數(shù)量。
(6)j為拆卸操作的編號(hào),j∈{1,2,…,Ng}。
(8)coij為緊固件約束矩陣G1中的元素。
(10)Dj為執(zhí)行拆卸任務(wù)時(shí)被干涉的拆卸方向數(shù),0≤Dj≤s。
(11)Td(x)為拆卸方向變換消耗的時(shí)間。
(12)Tt(x)為拆卸工具變換消耗的時(shí)間。
(13)Tc(x)為移除時(shí)緊固件與結(jié)構(gòu)件的切換消耗的時(shí)間。
(14)Tp(x)為移除結(jié)構(gòu)件時(shí)額外消耗的時(shí)間。
(15)Tb(x)為移除零部件的基本拆卸時(shí)間。
(16)V(x)為零部件可再利用價(jià)值指數(shù)。
(17)E(x)為零部件回收收益。
基于以上定義,以拆卸過程中拆卸時(shí)間最小化和拆卸收益最大化為目標(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)分別表示最小化拆卸時(shí)間和最大化拆卸收益的目標(biāo)函數(shù);式(5)表示緊固件i能被拆卸的約束條件;式(6)表示已拆除相關(guān)緊固件的結(jié)構(gòu)件i能被拆卸的約束條件;式(7)為拆除所有目標(biāo)件所拆卸的所有零部件均屬于待拆卸產(chǎn)品中的部件;式(8)表示包括目標(biāo)件在內(nèi),每個(gè)零部件只能被拆卸一次;式(9)表示每執(zhí)行一次拆卸操作,必須且只能拆掉一個(gè)零部件。
本文通過多目標(biāo)優(yōu)化理論設(shè)計(jì)基于多目標(biāo)改進(jìn)蛙跳算法(MISFLA),主要包括青蛙個(gè)體編碼與可行解構(gòu)造、蛙群分組、局部搜索及全局信息混合等部分。
MISFLA的青蛙個(gè)體結(jié)構(gòu)與多目標(biāo)件選擇性DSP問題的解的表現(xiàn)形式相對應(yīng),即每一個(gè)青蛙個(gè)體表示為一個(gè)可行的拆卸序列。青蛙個(gè)體編碼結(jié)構(gòu)定義如下:
青蛙個(gè)體Frog采用三段式編碼,總體包括偽碼fv、實(shí)碼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中,定義臨時(shí)變換矩陣G3和G4,使G3=G1,G4=G2。
(3)從A中隨機(jī)選擇一個(gè)元素a,放入X最左端,并在A中刪除元素a;然后判斷元素a的類型,若元素a為緊固件,轉(zhuǎn)步驟(4),若元素a為結(jié)構(gòu)件,則轉(zhuǎn)步驟(5)。
(4)更新G3(刪除G3中a所在行的所有元素),然后根據(jù)G1,對于a所連接的每一個(gè)結(jié)構(gòu)件,在G4中由式(6)判斷其是否可拆,若可拆,則將相應(yīng)結(jié)構(gòu)件編號(hào)放入A中。
(5)更新G3(刪除G3中a所在行的所有元素),同時(shí)更新G4(刪除G4中a所在行與列的所有元素),然后根據(jù)G1,對a所阻擋的每一個(gè)緊固件,在G3中由式(5)判斷其是否可拆,若可拆,則將相應(yīng)緊固件放入a中;同時(shí),根據(jù)G2,對結(jié)構(gòu)件a在任一拆卸方向所阻擋的每一個(gè)結(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è)體構(gòu)造完成。
DSP的目的是為了獲取拆卸時(shí)間最短和拆卸經(jīng)濟(jì)效益最好的可行拆卸序列。本文的優(yōu)化目標(biāo)函數(shù)如式(3)和式(4)所示,拆卸時(shí)間包括零部件拆卸方向變換消耗的時(shí)間、拆卸工具變換消耗的時(shí)間、基本拆卸時(shí)間、移除結(jié)構(gòu)件時(shí)額外消耗的時(shí)間、拆除時(shí)緊固件與結(jié)構(gòu)件的切換消耗的時(shí)間,拆卸收益包括零部件可再利用價(jià)值指數(shù)及回收收益,各目標(biāo)函數(shù)值依據(jù)實(shí)碼fr進(jìn)行計(jì)算。
因?yàn)楸疚纳婕岸鄠€(gè)目標(biāo)的協(xié)同優(yōu)化,無法簡單地對解的優(yōu)劣性進(jìn)行排序,所以引入Pareto最優(yōu)解集理論和NSGA-Ⅱ中的快速非支配排序及擁擠距離比較思想進(jìn)行蛙群分組。
青蛙個(gè)體支配關(guān)系,即任意兩個(gè)具有k個(gè)子目標(biāo)的青蛙個(gè)體Frog1和Frog2,若滿足式(11),則稱Frog1支配Frog2,記為Frog1?Frog2。
(11)
若同時(shí)存在某目標(biāo)i,使得fi(Frog1)優(yōu)于fi(Frog2),以及目標(biāo)j,使得fj(Frog1)優(yōu)于fj(Frog2),則兩青蛙個(gè)體互不支配,F(xiàn)rog1和Frog2對應(yīng)的解互為非支配解或Pareto解。若在決策空間中不存在某個(gè)青蛙支配當(dāng)前青蛙,則當(dāng)前青蛙個(gè)體對應(yīng)的解為Pareto最優(yōu)解,多目標(biāo)優(yōu)化問題會(huì)產(chǎn)生一組Pareto最優(yōu)解,即Pareto最優(yōu)解集,所有Pareto最優(yōu)解對應(yīng)目標(biāo)值的連線構(gòu)成Pareto最優(yōu)前沿。
基于快速非支配排序及擁擠度比較思想的蛙群分組方式如下:
(1)計(jì)算種群中每個(gè)青蛙個(gè)體的目標(biāo)函數(shù)值f1和f2,定義集合L(l),用以存放不同非支配等級的Pareto解,l表示非支配等級,l越小,等級越高。為種群中所有青蛙個(gè)體定義兩個(gè)參數(shù)nF和SF,分別表示種群中Frog支配個(gè)體的個(gè)數(shù)和被Frog支配的個(gè)體的集合。
(2)種群分級。計(jì)算每個(gè)青蛙個(gè)體的nF和SF,將種群中所有nF=0的個(gè)體保存到L(1)中,對于L(1)中L(1)的每個(gè)個(gè)體i,遍歷其所支配個(gè)體集合SFi中的每個(gè)個(gè)體j,執(zhí)行nFj=nFj-1,若nF=0,則將該個(gè)體j保存到L(2)中,依此類推,直至整個(gè)種群被分級。
(3)擁擠度計(jì)算。設(shè)共有k個(gè)目標(biāo)函數(shù),依照每個(gè)優(yōu)化目標(biāo)函數(shù)值fj,將種群中所有個(gè)體進(jìn)行升序排列,令邊界的兩個(gè)個(gè)體擁擠度為∞,其他個(gè)體i的擁擠度
(12)
(4)青蛙個(gè)體排序。首先根據(jù)非支配等級l進(jìn)行排序,l越小,青蛙個(gè)體越優(yōu)秀,對于相同等級的個(gè)體再依照擁擠度進(jìn)行排序,擁擠度越大,個(gè)體越優(yōu)秀,最終將所有個(gè)體從優(yōu)到劣進(jìn)行排序。
(5)依照排序排名,第i個(gè)青蛙子群體Yi的分組公式如下:
Yi={Frogi+qsp(j-1)|1≤j≤qsf},1≤i≤qsp。
(13)
式中:qsp為青蛙子群體數(shù)量;qsf為每個(gè)子群體中的青蛙個(gè)體數(shù)量;i,j為整數(shù)。
由于標(biāo)準(zhǔn)混合蛙跳算法的局部搜索策略不適用于DSP問題的求解,本文引入調(diào)節(jié)因子和調(diào)節(jié)序的思想優(yōu)化設(shè)計(jì)局部搜索策略。
在旅行商問題(Traveling Salesman Problem, TSP)的求解中,調(diào)節(jié)因子用于改變兩個(gè)城市的先后訪問順序,調(diào)節(jié)序則是由多個(gè)調(diào)節(jié)因子構(gòu)成的有序序列[20]。本文針對DSP問題,借鑒遺傳算法用于離散組合優(yōu)化問題時(shí)對優(yōu)先關(guān)系保留交叉算子的相關(guān)處理,提出基于調(diào)節(jié)位置的調(diào)節(jié)序?qū)η嗤軅€(gè)體中的偽碼段fv進(jìn)行調(diào)節(jié)。
(1)調(diào)節(jié)因子與調(diào)節(jié)序
已知某拆卸序列fv,定義調(diào)節(jié)因子為Af(α,β),其作用是將fv中第β個(gè)零部件插入到第α個(gè)零部件之前,產(chǎn)生一個(gè)新序列。假設(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個(gè)調(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為兩個(gè)不同的拆卸任務(wù)序列,則Afs(γ,δ)?(fv1Θfv2)表示將fv1中第γ個(gè)零部件與第δ個(gè)零部件之間的序列按照其在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中第γ個(gè)零部件與第δ個(gè)零部件之間的零部件在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è)體更新策略構(gòu)建
設(shè)當(dāng)前迭代子群體中的最差個(gè)體為Frogw、最好個(gè)體為Frogb、全局最優(yōu)個(gè)體為Frogg,基于上述調(diào)節(jié)序思想構(gòu)建更新策略,對最差青蛙個(gè)體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,并計(jì)算newFrogw的各個(gè)目標(biāo)函數(shù)值,判斷newFrogw的支配個(gè)體數(shù)num(SnF)與被支配的個(gè)體數(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è)體的構(gòu)造方法重新構(gòu)造一個(gè)newFrogw。
圖2所示為青蛙個(gè)體執(zhí)行更新策略的一個(gè)實(shí)例,圖中,調(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)系,從而避免了因驗(yàn)證青蛙個(gè)體是否可行帶來的時(shí)間浪費(fèi)。每一個(gè)調(diào)節(jié)因子表示一個(gè)青蛙步長,通過smax可有效地控制青蛙個(gè)體跳躍的距離,避免因跳躍距離過大而找不到最優(yōu)解或因跳躍距離過小導(dǎo)致移動(dòng)速度緩慢。同時(shí),在進(jìn)化過程中實(shí)現(xiàn)了實(shí)碼串frw的長度、零部件優(yōu)先順序的多樣性調(diào)節(jié),保證了青蛙個(gè)體的多樣性。
(4)青蛙個(gè)體更新信息源增加
在基本蛙跳算法的子群更新策略中,信息交互的來源只有全局最優(yōu)解、局部最優(yōu)解和局部最劣解,因此本文通過增加信息交互源讓子群內(nèi)鄰域解參與到信息交互中,實(shí)現(xiàn)子群內(nèi)部信息的充分交流。具體策略如下:
在每個(gè)子群體局部最劣解更新的同時(shí),選擇除局部最劣解以外的4個(gè)次劣解構(gòu)成局部次劣域,同時(shí)選擇除局部最優(yōu)解以外的4個(gè)次優(yōu)解構(gòu)成局部次優(yōu)域,從局部次劣域中隨機(jī)選取2個(gè)不同的次劣解Frogw1與Frogw2作為待更新解,從局部次優(yōu)域中隨機(jī)選取2個(gè)不同的次優(yōu)解Frogb1與Frogb2分別對Frogw1和Frogw2進(jìn)行更新,次劣域更新公式如下:
s=min{int[r·length(Afs(γ,δ)?
(fvw1Θfvb1))],smax};
(19)
Afi∈Afs(γ,δ)?(fvw1Θfvb1)。
(20)
基本蛙跳算法在全局混合的過程中只是進(jìn)行了簡單的信息交流,各個(gè)子群信息并未進(jìn)行深度挖掘。但是,一味盲目追求交互深度會(huì)增加種群的相似性和單一性,導(dǎo)致后續(xù)迭代中蛙群分組的價(jià)值降低。針對這一問題,為兼顧信息交互深度和個(gè)體多樣性,本文提出一種滿足優(yōu)先約束關(guān)系的三段隨機(jī)交叉和單點(diǎn)變異思想。將qsp個(gè)子群的局部最優(yōu)解進(jìn)行隨機(jī)交叉,生成qsp個(gè)新解分別代替各子群的局部最劣解,接著再進(jìn)入全局混合,然后對種群所有個(gè)體進(jìn)行單點(diǎn)變異。
三段隨機(jī)交叉策略如圖3所示,即隨機(jī)產(chǎn)生4個(gè)交叉點(diǎn)1~4,對每兩個(gè)交叉點(diǎn)之間的片段,從起始交叉點(diǎn)往后隨機(jī)選取長度為2~5不等的碼段進(jìn)行交叉,將父代P1中1-1′、2-2′、3-3′之間的元素按照父代P2中的相同元素的排列順序進(jìn)行調(diào)節(jié),并填充到子代C1的相應(yīng)位置,剩下的片段則全部賦值給子代C1。
本文采用單點(diǎn)變異方式構(gòu)建變異算子,如圖4所示,其基本思想如下:首先在P1中產(chǎn)生1個(gè)隨機(jī)變異點(diǎn)a,將a點(diǎn)之前的序列賦值給C1,a點(diǎn)之后的序列構(gòu)建步驟如下:①刪除約束矩陣G1和G2中關(guān)于a點(diǎn)之前片段所有元素的優(yōu)先關(guān)系約束;②在新的約束矩陣G1和G2條件下,依據(jù)產(chǎn)生初始解的過程,對a點(diǎn)之后的片段所有元素進(jìn)行隨機(jī)重新排列,完成C1的構(gòu)建。
步驟1算法基本參數(shù)設(shè)定(青蛙的種群規(guī)模N、子群體數(shù)qsp、種群迭代次數(shù)Ip、子群體迭代次數(shù)Ic、最大蛙跳步長Smax)。
步驟2種群初始化。按照2.1節(jié)所述可行序列的構(gòu)造方法隨機(jī)產(chǎn)生N個(gè)可行解,并計(jì)算每個(gè)青蛙個(gè)體的各個(gè)目標(biāo)函數(shù)值。
步驟3蛙群分組。根據(jù)2.2節(jié)所述的蛙群分組方法,將種群中所有個(gè)體劃分至qsp個(gè)子群體中。
步驟4局部搜索。根據(jù)2.3節(jié)所述的青蛙個(gè)體更新策略,對每個(gè)子群體進(jìn)行局部搜索。
步驟5全局信息交流。根據(jù)2.4節(jié)所述的全局信息混合策略,重新混合所有青蛙個(gè)體。
步驟6計(jì)算每個(gè)青蛙個(gè)體的各個(gè)目標(biāo)函數(shù)值,并更新種群中的Pareto非支配解集。
步驟7判斷是否滿足算法終止條件,若滿足,則結(jié)束搜索并輸出Pareto非支配解集;否則,轉(zhuǎn)步驟3,繼續(xù)搜索。
MISFLA的算法流程圖如圖5所示。
本文基于Visual Studio 2015,采用VC++語言編寫算法程序。運(yùn)行本應(yīng)用程序的計(jì)算機(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ī)模的拆卸實(shí)例并與多種算法作對比,說明所提算法MISFLA的可行性與優(yōu)越性。
以文獻(xiàn)[25]中的工業(yè)機(jī)械臂模型為算例求解MSDSP問題,該模型由23個(gè)零部件組成,其三維模型如圖6所示,由于原始拆卸模型中部分拆卸信息不全,對其進(jìn)行補(bǔ)充后的拆卸信息如表1所示。
表1 工業(yè)機(jī)械臂拆卸信息表
續(xù)表1
通過正交試驗(yàn)及統(tǒng)計(jì)分析,在綜合考慮解的質(zhì)量與程序運(yùn)行時(shí)間的基礎(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é)果
為綜合評價(jià)本文所提MISFLA的性能,將本文算法與帶精英策略的快速非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm Ⅱ, NSGA-Ⅱ)[26]、粒子群算法(Particle Swarm Optimization, PSO)[27]和基本蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)進(jìn)行對比,本文均采用C++語言實(shí)現(xiàn)上述各算法的編寫,并運(yùn)行于相同的計(jì)算機(jī)環(huán)境中,各算法在目標(biāo)件為fob1和fob2時(shí),求解的Pareto前沿曲線分別如圖7和圖8所示。同時(shí)本文采用程序平均運(yùn)行時(shí)間tr、反轉(zhuǎn)世代距離IGD、間距指標(biāo)SP和Pareto非劣解的個(gè)數(shù)nump四個(gè)指標(biāo)綜合綜合評價(jià)各算法,對比結(jié)果如表3所示。其中:IGD用于評價(jià)所求Pareto非劣解與真實(shí)Pareto的前沿的總體差距,IGD值越小表示所求Pareto前沿的收斂性和分布多樣性越好,即更加逼近真實(shí)Pareto前沿;SP用于評價(jià)Pareto前沿分布的均勻性,SP越小表示分布均勻性越好。本文計(jì)算IGD和SP的公式如下:
(21)
(22)
由圖7和表3可知,當(dāng)拆卸目標(biāo)件為{6,11,12}時(shí),NSGAⅡ的運(yùn)行時(shí)間較好、收斂性及Pareto非劣解的求解能力適中,但其分布均勻性較差;PSO的運(yùn)行時(shí)間及分布均勻性適中,其收斂性及Pareto非劣解的求解能力較差;基本SFLA的運(yùn)行時(shí)間、收斂性、Pareto非劣解的求解能力適中,且分布均勻性較好;MISFLA運(yùn)行時(shí)間稍長,但其在收斂性、Pareto非劣解的求解能力及分布均勻性方面均表現(xiàn)良好。當(dāng)拆卸目標(biāo)件為{5,6,9,12}時(shí),雖然MISFLA的運(yùn)行時(shí)間略長,但在求解質(zhì)量、收斂性方面遠(yuǎn)優(yōu)于其余3種算法,且表現(xiàn)出了良好的分布均勻性。因此,MISFLA的綜合性能優(yōu)于其余3種算法,在求解MSDSP方面具有良好的求解優(yōu)勢。
表3 各算法性能對比
現(xiàn)以某企業(yè)中的絲桿升降機(jī)拆卸作為拆卸實(shí)例進(jìn)行分析。該產(chǎn)品由33個(gè)結(jié)構(gòu)件和13個(gè)緊固件組成,其爆炸圖如圖9所示[28],產(chǎn)品的拆卸信息如表4所示。
表4 絲桿升降機(jī)拆卸信息表
續(xù)表4
運(yùn)用MISFLA算法求解共有46個(gè)零部件的絲桿升降機(jī)拆卸實(shí)例,算法參數(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}時(shí),共求得4組Pareto非支配解,各目標(biāo)函數(shù)值的變化范圍為f1∈[272,272.8],f2∈[3.340 37,2.707 38],運(yùn)行時(shí)間為25.405 s;在fob2={4,13,19,21,29}的情況下,共求得8組Pareto非支配解,f1∈[305.2,343.6],f2∈[1.539 99,2.010 98],運(yùn)行時(shí)間為31.504 s。由此可見,MISFLA可在較短的時(shí)間內(nèi)求解不同規(guī)模的拆卸目標(biāo),并且可以為決策者提供多種拆卸方案,使其可根據(jù)實(shí)際情況進(jìn)行多樣化的選擇;另外,多目標(biāo)件的選擇性拆卸可使決策者針對某一特定類別的零部件進(jìn)行高效分類拆卸。
本文在現(xiàn)有拆卸序列規(guī)劃方法的基礎(chǔ)上,針對其不足方面及存在難點(diǎn),提出基于多目標(biāo)改進(jìn)蛙跳算法的MSDSP方法,具體如下:
(1)提出基于緊固件約束矩陣和結(jié)構(gòu)件約束矩陣的產(chǎn)品拆卸信息建模方法;以拆卸時(shí)間最小化和拆卸收益最大化為目標(biāo),并融入多目標(biāo)件價(jià)值因素構(gòu)建全新的多目標(biāo)選擇性序列評價(jià)方法,同時(shí)構(gòu)建多目標(biāo)件選擇性拆卸序列規(guī)劃數(shù)學(xué)模型。
(2)融入Pareto思想構(gòu)建多目標(biāo)改進(jìn)蛙跳算法,提出三段式青蛙個(gè)體編碼結(jié)構(gòu);采用基于快速非支配排序與擁擠度比較的思想改進(jìn)排序分組策略;提出基于調(diào)節(jié)位置的調(diào)節(jié)序的方法構(gòu)建子蛙群局部搜索策略,并構(gòu)建新的青蛙個(gè)體位置更新公式,同時(shí)通過構(gòu)建青蛙個(gè)體更新次劣域增加信息源以實(shí)現(xiàn)子群體充分交流;提出一種新的交叉和變異思想構(gòu)建全局信息交互策略,以此兼顧信息交互深度和多樣。
(3)通過不同規(guī)模的拆卸實(shí)例,將改進(jìn)后的多目標(biāo)蛙跳算法與多目標(biāo)算法NSGA-Ⅱ和粒子群算法進(jìn)行多指標(biāo)對比分析,驗(yàn)證了該算法的可行性與優(yōu)越性,最后將其應(yīng)用到實(shí)際的拆卸實(shí)例中。
大型復(fù)雜機(jī)械產(chǎn)品的拆卸具有約束關(guān)系復(fù)雜、零件數(shù)量龐大及多人協(xié)作等特點(diǎn),后續(xù)將繼續(xù)優(yōu)化該算法,研究多人多目標(biāo)件的選擇性異步并行拆卸序列規(guī)劃方法,進(jìn)一步提高拆卸效率。