基于蟑螂算法的產(chǎn)品拆卸序列規(guī)劃

施英瑩， 劉志峰， 張洪潮，2， 胡 迪

（1.合肥工業(yè)大學(xué) 機(jī)械與汽車工程學(xué)院，安徽 合肥 230009；2.德克薩斯理工大學(xué) 工業(yè)工程系，拉伯克 79409）

對(duì)廢棄產(chǎn)品進(jìn)行回收和重利用能大大減輕環(huán)境污染，拆卸是產(chǎn)品回收的重要環(huán)節(jié)，如何拆卸已經(jīng)成為全球性的重要研究課題［1］。拆卸序列規(guī)劃就是通過對(duì)產(chǎn)品裝配信息進(jìn)行分析、提取，生成幾何可行的拆卸序列，同時(shí)根據(jù)一定的評(píng)價(jià)標(biāo)準(zhǔn)，尋找最優(yōu)的拆卸序列。近年來，國內(nèi)外很多學(xué)者對(duì)其進(jìn)行了深入研究。早期的研究主要傾向于圖論研究，包括 AND／OR 圖法［2］、Petri網(wǎng)法［3］、割集圖法［4］等。這些方法在一定程度上解決了拆卸中的序列生成問題，但是當(dāng)零件數(shù)目較大時(shí)，會(huì)出現(xiàn)組合爆炸現(xiàn)象。近來，隨著進(jìn)化算法的發(fā)展，基于人工智能算法求解最優(yōu)拆卸序列的研究受到了重視。文獻(xiàn)［5］基于組件數(shù)量、拆卸工具以及拆卸方向的考慮建立了拆卸優(yōu)化模型，然后運(yùn)用蟻群算法得到了有效的產(chǎn)品拆卸序列。文獻(xiàn)［6］構(gòu)建了產(chǎn)品拆卸可行性信息圖，并引入了遺傳算法進(jìn)行最優(yōu)拆卸序列的搜尋。文獻(xiàn)［7］將賦權(quán)混合圖模型映射到粒子群模型，應(yīng)用粒子群算法實(shí)現(xiàn)了復(fù)雜產(chǎn)品的拆卸序列優(yōu)劃。然而，這些算法都易陷入局部最優(yōu)，在進(jìn)化后期收斂速度較慢，優(yōu)化精度較差。

蟑螂算法（Cockroach Swarm Optimization，簡(jiǎn)稱CSO）是通過模擬蟑螂（Cockroach，簡(jiǎn)稱C）的覓食行為和簡(jiǎn)化社會(huì)模型而提出的一種新型智能算法，CSO算法公式簡(jiǎn)單，充分利用了C社會(huì)的平等特性和群體智慧，通過群體協(xié)作達(dá)到尋優(yōu)目的，再分配和大變異策略使算法具有較強(qiáng)的全局搜索及跳出局部最優(yōu)的能力［8－9］。本文將CSO算法用于產(chǎn)品拆卸序列規(guī)劃，通過建立產(chǎn)品拆卸混合圖來產(chǎn)生可行的初始拆卸序列，建立拆卸成本最小的目標(biāo)函數(shù)，并結(jié)合CSO算法進(jìn)行拆卸序列規(guī)劃，以得到最優(yōu)或近似最優(yōu)的拆卸序列。

1 基于混合圖的拆卸模型的建立

1.1 拆卸模型描述

產(chǎn)品一般由零件或部件組成，在建立混合圖時(shí)，需要把部件當(dāng)作零件來看，定義混合圖的頂點(diǎn)為產(chǎn)品的零件或部件。

首先對(duì)產(chǎn)品拆卸建模作如下假設(shè)［10－11］：

（1）產(chǎn)品零件或部件分為功能件和連接件，連接件指用來連接和固定功能件的零件或部件?；旌蠄D中的零件或部件均指功能件。

（2）產(chǎn)品拆卸需求信息（包括拆卸零件信息，主要考慮零件或部件間的連接關(guān)系；拆卸工藝信息，主要考慮拆卸過程所需的工具；拆卸約束信息，主要考慮零件或部件的拆卸方向）都作為已知條件，轉(zhuǎn)換成0－1矩陣。

