多目標拆卸線平衡問題的Pareto人工魚群算法

汪開普 張則強 毛麗麗 李六柯

西南交通大學機械工程學院，成都，610031

多目標拆卸線平衡問題的Pareto人工魚群算法

汪開普 張則強 毛麗麗 李六柯

西南交通大學機械工程學院，成都，610031

針對拆卸線平衡問題的復雜性，提出了一種改進的基于Pareto解集的多目標人工魚群算法進行求解。為提高人工魚覓食時的尋優(yōu)能力，引入遺傳算法的隨機交叉操作，指導人工魚向全局最優(yōu)拆卸方向覓食。通過擁擠距離不斷篩選人工魚覓食、聚群和追尾過程中的非劣解，實現(xiàn)了各行為結果的多樣性。采用精英保留策略，將外部檔案中的非劣解添加到算法下次迭代的種群中，加快了算法的收斂。通過對不同規(guī)模的拆卸實例進行求解，并將其與已有算法進行對比，驗證了所提算法的有效性和優(yōu)越性。

拆卸線平衡問題；多目標優(yōu)化；Pareto解集；人工魚群算法

0 引言

隨著經(jīng)濟的高速增長、物質(zhì)財富的極大豐富化，資源與環(huán)境問題日趨嚴峻。實現(xiàn)廢舊機電產(chǎn)品的拆卸處理能夠提高資源利用率，減少環(huán)境污染，因此廢舊產(chǎn)品的拆卸回收再利用日益得到重視。拆卸線具有生產(chǎn)效率高、成本低等優(yōu)點，是規(guī)?；鹦懂a(chǎn)品的最有效途徑之一。然而實際拆卸線各工作站間普遍存在著作業(yè)不均衡現(xiàn)象，影響著生產(chǎn)效率的提升。

針對拆卸線所面臨的問題，國內(nèi)外開展了廣泛探索和研究。GUNGOR等[1]首先提出拆卸線平衡問題 (disassembly line balancing problem，DLBP)。啟發(fā)式方法[2]和數(shù)學規(guī)劃法[3]在求解小規(guī)模DLBP上能夠得到最優(yōu)解，但難以求解大規(guī)模問題。由于DLBP是NP完全問題[4]，隨著任務規(guī)模數(shù)的增大，難以在有效時間內(nèi)求得最優(yōu)解。McGOVERN等[5]提出了一種蟻群算法來求解以平衡率和工作站數(shù)為優(yōu)化目標的DLBP，并與現(xiàn)有的幾種啟發(fā)式算法的求解性能進行對比，結果表明群智能算法較啟發(fā)式算法更具優(yōu)越性[6]。KALAYCI等用遺傳算法[7]、模擬退火算法[8]、粒子群算法[9]、人工蜂群算法[10]、變鄰域搜索算法[11]、禁忌搜索算法[12]求解不同規(guī)模任務的DLBP，都能夠快速得到較優(yōu)解。

上述文獻采用群智能算法求解多目標DLBP時均是將其轉(zhuǎn)化為單目標問題進行求解，只能求得一個解，但DLBP各優(yōu)化目標間存在著相互博弈的關系，導致求得的平衡方案無法實現(xiàn)各優(yōu)化目標間的均衡，并且使求解結果喪失了多樣性。朱興濤等[13]提出一種改進蟻群算法求解多目標DLBP，按順序處理各目標，其本質(zhì)還是將多目標問題轉(zhuǎn)化為單目標問題求解。丁力平等[14]利用基于Pareto解集的蟻群算法對多目標DLBP進行優(yōu)化，能夠得到多種優(yōu)化方案，實現(xiàn)了各目標間的均衡，但各平衡方案的性能指標還有進一步提升的空間。

人工魚群算法(artificial fish swarm algorithm，AFSA)具有收斂速度高、全局搜索能力強、魯棒性強等優(yōu)點[15]，在求解組合優(yōu)化問題[16-17]時表現(xiàn)出優(yōu)良的求解性能。參考已有文獻，尚未發(fā)現(xiàn)有將人工魚群算法用于求解DLBP的公開報道。

