基于改進人工蜂群算法的產品拆卸序列規劃

宋守許　張文勝　張雷

合肥工業大學，合肥，230009

?

基于改進人工蜂群算法的產品拆卸序列規劃

宋守許張文勝張雷

合肥工業大學，合肥，230009

為了提高復雜產品拆卸序列規劃效率，提出了一種改進的人工蜂群算法用于此類問題求解。通過拆卸混合圖表達產品零部件之間的連接關系和優先約束關系，并推導出可行拆卸序列的約束表達式，建立拆卸序列規劃數學模型和適應度計算公式。對初始種群進行了優先約束規劃，提出一種可行度算法用于蜂群對蜜源的搜尋與選擇。定義了自適應選擇參數、動態平衡可行度與適應度算法的優先配比，以實現復雜產品拆卸序列規劃的快速求解。最后以內嚙合齒輪泵為實例，利用所提方法進行了拆卸序列規劃求解，通過分析實驗結果，并對比傳統人工蜂群算法，證明了該方法的可行性和高效性。

復雜產品；拆卸序列規劃；人工蜂群算法；約束優化

0　引言

拆卸是回收或者維修的重要組成部分[1]，對廢舊產品進行拆卸處理能減輕環境污染，促進資源回收利用。拆卸序列規劃就是提取產品的結構與裝配信息，形成一定順序的可行拆卸序列，并挑選出符合某種條件的最優拆卸序列。許多學者對其展開了研究。

早期的研究主要傾向于圖論研究，如緊固件圖[2]、AND/OR圖[3]、Petri網[4]等方法。這些方法在一定程度上解決了產品拆卸序列規劃中的問題，但隨著產品結構的復雜化，拆卸所涉及的零件數量也呈指數增長，傳統的拆卸序列規劃方法已經無法滿足復雜產品的拆卸需求。于是許多學者利用智能進化算法來解決這一問題。張雷等[5]通過人工蜂群(artificial bee colony,ABC)算法對復雜產品拆卸序列進行并行求解。邢宇飛等[6]通過蟻群算法搜索可行解并計算各個解之間的支配關系，得到Pareto解集，從而實現拆卸序列規劃。張秀芬等[7]將拆卸混合圖模型映射到粒子群模型，通過粒子群算法實現了復雜產品的最優拆卸序列規劃。王輝等[8]將拆卸序列規劃問題轉化為最優路徑搜索和尋優解問題，并通過蟻群算法進行求解。吳昊等[9]利用二叉樹算法對初始種群的產生、種群的交叉和變異過程進行優化，通過改進的遺傳算法實現了拆卸序列規劃的求解。

上述研究成果介紹了智能算法在拆卸序列規劃求解方面的應用，其中人工蜂群算法相對于其他傳統算法有著較好的求解質量[10]，在處理組合優化問題中有著明顯的優勢。但由于人工蜂群算法[11]是一種新興算法，在拆卸序列規劃方面的應用研究還存在許多不足。故本文根據拆卸序列規劃的約束特性，對傳統人工蜂群算法中種群的初始化，引領蜂和跟隨蜂的活動準則進行了優化，彌補了其在約束判定方面的不足，提高了復雜產品拆卸序列規劃的求解效率。

1　拆卸序列規劃問題描述

1.1拆卸混合圖模型

為了描述產品各個零件之間的連接關系、優先約束關系，本文選擇拆卸混合圖來表達產品拆卸模型。拆卸混合圖[12]描述了各個零件之間的約束關系，由若干節點、無向邊和有向邊根據一定規則組合而成。

G={V,E,DE}

其中，G代表混合圖；V代表節點，表示產品的零件或子裝配體，若產品有n個零件，則V={v1,v2,…,vn}；E為無向邊；DE為有向邊。例如圖1某產品拆卸混合圖所示，頂點1,2,…,9表示零件或者子裝配體，無向邊1到2表示零件1與零件2直接存在連接接觸關系，有向邊1到4表示零件1與零件4存在優先約束關系，且零件1先于零件4拆卸。

圖1　拆卸混合圖