在獲取產(chǎn)品拆卸信息的基礎(chǔ)上，建立混合圖來描述產(chǎn)品零件或部件間的關(guān)系?；旌蠄D由表示零件或部件的頂點(diǎn)、零件或部件間連接關(guān)系的實(shí)線無向邊以及零件或部件間優(yōu)先關(guān)系的虛線有向邊構(gòu)成，拆卸就是把這些零件或部件從產(chǎn)品中分離出來的過程。圖1所示為其混合圖。

圖1 拆卸混合圖

表示為：

其中，G表示混合圖；V為頂點(diǎn)，表示零件或部件；UE為實(shí)線無向邊，表示零件或部件間的接觸約束關(guān)系（如圖1中頂點(diǎn)1到2為無向邊，表示零件1和2間有連接關(guān)系）；DE為虛線有向邊，表示零件或部件間的優(yōu)先關(guān)系（如圖1中頂點(diǎn)5到2為有向邊，表示零件5應(yīng)在2之前拆卸）。

混合圖中的無向邊和有向邊可以表示成連接矩陣和優(yōu)先矩陣，G＝｛V，UE，DE｝可以分解為GB＝｛V，UE｝和GC＝｛V，DE｝。假設(shè)混合圖含有N個(gè)頂點(diǎn)，則G可以分解為2個(gè)N維矩陣，即

其中，當(dāng)零件i與零件j有接觸連接時(shí)，bi，j＝1；當(dāng)零件i與零件j沒有連接關(guān)系時(shí)，bi，j＝0；當(dāng)i＝j(luò)時(shí)，bi，j＝0。

其中，當(dāng)零件j須在零件i前拆卸時(shí)，ci，j＝1；當(dāng)零件i與零件j間無優(yōu)先關(guān)系時(shí)，ci，j＝0；當(dāng)i＝j(luò)時(shí)，ci，j＝0。

圖1所示的拆卸混合圖表示為2個(gè)矩陣，即

1.2 可拆卸零件推導(dǎo)及初始拆卸序列生成

可拆卸零件是指可以從產(chǎn)品中分離出來的零件，根據(jù)混合圖模型的2個(gè)矩陣可以判斷零件是否可拆卸。當(dāng)零件i同時(shí)滿足以下2個(gè)條件：① 零件i只有一個(gè)接觸連接；② 零件i沒有受到其他零件的優(yōu)先約束時(shí)，零件i可拆卸；否則，零件i不可拆卸。當(dāng)零件i被拆卸后，在混合圖中，零件i與其他零件間的約束關(guān)系都被解除，即頂點(diǎn)i變成了一個(gè)孤立點(diǎn)。拆卸結(jié)束時(shí)，混合圖將由一些孤立點(diǎn)組成。

初始拆卸序列的質(zhì)量對(duì)搜索效率有很大的影響。為了在人為給定和隨機(jī)生成之間取得平衡，保證搜索效率，根據(jù)零件的可拆卸性推導(dǎo)，按照串行方式逐步生成初始拆卸序列。首先定義列表allowed存放可拆卸零件，定義列表sequence存放當(dāng)前獲得的拆卸序列。例如，拆卸對(duì)象為圖1產(chǎn)品，根據(jù)條件① 和② 可判斷allowed＝｛1，5｝，隨機(jī)選取零件5放入sequence中，使sequence＝｛5｝，更新混合圖使頂點(diǎn)5變成孤立點(diǎn)；然后用同樣的方法判斷allowed＝｛1，4｝，隨機(jī)選取零件1放入sequence中，使sequence＝｛5，1｝，更新混合圖將頂點(diǎn)1變成孤立點(diǎn)；以此類推，最后1、2、3、4、5都變成孤立點(diǎn)，生成一條可行拆卸序列sequence＝｛5，1，4，3，2｝。初始拆卸序列生成的具體流程如圖2所示。

圖2 初始拆卸序列的生成