鑒于現(xiàn)有研究的不足，本文結合Pareto解集求解多目標問題思想以及人工魚群算法求解組合優(yōu)化問題的優(yōu)勢，提出一種求解DLBP的Pareto人工魚群算法。通過對不同規(guī)模任務的問題進行測試對比，驗證了所提算法求解多目標DLBP的求解性能。

1 多目標拆卸線平衡問題

1.1 問題描述

拆卸線是實現(xiàn)大規(guī)模拆卸作業(yè)的最佳選擇，面對日益增多的待拆卸廢舊機電產(chǎn)品，拆卸線越來越多地被采用，圖1為一個拆卸線示意圖。在廢舊產(chǎn)品完全拆卸的情況下，需綜合考慮拆卸線工作任務分配、拆卸線開啟工作站數(shù)、拆卸線節(jié)拍時間安排、拆卸危害度等多種因素。針對多目標拆卸線平衡問題，尋求滿足拆卸任務間優(yōu)先關系的可行拆卸序列，且該序列需滿足多個拆卸目標的優(yōu)化，包括最小化工作站數(shù)目、平衡各個工作站間的負荷、盡早拆卸有危害以及需求高的零件。

圖1 拆卸線示意圖Fig.1 Diagram of dissembly line

1.2 數(shù)學模型

針對拆卸線平衡問題的特點，建立如下多目標模型[4]：

min f1=M

(1)

(2)

(3)

(4)

(5)

Tm≤TC?m∈{1,2,…,M}

(6)

(7)

(8)

目標函數(shù)中，式(1)表示最小化拆卸線開啟的工作站數(shù)。當拆卸線節(jié)拍固定時，開啟的工作站越多，所需的作業(yè)工人和拆卸設備也越多，將導致拆卸成本增大。式(2)表示均衡每個工作站的空閑時間。每個拆卸工作站的空閑時間與拆卸線的效率正相關，工作站間工位時間的均衡有利于提高拆卸線的作業(yè)效率。式(3)表示盡可能早地拆卸需求高的零部件。需求指標越高的零件，帶來的經(jīng)濟效益越大，故在同等條件下優(yōu)先考慮拆卸。式(4)表示盡可能早地拆卸有危害的零部件?？紤]到產(chǎn)品拆卸任務的特殊性，一些攜帶有毒或有害化學物質(zhì)的零部件需盡早作業(yè)。

2 Pareto人工魚群算法

人工魚群算法在求解組合優(yōu)化問題中表現(xiàn)出良好的性能，該算法具有較強的搜索能力，已在旅行商問題[15]、冗余分配問題[16]、多維0-1背包問題[17]等諸多組合優(yōu)化問題中得到了成功應用。本文針對拆卸線平衡問題的特點，借鑒文獻[18]中的多目標處理方式，結合人工魚群算法的優(yōu)勢，提出一種求解多目標拆卸線平衡問題的Pareto人工魚群算法。

2.1 可行解的構造

根據(jù)拆卸任務間的優(yōu)先關系圖構造優(yōu)先關系矩陣Y，為保證初始解的多樣性，每次挑選任務均為隨機挑選。此過程無需考慮工作站節(jié)拍的影響，解碼時才需考慮節(jié)拍對目標函數(shù)的影響。生成初始可行解的具體步驟如下：

Step1 從拆卸優(yōu)先關系矩陣Y中隨機挑選未分配的任務i，且任務i無緊前任務或緊前任務已分配(即Y中每列全部為零的任務)，將其作為當前位置n處的拆卸任務；

Step2 將與任務i有優(yōu)先關系的約束從Y中刪除：?a∈{1,2,…,N}，令yia=0，yai=0；

Step3 尋找下一位置處的任務，令n←n+1；