為了便于拆卸分析，將無向邊集合E和有向邊集合DE用連接矩陣Gc和優先約束矩陣Gp來表示，Gc對應{V,E},Gp對應{V,DE}。

其中，

i=j時，Cij=0。

i=j時，Pij=0。

于是可以得出圖1拆卸混合圖的連接矩陣和優先約束矩陣分別為

1.2拆卸序列求解模型

拆卸序列規劃實質就是從產品零部件的隨機排列組合中，選出一條可行且最優的拆卸序列。

可行拆卸序列要求當前拆卸零件必須具有可拆性?？刹鹦读慵13]是指當前零件沒有受到其他零件的優先約束，即滿足：

(1)

并且，只與其他零件中的一個有連接關系，即滿足：

(2)

在拆卸序列中，一個單元拆卸完畢后，需要對連接矩陣和優先約束矩陣進行更新，然后判斷下一個單元的可拆性。拆卸序列的可行性通過式(1)、式(2)約束。

同時，在上述可行拆卸序列中，還需要選取最優的拆卸序列。在不同的拆卸序列中，零件與零件之間拆卸方向與拆卸工具是否發生變化也是不同的。為了在可行拆卸序列中尋求拆卸時間最短的序列，需要盡可能少地進行工具與方向的轉變。因此，將拆卸方向變化及拆卸工具變化作為拆卸序列最優的判定指標，則有

(3)

式中，T(x)為可行拆卸序列x對應的適應值；k為拆卸序列中第k個零件；s為拆卸序列總的操作次數；ωd為拆卸方向變化權重系數;ωt為拆卸工具變化權重系數。

2　基于改進人工蜂群算法的拆卸序列優化

人工蜂群算法是由土耳其學者Karaboga[14]于2005年提出的一種模擬蜜蜂群尋找優秀蜜源的智能優化算法，也是典型的元啟發式算法。人工蜂群算法具有搜索精度高、魯棒性強和易于操作等特點，在多約束組合優化問題的求解過程中具有明顯的優勢。而產品的拆卸序列規劃從數學本質來說是一個NP困難問題，適合利用人工蜂群算法進行求解。與蟻群算法、粒子群算法和遺傳算法相比較，人工蜂群算法的突出優點是在每次迭代過程中都進行全局搜索和局部搜索，能夠較大程度地避免陷入局部最優[15]。同時函數優化測試結果[16-17]也表明，人工蜂群算法具有更優異的優化性能。這也是本文選取人工蜂群算法作為求解方法的理由。

2.1初始種群優先約束算法

拆卸序列規劃問題是一個具有強約束條件的組合優化問題，在尋優行為之前要滿足可行拆卸序列的約束條件。通常情況下初始種群無法充分提取拆卸混合圖的信息，故本文提出初始種群優先約束算法，對初始種群進行優先約束規劃。

在優先約束算法中，二叉樹作為優先約束儲存結構，樹結構中每個節點最多有兩個子樹，且有左右、次序之分。當采用中序遍歷時，左子樹信息在根節點之前讀取，右子樹信息在根節點之后讀取。

在基于零件的二叉樹[18]結構中，每個節點代表一個拆卸單元，左子樹所代表的拆卸單元總是先于右子樹進行拆卸，根節點則介于二者之間。

優先約束矩陣行和表示該行對應的零件在被拆卸前需要優先拆卸的零件個數，作為優先約束算法中的各零件排列順序的主要判定依據。在優先約束矩陣Gp中，記

(4)

式中，Si為優先約束矩陣行和(以下簡稱行和)，表示第i行各元素的值之和；pij為不同零件間優先約束關系對應的數值。

定義Sk為零件k的行和；m為與當前零件k存在約束關系的零件集合。則優先約束算法的具體步驟如下。

(1)根據上述定義獲取各個零件的優先矩陣行和；令k=1。