1.3 拆卸序列優(yōu)化

拆卸序列規(guī)劃的目的是得到拆卸成本較低的拆卸序列。對(duì)完全拆卸而言，拆卸過程中拆卸方向的改變次數(shù)和拆卸工具的更換次數(shù)是影響拆卸成本的2個(gè)最大因素。優(yōu)化算法的目的就是盡可能減少拆卸方向和拆卸工具的變化，以降低成本，提高拆卸效率［12］。根據(jù)分析，對(duì)這2個(gè)評(píng)價(jià)指標(biāo)進(jìn)行加權(quán)，確定拆卸序列優(yōu)化的目標(biāo)函數(shù)為：

其中，s為可行的拆卸序列；a為拆卸方向改變權(quán)值；b為拆卸工具更換權(quán)值。

2 拆卸序列優(yōu)化模型的求解

2.1 算法原理及模型映射

CSO算法是從自然界中C覓食過程得到啟發(fā)，通過改進(jìn)而得到的一種算法，通過C群體的集體協(xié)作達(dá)到尋優(yōu)目的。拆卸序列規(guī)劃屬于離散組合優(yōu)化問題，用CSO求解該問題時(shí)，需要通過下面的關(guān)系映射，將拆卸序列規(guī)劃的圖模型與CSO模型對(duì)應(yīng)起來。

在產(chǎn)品混合圖模型G的基礎(chǔ)上，每個(gè)C的位置坐標(biāo)Ci＝｛c1，c2，…cn｝代表一條拆卸序列，n為零件個(gè)數(shù)，ci代表零件i。例如，C1｛5，3，2，4，1，6｝就代表拆卸序列5→3→2→4→1→6。C的位置坐標(biāo)對(duì)應(yīng)的適應(yīng)度值確定了對(duì)應(yīng)拆卸序列的優(yōu)劣程度，對(duì)拆卸成本函數(shù)，適應(yīng)度值越小，對(duì)應(yīng)的拆卸序列越優(yōu)秀。每個(gè)C根據(jù)自身、自身的局部最優(yōu)位置和整個(gè)群體的全局最優(yōu)位置不斷爬行，尋找滿足條件的最優(yōu)解［13－15］。

（1）交換路徑。C爬行一步用Step（i，j）表示，代表拆卸序列中零件i和零件j交換。C爬行一段距離表示拆卸序列經(jīng)過若干次交換，表示Road＝Step1＋Step2＋…＋Stepm。

例如，當(dāng)前拆卸序列為（2，4，3，6，5，1），目標(biāo)拆卸序列為（3，6，1，4，2，5），交換路徑為：Road＝Step（1，3）＋Step（2，4）＋Step（3，6）＋Step（5，6），如圖3所示。

圖3 交換路徑

（2）再分配策略。設(shè)m為C群體規(guī)模，即初始拆卸序列總數(shù)；Fg為全局最優(yōu)解，即所有拆卸序列中適應(yīng)度值最小的拆卸序列；Fpi（i＝1，2，…，m）為局部最優(yōu)解，即每個(gè)初始拆卸序列對(duì)應(yīng)的、除Fg外適應(yīng)度值最小的拆卸序列。隨著算法的不斷迭代，可能會(huì)出現(xiàn)Fg＝Fp1＝Fp2＝…＝Fpm，使算法陷入局部最優(yōu)，此時(shí)要采取再分配策略，對(duì)Fpi進(jìn)行重新分配：

（3）回巢策略。每次向Fg或Fpi爬行前，C群體重新回到初始位置，即所有的初始拆卸序列不變化。回巢策略使算法具有全局搜索能力，從而避免早熟。

（4）大變異策略。把所有C向Fg和Fpi（i＝1，2，…，m）爬行完成作為一次總迭代，即把所有初始拆卸序列向Fg和Fpi（i＝1，2，…，m）交換完成的過程作為一次總迭代，用FgRemb記錄當(dāng)前全局最優(yōu)拆卸序列。如果T次迭代FgRemb不更新，則執(zhí)行大變異策略：