Step4 重復Step1～Step3，直至所有任務分配完成，得到的序列即為初始可行拆卸序列。

2.2 Pareto解集的更新

現(xiàn)有求解多目標拆卸線平衡問題的文獻一般采用線性加權法和順序處理法[4-13]，其本質(zhì)是將多目標問題轉(zhuǎn)化為單目標問題進行求解，不能很好地平衡存在沖突關系的多個目標函數(shù)。Pareto解集思想能很好地兼顧多個優(yōu)化目標間的均衡，求解結果更符合問題實際情況，可以作為該問題的求解思想。

滿足拆卸優(yōu)先關系的拆卸序列稱為多目標拆卸線的可行解，所有可行解組成的集合稱為可行解集。給定兩個可行拆卸序列X1、X2，若X1、X2滿足

(9)

式中，D為目標函數(shù)個數(shù)；fd為第d個目標函數(shù)值。

則稱X1Pareto占優(yōu)于X2，或X1支配X2，記為X1X2。

若可行解X*滿足：不存在拆卸序列X使得XX*，則稱序列X*為Pareto最優(yōu)解或非劣解。所有Pareto最優(yōu)解的集合構成Pareto最優(yōu)解集，對應拆卸序列的多目標函數(shù)值組成的集合稱為Pareto最優(yōu)前沿。

利用外部檔案Q記錄已找到的Pareto最優(yōu)拆卸序列的目標函數(shù)值，算法每迭代一次就將種群P中的每一個新解pi與外部檔案Q中每一個非劣解qj進行比較：若piqj，則將pi置于Q中，同時將qj從Q中刪除；若qjpi，則Q保持不變；若pi和qj互不支配，則將pi、qj都置于Q中，實現(xiàn)外部檔案Q的更新，得到最優(yōu)非劣解。

2.3 個體評價

在算法的每一次迭代過程中，將更新后的外部檔案中的Pareto最優(yōu)解作為下一次迭代的種群。為避免外部檔案Q的容量過大對種群產(chǎn)生不利影響，需要對外部檔案中的非劣解進行評價篩選。引入NSGA-Ⅱ擁擠距離機制[18]評價每個非劣解，將每個目標函數(shù)fd按升序排列，其中d∈{1,2,…,D}，定義目標函數(shù)fd的兩個邊界個體的擁擠距離L1=Lk→∞，其他非劣解個體的擁擠距離為

(10)

g∈{2,3,…,k-1}

式中，k為非劣解的個數(shù)；fd,k、fd,1分別為第d個目標函數(shù)值的最大值和最小值。

2.4 覓食行為

覓食行為中人工魚是通過視覺或嗅覺感知水中食物濃度來選擇趨向的，設人工魚當前狀態(tài)為Xcurrent，人工魚感知視野范圍為V，在V內(nèi)經(jīng)過ntry次嘗試后若找到食物濃度較高的位置，則向該位置移動一步。離散問題中，不設置人工魚的步長，人工魚直接從食物濃度低的位置跳到濃度較高的位置?；救斯~群算法中當前狀態(tài)人工魚Xcurrent執(zhí)行隨機搜索，搜索方向是不確定的，無法指導人工魚向最優(yōu)方向收斂，鑒于此引入遺傳算法的交叉算子，指導人工魚覓食，對Xcurrent進行隨機順序交叉操作，如圖2所示。

圖2 交叉操作示意圖Fig.2 Diagram of cross operation

在Xcurrent中隨機選取2個交叉點，則交叉點1之前的序列和交叉點2之后的序列必然滿足拆卸優(yōu)先關系，保持不變；交叉點1和交叉點2之間的序列通過隨機生成的參考人工魚Xreference映射得到，組成新的人工魚Xnew。交叉部分在Xreference中滿足拆卸優(yōu)先關系，則生成的Xnew也必然滿足拆卸優(yōu)先關系。通過隨機選擇Xcurrent中交叉點并與隨機生成的參考人工魚Xreference交叉映射得到新的人工魚Xnew，增強了覓食魚群跳出局部最優(yōu)的能力。