(2)判斷行和值Sk：①若Sk=-1，則說明該零件已被操作，跳過此零件，k←k+1;②若Sk=0，則說明沒有其他零件對此零件k有優先約束關系,令k所在的節點為新的根節點，在根節點的右子節點插入k+1所代表的零件,k←k+1;③若Sk≥1，則利用優先約束矩陣搜索與此零件有優先約束關系的零件集合m。a.當m不存在時，說明對此零件有優先約束關系的零件已被拆卸。令Sk=0，并返回步驟(2)。b.當m存在多個時，令k所在的節點為新的根節點，利用各零件行和Si進行排序，由大到小依次插入根節點的左子節點，每一次插入后令插入零件為新的根節點。并將所有零件m的行和置為-1，避免再次操作。最后，令Sk=0，并返回步驟(2)。

(3)如果k為拆卸序列最后一個零件，則轉步驟(4)；否則，返回步驟(2)。

(4)優化完畢，算法結束。

圖2　二叉樹信息結構

2.2可行度算法與適應度算法

在蜜蜂搜尋和選擇蜜源的過程中，提出一種可行度算法，以拆卸序列約束滿足程度為基準，指導蜜蜂活動傾向。

一條拆卸序列的約束滿足程度取決于拆卸序列可行值與拆卸序列最大維數的比值，則有

(5)

式中，Fx為拆卸序列x的可行度，即表示拆卸序列的約束滿足情況；Mx為拆卸序列x可行值，即在拆卸序列中依次連續可拆零件的個數；D為拆卸序列最大維數。

其中拆卸序列可行值M的求解問題可描述為

findXl={X1,X2,…,Xn}

maxg(Xl)

(6)

式中，集合{X1,X2,…,Xl,…Xn}代表一條拆卸序列；Xl為當前拆卸零件；函數g(Xl)為Xl在拆卸序列中的次序；約束條件為可行拆卸序列的約束條件;PVij和CVij分別為可變優先約束矩陣的第i行、第j列元素和可變連接矩陣的第i行、第j列元素。

為了求解該問題，按照拆卸序列次序依次判斷當前零件Xl是否具有可拆性，令l=1。如果Xl滿足約束條件，則表明當前零件Xl具有可拆性。此時l←l+1，拆卸此零件。當某一零件被拆除時，與之相關的連接關系和優先約束關系也應當去除。反映到可變矩陣上就是：可變連接矩陣CV第i行、第i列所有元素置0，可變優先約束矩陣PV第i列所有元素置0，然后循環此過程，直至所有零件都被拆卸。如果Xl不滿足約束條件，則l←l-1，求解結束。取函數g(Xl)的最大值即可獲得拆卸序列可行值M。

在引領蜂搜尋蜜源時，由于可行值M之前的元素都已滿足約束，只需對其之后元素進行交換即可得到新蜜源；引領蜂通過貪婪準則對新舊蜜源的可行度F進行比較，保留可行度較高者為優秀蜜源；引領蜂將蜜源信息共享于跟隨蜂，可行度較高的拆卸序列將吸引更多跟隨蜂，其選擇概率公式為

(7)

式中，p′x為拆卸序列x的可行度選擇概率；NP為種群數量。

相應地，以適應度為依據的蜜源選擇算法稱之為適應度算法。引領蜂選擇蜜源適應度較高者為優秀蜜源，并將信息共享于跟隨蜂。跟隨蜂根據轉移概率公式進行選擇：

(8)

2.3自適應選擇算法

可行度算法雖然提高了收斂速度，但新蜜源僅影響可行值M之后的元素，難以保證種群多樣性。而適應度算法面向的是拆卸序列中所有元素，在解集多樣性的方面優于可行度算法。理想情況下，在算法初期采用可行度算法進行快速約束收斂，中后期逐步采用適應度算法擴大搜索范圍和深度，保證種群多樣性。本文綜合兩者優點，定義了一種自適應選擇參數：

(9)

式中，H為可行拆卸序列的數量，其值是由種群中滿足可行度F=1的拆卸序列個數決定。

自適應選擇算法采用輪盤賭的方式決定可行度算法與適應度算法的傾向性。即在區間[0,1]中產生一個均勻分布的隨機數r，如果參數α小于r，則采用可行度算法；反之，則采用適應度算法。

算法初期，絕大多數拆卸序列沒有滿足約束關系，參數α數值較小，可行度算法使用頻率居多；隨著可行的拆卸序列逐漸增多，參數α逐漸增大，適應度算法會逐步取代可行度算法，以保證種群的多樣性。而適應度算法又會降低α的數值，最終二者會在某一范圍內實現動態平衡，交替作用于拆卸序列規劃的求解。