其中，x∈［1，n／5］，n為零件個(gè)數(shù)。

大變異策略使CSO算法跳出局部最優(yōu)，使Fg在一個(gè)新的位置引領(lǐng)所有C在空間內(nèi)搜索最優(yōu)解。

2.2 基于CSO算法的拆卸序列規(guī)劃

最優(yōu)化拆卸序列求取流程如圖4所示。

圖4 拆卸序列優(yōu)化流程圖

利用CSO優(yōu)化算法進(jìn)行產(chǎn)品序列規(guī)劃的實(shí)質(zhì)是將基于圖搜索和智能算法相結(jié)合。

（1）建立產(chǎn)品混合圖模型，根據(jù)連接矩陣和優(yōu)先矩陣得到可行的初始拆卸序列群，初始化個(gè)體的局部最優(yōu)拆卸序列Fpi（初始化時(shí)，可設(shè)Ci＝Fpi對(duì)算法無影響）。

（2）對(duì)一個(gè)局部最優(yōu)目標(biāo)拆卸序列Fpi，所有初始拆卸序列同時(shí)向其爬行，交換過程中，若沿途搜索到適應(yīng)度值小于Fpi序列的更優(yōu)解，則更新該Fpi；初始拆卸序列對(duì)所有Fpi爬行完成后，在Fpi中選出適應(yīng)度值最小的作為當(dāng)前全局最優(yōu)目標(biāo)拆卸序列Fg。

（3）所有初始拆卸序列向Fg爬行，沿途搜索到適應(yīng)度值更小的拆卸序列則更新對(duì)應(yīng)Fpi；所有初始拆卸序列向Fg爬行完成后，在Fpi中選出適應(yīng)度值最小的序列更新Fg，記錄FgRemb＝Fg；步驟（2）、（3）表示一次完整的交換過程。

（4）判斷拆卸序列Fg＝Fp1＝Fp2＝…＝Fpm是否成立，若成立則執(zhí)行再分配策略，重新得到局部最優(yōu)目標(biāo)拆卸序列Fpi，轉(zhuǎn)入步驟（2）；若不成立則直接轉(zhuǎn)入步驟（2），直至T次迭代結(jié)束。

（5）判斷T次迭代過程中FgRemb是否更新，若更新則直接轉(zhuǎn)入步驟（2）進(jìn)行下一輪循環(huán)；若不更新則執(zhí)行大變異策略，轉(zhuǎn)入步驟（3）。

（6）判斷循環(huán)次數(shù)是否達(dá)到N，若達(dá)到則退出算法，輸出最優(yōu)拆卸序列；若沒達(dá)到則轉(zhuǎn)入步驟（2）繼續(xù)循環(huán)。

3 實(shí)例研究

基于求解算法，使用VC＋＋6.0編寫了相應(yīng)的CSO優(yōu)化算法程序。本文以某款柜式洗碗機(jī)為例，模型的爆炸圖如圖5所示。該洗碗機(jī)模型中共包含14個(gè)功能件，各功能件的信息見表1所列。

圖5 洗碗機(jī)模型爆炸圖

表1 洗碗機(jī)零部件信息表

在洗碗機(jī)的拆卸過程中，由于洗碗機(jī)體積較大，拆卸方向的改變對(duì)整個(gè)拆卸影響也較大。其拆卸混合圖如圖6所示。

圖6 洗碗機(jī)模型混合圖

同時(shí)，拆卸過程中對(duì)不同的拆卸對(duì)象，有不同的拆卸工具，拆卸工具更換的影響相對(duì)較小。因此，目標(biāo)函數(shù)F中權(quán)值分別為：a＝0.6，b＝0.4，算法中迭代次數(shù)T＝5，經(jīng)過反復(fù)多次試驗(yàn)，CSO算法中參數(shù)變化對(duì)結(jié)果的影響見表2所列。從表2可以看出，CSO算法的最優(yōu)解受初始種群的影響較大，而在初始種群相同的情況下，循環(huán)次數(shù)越多，獲得最優(yōu)解的可能也越大。在種群規(guī)模均為60，循環(huán)次數(shù)均為80的情況下，CSO算法和PSO算法的結(jié)果對(duì)比見表3所列，由表3可以看出，CSO算法得到的結(jié)果較優(yōu)于PSO算法。