將Xcurrent置于覓食行為外部檔案Qprey中，作為非劣解。人工魚每執(zhí)行一次交叉操作，即完成一次覓食嘗試。將每一次交叉后的解與Qprey中的每一個非劣解進行比較，不斷篩選非劣解，實現(xiàn)Qprey的更新，直至完成ntry次嘗試，Qprey中非劣解為Xcurrent覓食后得到的可移動狀態(tài)。若執(zhí)行ntry次嘗試后，Qprey中非劣解保持Xcurrent不變，則表明覓食失敗，執(zhí)行隨機行為，即隨機選擇一種可行解。覓食行為過程如圖3所示。

圖3 覓食行為過程Fig.3 Flow of prey

2.5 聚群行為

聚群行為是Xcurrent探索視野范圍V內(nèi)伙伴數(shù)目Ns及中心位置Xcenter是否滿足移動條件。設有兩條人工魚X1=(a1，a2，…，an)和X2=(b1，b2，…，bn)，在常見的連續(xù)性問題中，兩條人工魚的距離采用歐幾里得法表示為

(11)

離散問題并不適用于該方法。離散問題中兩條人工魚之間的距離可表示為

(12)

(13)

式中，argmaxfreq(A)表示集合A中出現(xiàn)次數(shù)最多的元素。

Xcenter由視野范圍內(nèi)伙伴矩陣中每列出現(xiàn)次數(shù)最多的元素組成，且Xcenter的序列必須滿足拆卸任務優(yōu)先關系。

若Xcurrent在視野范圍V內(nèi)看不到伙伴或Ns/ Nfish>δ，其中，Nfish為種群數(shù)目，δ為擁擠度，則表明聚群失敗，執(zhí)行覓食行為。當Ns/Nfish≤δ時，則需將Xcenter與Xcurrent進行比較：若XcenterXcurrent，則用Xcenter替換Xcurrent，表明聚群成功；若XcurrentXcenter，表明聚群失敗，則執(zhí)行覓食行為；若Xcenter、Xcurrent互不支配，則將Xcenter、Xcurrent都保留下來，聚群成功。聚群行為過程如圖4所示。

圖4 聚群行為過程Fig.4 Flow of swarm

2.6 追尾行為

追尾行為是Xcurrent探索視野范圍V內(nèi)伙伴數(shù)目Nf及每個伙伴的食物濃度是否滿足移動條件。Nf=0表示Xcurrent探索視野范圍V內(nèi)無伙伴，表明追尾失敗，執(zhí)行覓食行為。將Xcurrent置于追尾行為外部檔案Qfollow中，將其與Qfollow中其他非劣解進行比較，實現(xiàn)Qfollow中非劣解的篩選與更新。若Qfollow中只有Xcurrent，則表明追尾失敗，執(zhí)行覓食行為；若Qfollow中除Xcurrent外還有Nq個非劣解且Nq/Nfish≤ δ，則追尾成功，否則執(zhí)行覓食行為。追尾行為過程如圖5所示。

圖5 追尾行為過程Fig.5 Flow of follow

2.7 更新種群

基本人工魚群算法中的種群是隨機生成的，且在迭代過程中保持不變，算法結果的優(yōu)劣依賴于初始解。為獲得較好最終解，可對種群進行更新。

針對多目標問題，采用Pareto占優(yōu)篩選外部檔案中的非劣解，可以考慮將外部檔案Q中的非劣解作為下次迭代的種群。該操作保留了每次迭代的較優(yōu)解，并在此基礎上尋找更優(yōu)的解，有利于算法快速收斂。為保證種群數(shù)目不變，需要對外部檔案中的非劣解進行篩選。

設定種群數(shù)目Nfish，當外部檔案中非劣解數(shù)目NQNfish時，按照個體擁擠距離評價指標從大到小選取Nfish個非劣解作為算法下次迭代的種群。