2.4拆卸序列規劃求解流程

至此，可以得出基于改進ABC算法的拆卸序列規劃求解流程，如圖3所示，步驟如下：

圖3　算法流程圖

(2)根據2.3節自適應選擇算法決定蜜蜂采用可行度算法亦或適應度算法進行計算。

(4)轉移概率的計算。在引領蜂搜索結束后，通過搖擺舞的方式將信息與跟隨蜂共享，跟隨蜂通過式(7)、式(8)計算轉移概率并跟隨。

(5)跟隨蜂搜尋新序列并記錄最優序列。當跟隨蜂通過轉移概率選擇序列后，采用與引領蜂一樣的方式搜索新序列并記錄最優序列。

(6)若通過有限次循環不能被進一步優化，則放棄原序列，偵查蜂根據步驟(1)方法隨機生成新序列進行探索。

(7)判斷是否滿足終止條件，是，則結束循環；否，則返回步驟(2)繼續循環。

3　實例分析

基于本文的求解方法，使用MATLAB編寫了改進人工蜂群算法程序，并以內嚙合齒輪泵為例進行了分析。該模型包括20個最小拆卸單位，其爆炸圖見圖4，零件信息如表1所示，拆卸混合圖見圖5。

圖4　內嚙合齒輪液壓泵爆炸圖

序號零件名稱拆卸工具拆卸方向序號零件名稱拆卸工具拆卸方向1內六角螺釘1內六角扳手1+y11外齒輪拉馬-y2前端蓋螺絲刀+y12內齒圈手-y3密封圈1手+y13滑動軸承螺絲刀+y4油封手+y14密封圈2手+y5滾動軸承拉馬-y15定位銷拔銷器-y6齒輪軸手+y16右殼體螺絲刀-y7擋圈尖嘴鉗+z17密封圈手+y8鍵螺絲刀+z18后端蓋螺絲刀-y9左殼體螺絲刀+y19內六角螺釘1內六角扳手1-y10滑動軸承螺絲刀-y20內六角螺釘2內六角扳手2-y

改進人工蜂群算法的主要參數設置為：ωd=0.4，ωt=0.6；種群數40，最大循環次數500，單個尋優目標最大循環次數100，經多次反復運算得出最優拆卸序列為1→19→18→20→17→16→15→12→11→8→10→13→2→3→14→4→6→9→7→5，最優適應度為10.4。算法收斂特性如圖6所示。在實際拆卸過程中，拆卸工具變化次數為12次，拆卸方向變化次數為8次，經計算T(x)=10.4，與算法計算結果相同，也證明了本算法的可行性。

圖5　內嚙合齒輪液壓泵混合圖

圖6　改進ABC算法的收斂特性曲線

為證明本文算法的優越性，將改進ABC算法與文獻[5]中傳統ABC算法進行比較，以相同參數求解本文實例，得出兩種算法的收斂特性曲線，如圖7所示。可以看出本文算法的收斂速度和最優結果都優于傳統ABC算法。為了避免特定參數的偶然因素，分別以多組參數進行多次實驗并取最優數據，結果如表2所示。

圖7　改進ABC算法與傳統ABC算法求解實例的收斂特性曲線

算法參數改進ABC算法ABC算法種群,循環次數最優適應度首次收斂次數算法耗時(s)最優適應度首次收斂次數算法耗時(s)20,20011.41730.9812.01871.0120,50010.84611.6511.24231.6440,20010.61781.5811.21861.5240,50010.42232.9610.83783.0160,20010.41892.3111.01742.3760,50010.41924.1310.64114.14

從表2中數據可知，改進ABC算法在最優適應度和首次達到該適應度的迭代次數上有較大優勢，在算法總耗時上與傳統ABC算法差距不大。但實際應用中，利用改進ABC算法能夠以較少的種群數量和循環次數進行準確求解，從而縮短了求解時間。

將本文算法與文獻[7-9]算法進行對比，其中ωd=0.5，ωt=0.5，種群數為40，結果如表3所示。