表2 各次主要試驗(yàn)結(jié)果

表3 CSO算法和PSO算法結(jié)果對(duì)比

4 結(jié)束語

產(chǎn)品拆卸規(guī)劃包括拆卸序列產(chǎn)生和拆卸序列優(yōu)化2部分，在現(xiàn)有拆卸序列規(guī)劃研究的基礎(chǔ)上，用混合圖來描述產(chǎn)品的拆卸模型，通過混合圖推導(dǎo)生成可行拆卸序列，提出拆卸序列優(yōu)化目標(biāo)函數(shù)，結(jié)合CSO算法對(duì)拆卸序列進(jìn)行優(yōu)化得到最優(yōu)或近似最優(yōu)解。通過實(shí)例分析，表明了本文提出的拆卸序列規(guī)劃模型能夠處理拆卸序列規(guī)劃問題。但是CSO優(yōu)化算法仍然存在一些不足，作為一個(gè)新的優(yōu)化算法，CSO仍需改進(jìn)，使其更適用于拆卸序列規(guī)劃。

［1］Kim H J，Leed H，Xirouchakis P，et al.Disassembly scheduling with multiple product types［J］.Annals of the CIRP，2003，52（1）：403－406.

［2］Zussman E，Zhou M C.A methodology for modeling and adaptive planning of disassembly process［J］.IEEE Transactions on Robotics and Automation，1990， 15（1）：190－194.

［3］Kuo T C.Disassembly sequence and cost analysis for electromechanical products［J］.Robotics and Computer Integrated Manufacturing，2000，16（1）：43－54.

［4］Guo Weixiang，Liu Zhifeng.Disassembly sequence planning based on modularization ［J］.Journal of Computer－Aided Design ＆ Computer Graphics， 2005，17（3）：498－504.

［5］Shan Hongbo，Li Shuxia，Huang Jing，et al.Colony optimization algorithm－based disassembly sequence planning［C］／／ICMA International Conference on Mechatronics and Automation，Harbin，China，2007：867－872.

［6］Wang Hui，Xiang Dong，Duan Guanghong.A genetic algo－rithm for product disassembly sequence planning［C］／／IEEE International Conference on Engineering of Intelligent Systems，Islamabad，Pakistan，2006：1－5.

［7］張秀芬，張樹有.基于粒子群算法的產(chǎn)品拆卸序列規(guī)劃方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2009，15（3）：508－514.

［8］Jeanson R，Rivault C，Deneubourg J，et al.Self－organized aggregation in cockroaches［J］.Animal Behavior，2005，69：169－180.

［9］Easom E E.A survey of global optimization techniques［D］.Louisville K Y：University of Lousisvile，1990.

［10］王 輝，向 東，段廣洪.基于蟻群算法的產(chǎn)品拆卸序列規(guī)劃研 究 ［J］.計(jì) 算 機(jī) 集 成 制 造 系 統(tǒng)，2006，12（9）：1431－1437.

［11］劉志峰，張少亭，宋守許，等.報(bào)廢汽車拆卸回收的經(jīng)濟(jì)性分析［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，32（3）：347－350.

［12］Lambert A J D.Optimum disassembly sequence with sequence－dependent disassembly costs［C］／／Proceedings of the IEEE International Symposium on Assembly and Task Planning，Portugal，2003：151－156.

［13］程 樂.引入大變異策略的蟑螂算法研究［J］.微電子學(xué)與計(jì)算機(jī)，2009，26（5）：13－16.

［14］Chen Zhaohui，Tang Haiyan.Cockroach swarm optimization［C］／／Proceedings of 2010 2nd International Conference on Computer Engineering and Technology，Portugal，2010：652－655.

［15］Havens T C，Spain C J，Salmon N G，et al.Roach infestation optimization［J］.Swarm Intelligence Symposium，Portugal，2008：1－7.