2.8 算法步驟

Step1 設定算法參數(shù)，包括種群規(guī)模Nfish、覓食行為最大嘗試次數(shù)ntry、擁擠度δ、視野V、最大迭代次數(shù)gmax、節(jié)拍TC等；

Step2 根據(jù)優(yōu)先關系矩陣Y生成初始種群，設外部檔案Q=?；

Step3 計算目標函數(shù)值f1、f2、f3、f4，按照2.2節(jié)內(nèi)容篩選種群非劣解，更新外部檔案；

Step4 開始迭代，分別按照2.5節(jié)、2.6節(jié)內(nèi)容執(zhí)行聚群行為和追尾行為；

Step5 將Step4的結果與種群非劣解進行比較篩選，更新種群外部檔案；

Step6 將Step5外部檔案中的非劣解作為種群，按照2.7節(jié)內(nèi)容更新種群；

Step7 判斷是否達到最大迭代次數(shù)gmax，若達到，則轉(zhuǎn)下一步；否則轉(zhuǎn)Step4；

Step8 輸出外部檔案中的非劣解，得到最優(yōu)拆卸序列。

多目標Pareto人工魚群算法流程如圖6所示。

圖6 Pareto人工魚群算法流程圖Fig.6 Flow of Pareto AFSA

3 算法驗證與實例應用

為驗證所提算法的有效性，針對不同規(guī)模的拆卸線平衡問題，應用所提算法進行測試。算法實驗采用的計算機硬件配置為Intel Core i3-2100 M，3.10 GHz，2 GB內(nèi)存，在Windows7系統(tǒng)下使用MATLAB R2010b軟件開發(fā)了算法的實驗程序。

3.1 算法驗證

文獻[7-11]分別采用遺傳算法(genetic algorithm，GA)、模擬退火 (simulated annealing，SA) 算法、粒子群優(yōu)化 (particle swarm optimization，PSO) 算法、人工蜂群 (artificial bee colony，ABC) 算法、變鄰域搜索 (variable neighborhood search，VNS) 算法求解了包含25項任務的SCH-3500移動電話拆卸案例，該案例的零件拆卸優(yōu)先關系、拆卸時間參數(shù)、危害參數(shù)、需求參數(shù)等詳見文獻[9]，現(xiàn)將5種單目標算法求解到的最優(yōu)方案結果列于表1。

表1 文獻[7-11]求解P25的解Tab.1 Solution of P25 in reference [7-11]

測試時兼顧求解質(zhì)量與求解效率，并結合實際拆卸情況，將Pareto AFSA的參數(shù)設置為：Nfish=25，ntry=16，δ=0.8，V=20，gmax=20，TC=18。實驗運行20次，計算平均運行時間為34.05 s，取其中一次求解結果的平衡方案列于表2，共求得8個非劣解。

表2 Pareto AFSA求解P25的非劣解Tab.2 Noninferior solution of P25 of Pareto AFSA

分析表1可知：按Pareto支配關系的定義，VNS結果方案支配GA、SA、PSO、ABC4種算法結果方案；SA、PSO、ABC結果方案相同，3種算法方案支配GA結果方案。對比表1、表2可知：Pareto AFSA方案1與VNS方案相同，其他7種方案與VNS方案互不占優(yōu)。Pareto AFSA方案1、方案2支配GA、SA、PSO與ABC的方案，方案3～方案8與GA、SA、PSO與ABC的方案互不占優(yōu)，方案5～方案8在f1、f2上差于GA、SA、PSO與ABC的方案，但在f3、f4上明顯優(yōu)于4種算法方案。

通過對比可知，所提Pareto AFSA不僅能夠求得比GA、SA、PSO、ABC更優(yōu)的方案，還能求得與4種算法互不占優(yōu)的方案，表明Pareto AFSA較GA、SA、PSO、ABC有明顯優(yōu)勢。Pareto AFSA結果方案個數(shù)明顯多于VNS求得的單一方案，驗證了Pareto AFSA求解多目標拆卸線平衡問題的結果具有多樣性。