由表3可知，四種算法均能得到近似最優解，但改進ABC算法更為優異。與蟻群算法相比，改進ABC算法有著較低的迭代次數與較短的運行時間；與粒子群算法相比，改進ABC算法在拆卸方向與工具變化次數方面占據優勢；與遺傳算法相比，改進ABC算法在運行時間方面有所減少，其余各方面也略有優勢?？傮w來看，改進ABC算法能夠利用較少的資源,在較短的時間內，求得較優的解。這主要是由于改進ABC算法在種群初始化階段能夠有效提取混合圖信息，同時具有較強的搜索能力，能夠根據求解進度自適應調整求解方案，從而降低運算時間，提高求解質量。綜上所述，本文提出的改進ABC算法與其他算法相比更具優越性。

4　結論

(1)本文建立了拆卸混合圖和拆卸序列規劃數學模型，并對拆卸約束特性進分析，指出了傳統人工蜂群算法在拆卸序列規劃求解方面的問題。

(2)針對隨機生成的初始種群無法有效提取拆卸解空間信息的缺點提出了優先約束算法。與同類算法比較，本文算法能夠有效避免優先約束關系較低的零件出現在拆卸序列前端導致相關零件搜尋不全面的情況，準確提取優先約束關系。

(3)提出了可行度算法與自適應選擇算法，共同指導蜂群活動行為，在保證種群多樣性的前提下實現了算法的快速收斂。

(4)實例驗證表明，本文所述改進人工蜂群算法具有良好的尋優和收斂性能，能夠實現復雜產品拆卸序列規劃的快速求解，有助于提高企業拆卸作業的工作效率。

[1]朱興濤，張則強，朱勛夢，等. 求解多目標拆卸線平衡問題的一種蟻群算法[J]. 中國機械工程, 2014, 25(8): 1075-1079.

ZhuXingtao，ZhangZeqiang，ZhuXunmeng,etal.AnAntColonyOptimizationAlgorithmforMulti-objectiveDisassemblyLineBalancingProblem[J].ChinaMechanicalEngineering, 2014, 25(8):1075-1079.

[2]ZhangH,KuoT.AGraph-basedDisassemblySequencePlanningforEolProductRecycling[J].IEEE/CPMTInternationalElectronicsManufactu-ringTechnologySymposium, 1997(10):140-151.

[3]MooreKE,GüngRAKN,GuptaSM.PetriNetApproachtoDisassemblyProcessPlanningforProductswithComplexand/orPrecedenceRelationships[J].EuropeanJournalofOperationalResear-ch, 2001, 135(2): 428-449.

[4]MeyssamiB.UseofCoagulantsinTreatmentofOliveOilWastewaterModelSolutionsbyInducedAirFlotation[J].BioresourceTechnology, 2005, 96(3): 303-307.

[5]張雷，彭宏偉，卞本陽，等. 復雜產品并行拆解建模及規劃方法研究[J]. 中國機械工程, 2014, 25(7): 937-943.

ZhangLei，PengHongwei，BianBenyang,etal.ParallelDisassemblyModelingandPlanningMethodofComplexProducts[J].ChinaMechanicalEngineer-ing, 2014,25(7):937-943.

[6]邢宇飛，王成恩，柳強. 基于Pareto解集蟻群算法的拆卸序列規劃[J]. 機械工程學報, 2012,48(9): 186-192.

XingYufei，WangCheng’en，LiuQiang.Disassemb-lySequencePlanningBasedonParetoAntColonyAlgorithm[J].JournalofMechanicalEngineering,2012,48(9):186-192.

[7]張秀芬，張樹有. 基于粒子群算法的產品拆卸序列規劃方法[J]. 計算機集成制造系統, 2009,15(3): 508-514.

ZhangXiufen，ZhangShuyou.ProductDisassemblySequencePlanningBasedonParticleSwarmOptimizationAlgorithm[J].ComputerIntegratedManufacturingSystems, 2009,15(3):508-514.

[8]王輝，向東，段廣洪. 基于蟻群算法的產品拆卸序列規劃研究[J]. 計算機集成制造系統, 2006, 12(9): 1431-1437.