文獻[7-11]中，GA、SA、PSO、ABC、VNS等5種算法均只求得一個單解，這些算法均是將多目標拆卸線平衡問題轉(zhuǎn)化為單目標問題進行求解，求解過程中只側重于某幾個目標而忽略其他目標。多目標拆卸線優(yōu)化問題中，各目標之間存在相互沖突的關系，其結果是解的某幾個目標較好(如f1、f2)而其他目標較差(如f3、f4)，并且使求解結果喪失了多樣性。Pareto AFSA能很好地兼顧多目標間的均衡性，求得8種可選平衡方案，每種方案結果各有側重，實現(xiàn)了求解結果的多樣性。

綜上所述，Pareto AFSA能有效求解多目標拆卸線平衡問題，且在求解性能上優(yōu)于文獻[7-11]的單目標算法GA、SA、PSO、ABC、VNS。

3.2 實例應用

以文獻[14]中的高速電子套結機拆卸線實例為研究對象，闡述所提算法在實例應用中的性能。實例對機殼的52個零件進行完全拆卸，機殼零件爆炸圖、零件的拆卸任務優(yōu)先關系圖、拆卸時間和拆卸成本等數(shù)據(jù)詳見文獻[14]，此處不再給出。文獻方案的優(yōu)化目標為最小化平均閑置率Fidle、最大化負荷均衡指標Fsmooth、最小化拆卸成本Fcost。為方便對比，引入該文獻的這3個目標函數(shù)：

(14)

(15)

(16)

minF=min(Fidle,1-Fsmooth,Fcost)

(17)

式中，Un為拆卸任務n的單位時間拆卸成本。

根據(jù)52項拆卸任務的實際拆卸情況，綜合考慮算法的求解性能與求解時間，將Pareto AFSA的參數(shù)設置為：Nfish=30，ntry=10，δ=0.8，V=40，gmax=20，TC=600。采用所提Pareto AFSA對實例進行求解，共求得8個非劣解的Pareto解集，Pareto前沿空間分布如圖7所示。將求得的Pareto前沿與文獻[14]的Pareto ACO結果在3個目標上進行對比，如圖8、圖9所示。

圖7 AFSA求解P52的Pareto前沿Fig.7 Pareto front edge of P52 of AFSA

圖8 AFSA與ACO在Fidle上對比Fig.8 Comparison of Fidle on AFSA and ACO

圖9 AFSA與ACO在Fcost、Fsmooth上對比Fig.9 Comparison of Fcost and Fsmooth on AFSA and ACO

由圖8可知：在Fidle指標上，所提AFSA的8種方案均求得最優(yōu)解0.0597，ACO有6種方案求得最優(yōu)解0.0597，其他4種方案為0.1757。由圖9可知：在Fsmooth指標上，AFSA求解結果中除了方案6劣于ACO的方案10外，其他方案均優(yōu)于ACO的方案；在Fcost指標上，AFSA的8種方案都優(yōu)于ACO的10種方案。綜合對比3個目標可知：所提AFSA的方案6與ACO的方案10互不支配，方案6支配ACO的其他9種方案；AFSA的其他7種方案中，每一種方案都支配ACO的10種方案。由此可知，在求解質(zhì)量上所提Pareto AFSA較文獻[14]的Pareto ACO有明顯優(yōu)勢。

分析表3可知，本文算法求得的8種方案閑置率都相同，因此在方案選擇上只需考慮負荷均衡指標和拆卸成本指標。由圖7可知：若要求負荷均衡率最高，可選方案2；若要求拆卸成本最低，可選方案6；若既要負荷均衡率高，又要拆卸成本低，可選方案1或方案4。8種方案的負荷均衡率均在96.9%～99.8%之間，各種方案的負荷率已經(jīng)非常均衡，拆卸成本在129～151之間，拆卸成本也得到進一步降低，實現(xiàn)了平衡方案性能指標的大幅提升，為決策者提供了多種可選方案。