WangHui，XiangDong，DuanGuanghong.ProductDisassemblySequencePlanningBasedonAntColonyAlgorithm[J].ComputerIntegratedManufacturingSystems, 2006, 12(9):1431-1437.

[9]吳昊，左洪福. 基于改進遺傳算法的產品拆卸序列規劃[J]. 中國機械工程, 2009,20(6): 699-703.

WuHao，ZuoHongfu.ProductDisassemblySeque-ncePlanningBasedonImprovedGeneticAlgorithm[J].ChinaMechanicalEngineering,2009,20(6):699-703.

[10]秦全德，程適，李麗，等. 人工蜂群算法研究綜述[J]. 智能系統學報, 2014, 9(2) : 127-135.

QinQuande，ChengShi，LiLi,etal.ArtificialBeeColonyAlgorithm:aSurvey[J].CAAITransactionsonIntelligentSystems, 2014, 9(2) : 127-135.

[11]KarabogaD,AkayB.AModifiedArtificialBeeColony(ABC)AlgorithmforConstrainedOptimizationProblems[J].AppliedSoftComputing, 2011, 11(3): 3021-3031.

[12]KondoY,DeguchiK,HayashiY,etal.ReversibilityandDisassemblyTimeofPartConnection[J].Resources,ConservationandRecycling, 2003, 38(3): 175-184.

[13]LiJ,KhooL,TorS.ANovelRepresentationSch-emeforDisassemblySequencePlanning[J].InternationalJournalofAdvancedManufacturingTechnology, 2002, 20(8):621-630.

[14]KarabogaD.AnIdeaBasedOnHoneyBeeSwarmforNumericalOptimization[R].Kayseri:ErciyesUniversity. 2005.

[15]張祥銀，徐春芳，段海斌. 仿生智能計算[M].北京：北京科學出版社, 2011.

[16]KarabogaD,BasturkB.APowerfulandEfficientAlgorithmforNumericalFunctionOptimization:ArtificialBeeColony(ABC)Algorithm[J].JournalofGlobalOptimization, 2007, 39(3): 459-471.

[17]KarabogaD,AkayB.AComparativeStudyofArtificialBeeColonyAlgorithm[J].AppliedMathematicsandComputation, 2009, 214(1):108-132.

[18]黃星梅，卿海鴿. 基于二叉樹的裝配體數據[J]. 湖南大學學報(自然科學版), 2003,30(2):47-50.

HuangXingmei，QingHaige.DataStructureofAssemblyModelBasedonBinaryTree[J].JournalofHunanUniversity(NaturalSciences), 2003,30(2):47-50.

(編輯王旻玥)

Product Disassembly Sequence Planning Based on Improved Artificial Bee Colony Algorithm

Song ShouxuZhang WenshengZhang Lei

Hefei University of Technology, Hefei, 230009

To improve the disassembly sequence planning rate of complex products, an improved artificial bee colony algorithm was proposed, which was used to find the answers in the process of disassembly sequence planning. Based on the disassembly hybrid graph model, the connection relationships and disassembly priority relationships were expressed, and the constraint expression of disassembly sequence was obtained. The mathematical model and fitness equation of the disassembly sequence planning were constructed. The initial population was given the priority of constraint algorithm. A feasible algorithm for searching and selecting source nectar was put forward. In order to quickly get the disassembly sequence planning of complex products, an adaptive selection parameter was defined to balance the feasibility and fitness algorithm.Finally, compared with a typical artificial bee colony algorithm, an internal gear pump was studied as an instance to demonstrate the feasibly and efficiency of the method presented.

complex product; disassembly sequence planning; artificial bee colony algorithm; constrained optimization

2015-10-26

國家自然科學基金資助項目(51575152)

TH122

10.3969/j.issn.1004-132X.2016.17.019

宋守許, 男, 1964 年生。合肥工業大學機械與汽車工程學院教授、博士。主要研究方向為綠色設計與綠色制造、廢舊產品再資源化理論及技術。發表論文50余篇。張文勝,男,1992年生。合肥工業大學機械與汽車工程學院碩士研究生。張雷,男,1978年生。合肥工業大學機械與汽車工程學院教授、博士。