表3 Pareto AFSA求解P52的非劣解Tab.2 Noninferior solution of P52 of Pareto AFSA

4 結論

(1)針對傳統(tǒng)方法求解多目標拆卸線平衡問題時將其轉(zhuǎn)化為單目標問題求解的不足，本文設計了一種Pareto多目標人工魚群算法，得到多種兼顧各個目標偏好程度的平衡方案，實現(xiàn)了求解結果的有效性與多樣性。

(2)在人工魚覓食過程中，通過引入遺傳算法的隨機交叉操作，指導魚群向全局最優(yōu)方向收斂，避免魚群陷入局部最優(yōu)。在人工魚覓食行為、聚群行為與追尾行為過程中均采用擁擠距離機制來篩選非劣解，保留了各行為結果的多樣性。將算法迭代過程中外部檔案的非劣解作為下次迭代的種群，實現(xiàn)了種群的更新，提升了魚群的全局尋優(yōu)能力，加快了算法的收斂速度。

(3) 基于25項拆卸任務算例，求得8種可選平衡方案，并與現(xiàn)有5種單目標算法進行對比，驗證了所提算法的有效性。進而將所提算法應用于52項拆卸任務實例中，對比Pareto蟻群算法，結果證實了所提算法的優(yōu)越性。

[1] GUNGOR A, GUPTA S M. Disassembly Line in Product Recovery[J]. International Journal of Production Research, 2002, 40(11): 2569-2589.

[2] AVIKAL S, MISHRA P K, JAIN R. A Fuzzy AHP and PROMETHEE Method-based Heuristic for Disassembly Line Balancing Problems[J]. International Journal of Production Research, 2014, 52(5): 1306-1317.

[3] ALTEKIN F T, AKKAN C. Task-failure-driven Rebalancing of Disassembly Lines[J]. International Journal of Production Research, 2012, 50(18): 4955-4976.

[4] McGOVERN S M, GUPTA S M. A Balancing Method and Genetic Algorithm for Disassembly Line Balancing [J]. European Journal of Operational Research, 2007, 179(3): 692-708.

[5] McGOVERN S M, GUPTA S M. Ant Colony Optimization for Disassembly Sequencing with Multiple Objectives[J]. The International Journal of Advanced Manufacturing Technology, 2006, 30(5/6): 481-496.

[6] McGOVERN S M, GUPTA S M. Combinatorial Optimization Analysis of the Unary NP-complete Disassembly Line Balancing Problem[J]. International Journal of Production Research, 2007, 45(18/19): 4485-4511.

[7] KALAYCI C B, GUPTA S M. A Hybrid Genetic Algorithm Approach for Disassembly Line Balancing [C]//Proceedings of the 42nd Annual Meeting of Decision Science Institute. Boston, 2011: 2142-2148.

[8] KALAYCI C B, GUPTA S M, NAKASHIMA K. A Simulated Annealing Algorithm for Balancing a Disassembly Line[C]//Proceedings of the Seventh International Symposium on Environmentally Conscious Design and Inverse Manufacturing. Kyoto, Japan, 2011: 713-718.

[9] KALAYCI C B, GUPTA S M. A Particle Swarm Optimization Algorithm for Solving Disassembly Line Balancing Problem[C]//Proceedings of Northeast Decision Sciences Institute 2012 Annual Conference. Newport, Rhode Island, USA, 2012: 347-357.

[10] KALAYCI C B, GUPTA S M. Artificial Bee Colony Algorithm for Solving Sequence-dependent Disassembly Line Balancing Problem[J]. Expert Systems with Applications, 2013, 40(18): 7231-7241.

[11] KALAYCI C B, POLAT O, GUPTA S M. A Variable Neighbourhood Search Algorithm for Disassembly Lines [J]. Journal of Manufacturing Technology Management, 2015, 26(2): 182-194.

[12] KALAYCI C B, GUPTA S M. Tabu Search for Disassembly Line Balancing with Multiple Objectives[C]//41st International Conference on Computers and Industrial Engineering. Los Angeles, 2011: 477-482.

[13] 朱興濤, 張則強, 朱勛夢, 等. 求解多目標拆卸線平衡問題的一種蟻群算法[J]. 中國機械工程, 2014, 25(8): 1075-1079. ZHU Xingtao, ZHANG Zeqaing, ZHU Xunmeng, et al. An Ant Colony Optimization Algorithm for Multi-objective Disassembly Line Balancing Problem [J]. China Mechanical Engineering, 2014, 25(8): 1075-1079.

[14] 丁力平, 譚建榮, 馮毅雄, 等. 基于Pareto蟻群算法的拆卸線平衡多目標優(yōu)化[J]. 計算機集成制造系統(tǒng), 2009, 15(7): 1406-1413. DING Liping, TAN Jianrong, FENG Yixiong, et al. Multiobjective Optimization for Disassembly Line Balancing Based on Pareto Ant Colony Algorithm [J].Computer Integrated Manufacturing Systems, 2009, 15(7)：1406-1413.

[15] CHENG C, LI H F, BAO C H. Hybrid Artificial Fish Algorithm to Solve TSP Problem[C]//Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation. Tianjin, 2016: 275-285.

[16] He Q, Hu X, Ren H, et al. A Novel Artificial Fish Swarm Algorithm for Solving Large-scale Reliability-redundancy Application Problem[J]. ISA Transactions, 2015, 59: 105-113.

[17] AZAD M A K, ROCHA A M A C, Fernandes E M G P. Solving Large 0-1 Multidimensional Knapsack Problems by a New Simplified Binary Artificial Fish Swarm Algorithm[J]. Journal of Mathematical Modelling and Algorithms in Operations Research, 2015, 14(3): 313-330.

[18] DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

(編輯 張 洋)

Pareto Artificial Fish Swarm Algorithm for Multi-objective Disassembly Line Balancing Problems

WANG Kaipu ZHANG Zeqiang MAO Lili LI Liuke

School of Mechanical Engineering，Southwest Jiaotong University，Chengdu，610031

In view of complexity of disassembly line balancing problems, an improved multi-objective artificial fish swarm algorithm was proposed based on Pareto set. In order to improve the searching ability of artificial fish, a random crossover operation of genetic algorithm was introduced to guide the artificial fish to the direction of global optimal disassembly directions. The crowding distance was adopted to filter the non-inferior solutions in the prey, swarm and follow processes of the artificial fish to realize the diversity of each behavior solution results. By employing the strategy of elite reservation, the non-inferior solutions in external file were added to the next iteration of the algorithm, which speeded up the convergence rate of the algorithm. Finally, the proposed algorithm was applied to the disassembly instances of different scales, and the results confirm the effectiveness and superiority of the proposed algorithm by comparing with the existing algorithms.

disassembly line balancing problem; multi-objective optimization; Pareto set; artificial fish swarm algorithm

2016-04-12

國家自然科學基金資助項目(51205328，51405403)；教育部人文社會科學研究青年基金資助項目(12YJCZH296)；四川省應用基礎研究計劃資助項目(2014JY0232)

TH122

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

汪開普，男，1991年生。西南交通大學機械工程學院碩士研究生。主要研究方向為生產(chǎn)線平衡與智能優(yōu)化。E-mail:wkp2010698@163.com。張則強(通信作者)，男，1978年生。西南交通大學機械工程學院教授、博士研究生導師。毛麗麗，女，1992年生。西南交通大學機械工程學院碩士研究生。李六柯，男，1993年生。西南交通大學機械工程學院碩士研究生。