面向拆卸線平衡的維度學習多目標粒子群優(yōu)化

肖閃麗，王宇嘉，于 慧

(上海工程技術大學 電子電氣工程學院，上海 201620)

在實際生產(chǎn)中拆卸線平衡問題(Disassembly Line Balancing Problem, DLBP)需要同時優(yōu)化多個相互牽制甚至互相矛盾的目標，是一類典型的NP組合優(yōu)化問題。Gungor等人[1]首先提出了DLBP，并采用了一種啟發(fā)式算法，但該方法的缺點是求解效果具有不確定性。Altekin和Llambert等人[2-3]利用啟發(fā)式算法求解基于拆卸利潤最優(yōu)的DLBP。文獻[4]提出了基于線性加權的多目標蟻群算法, 但其實質仍是單目標優(yōu)化。文獻[5～6]分別運用改進的蟻群算法和遺傳算法求解多目標DLBP，但在實際求解過程中卻把多目標問題轉化成了具有優(yōu)先順序的單目標問題。Kongar等人[7]利用遺傳算法，考慮了多個目標來實現(xiàn)DLBP，但其針對大規(guī)模問題的求解性能還有待提升。丁力平等人[8]提出Pareto蟻群算法求解拆卸線的多目標問題，其目標為平均閑置率、負荷均衡指標和拆卸成本，但在解決復雜的DLBP上可能會出現(xiàn)早熟現(xiàn)象。Kalayci等人[9-11]提出了基于鄰居變異操作的粒子群優(yōu)化算法、蜂群算法和蟻群算法，但其沒有考慮算法自身存在易陷入局部最優(yōu)的問題。

粒子群算法憑借實現(xiàn)容易、控制參數(shù)少以及收斂速度快的特點[12]，目前廣泛應用在工業(yè)生產(chǎn)上。本文根據(jù)生產(chǎn)實際的需要構建了DLBP數(shù)學模型，并采用基于維度學習的多目標粒子群算法(DL-MOPSO)對其進行優(yōu)化求解。

1 多目標拆卸線平衡問題的數(shù)學模型

1.1 拆卸線平衡問題描述

1.2 拆卸線平衡問題數(shù)學模型

(1)盡可能減小工作站的數(shù)量

minf1=m

(2)最小化工作站的空閑時間

(3)最小化需求指數(shù)：根據(jù)市場需要對零件進行拆卸，減少庫存壓力

其中，PSi表示在拆卸序列中第i個零件；dPSi代表任務為PSi的零部件的需求量；N為自然數(shù)集；

(4)盡早拆除危害零部件：可減少危害，節(jié)約成本。

綜上所述，本文對拆卸線平衡問題優(yōu)化的數(shù)學模型如式(1)所示

minf=min{f1,f2,f3,f4}

(1)

約束條件如式(2)所示

(2-a)

(2-b)

(2-c)

其中，ti為第i個任務的作業(yè)時間；式(2-a)表示每個任務必須要分配給工作站，且只能分配給一個工作站；式(2-b)表示工作站數(shù)的取值范圍；m*表示所需的最小工作站數(shù)；式(2-c)表示任務i分配給工作站j時，其之前的任務都已經(jīng)分配給j之前的工作站，即保證在滿足拆卸任務優(yōu)先關系的情況下分配作業(yè)任務；IP表示在任務i之前的集合。

2 動態(tài)鄰居維度學習的多目標粒子群算法

2.1 粒子的編碼與解碼

拆卸線平衡問題是離散優(yōu)化問題，與連續(xù)優(yōu)化問題不同，在求解之前要確定粒子的編碼與解碼方案。本文利用帶優(yōu)先權的零入度拓撲排序方法建立粒子位置與拆卸序列之間的映射關系[13]。

以7個零部件的拆卸為例，其用優(yōu)先圖表示的拆卸任務之間的先后關系如圖1所示，其拆卸優(yōu)先權如表1所示。

圖1 7個零部件拆卸優(yōu)先順序

粒子維度1234567優(yōu)先權0.20.30.40.10.50.50.6

由圖1可得, 開始只有零件O1的入度為0，故選擇O1為拆卸序列的第一個，接下來零件O2和O4的入度為0，但零件O2的優(yōu)先權大于O4的優(yōu)先權，因此下一個可用來拆卸的零件為O2。重復上述過程，直到零件集為空集。該粒子經(jīng)解碼后得到的可行的拆卸序列(Feasible disassembly Sequence，F(xiàn)OS)為[1，2，5，6，3，4，7]。

2.2 動態(tài)鄰居拓撲結構

Suganthan等[14]提出了將環(huán)形結構與星形結構結合起來的動態(tài)鄰居構建策略來減小種群陷入局部最優(yōu)的概率。在粒子鄰居數(shù)增長模型中，當任意兩個粒子滿足式(3)時，認定上述兩粒子為鄰居關系

(3)

其中，xi和xbin為種群中任意兩粒子；t為算法當前迭代次數(shù)；tmax為算法最大迭代次數(shù)；dmax是任意兩個粒子間的最大距離。

2.3 構建最優(yōu)維度粒子

為平衡學習過程中的探索性能和開發(fā)性能[15]，在DL-MOPSO算法中，選取每個粒子鄰居中最優(yōu)維度。

粒子i的每一維學習對象根據(jù)式(4)選取，構成的新學習個體為

(4)

2.4 粒子的速度更新

為提高種群的多樣性，本文按如下方法對粒子進行更新：

步驟 1 隨機選出粒子i的p(j∈p)個維數(shù)，根據(jù)式(5-a)使粒子i向gbest學習

vi,j=wvi,j+rand()(gbestj-xi,j)

(5-a)

步驟 2 再隨機選出粒子i的q(j∈q)個維數(shù)，根據(jù)式(5-b)使粒子 向鄰居中最優(yōu)維度組成的新個體pbestbin學習

vi,j=wvi,j+rand()(pbestbin(j)-xi,j)

(5-b)

步驟 3 剩余維數(shù)D-p-q(j∈D-p-q)根據(jù)式(5-c)使粒子i向自身的pbest學習

vi,j=wvi,j+rand()(pbesti,j-xi,j)

(5-c)

其中，p和q分別由精英概率pm和學習概率pc決定；pc決定了粒子的某一維向pbest或pbestbin的學習能力；pm決定了粒子的某一維向gbest的學習能力。

2.5 學習樣本的選取和隨機向導學習策略

2.5.1 全局最優(yōu)位置的選取

本文根據(jù)密集距離distancei[16]的大小選擇全局最優(yōu)解，其計算如式(6)所示，擁有密集距離較大的粒子將作為全局最優(yōu)粒子

(6)

2.5.2 個體最優(yōu)位置的更新

本文提出一種隨機向導學習策略來更新pbest，即當一個粒子連續(xù)T代個體最優(yōu)位置沒有得到提升時，隨機產(chǎn)生若干個粒子與pbest進行支配性比較，在支配的粒子中隨機選擇一個粒子替代pbest；當條件不滿足時，隨機選擇一個其它粒子的pbest進行更新。

3 面向拆卸線平衡問題的多目標粒子群優(yōu)化

步驟 1 算法初始化，包括：種群規(guī)模Num；外部檔案規(guī)模NP；粒子位置x和速度v；搜索空間維數(shù)D(實際為拆卸產(chǎn)品的零件數(shù)量)；慣性權值w；粒子全局最優(yōu)位置gbest；個體最優(yōu)歷史位置pbest；粒子最優(yōu)維度個體pbestbin；學習概率pc；精英概率pm；隨機向導學習持續(xù)代數(shù)閾值T；最大迭代次數(shù)tmax；目標向量f；拆卸任務偏序集Z；工作站節(jié)拍CT；

步驟 2 對粒子進行解碼操作，根據(jù)優(yōu)先關系確定外部檔案NP中的粒子；

步驟 3 從外部檔案中隨機選取兩個粒子，根據(jù)式(6)計算密集距離確定所對應粒子的全局最優(yōu)位置gbest；

步驟 4 根據(jù)式(3)確定粒子的鄰居個數(shù)，利用式(4)確定粒子每一維學習樣本；

步驟 5 采用隨機向導學習策略更新粒子個體最優(yōu)歷史位置pbest；

步驟 6 根據(jù)式(5-a)～(5-c)更新粒子的速度v；

步驟 7 計算每個FOS狀態(tài)下的適應度函數(shù)，并對外部檔案文件NP進行更新和維護；

步驟 8 如果終止條件成立，則停止搜索，對非劣解進行解碼，輸出非劣解和非劣解所對應的目標值，否則轉到步驟 3；

步驟 9 對得到的最優(yōu)拆卸序列完成工作站的分配。

4 實驗分析

實例1 以零件數(shù)目為10的部件拆卸為例，零部件優(yōu)先順序如圖2所示，其拆卸時間、需求和危害等信息見文獻[17]，工作節(jié)拍CT為40s。

圖2 零部件拆卸優(yōu)先順序

本文算法與文獻[5]、文獻[9]和文獻[18]的優(yōu)化結果進行比較，如表2所示，本文的優(yōu)化結果在需求指數(shù)f3上遠遠優(yōu)于文獻[5]；相對于文獻[9]和文獻[18]，本文所得優(yōu)化解與其互不支配。由上可得，本文所提算法的優(yōu)勢在于不僅得到了優(yōu)于或與現(xiàn)有文獻一致的拆卸序列，而且在考慮了生產(chǎn)實際情況后，為決策者提供了更多的備選拆卸方案，尤其在對產(chǎn)品不同需求方面為決策者提供了有利的參考。

表2 零件數(shù)目為10的優(yōu)化結果

實例2 以零件數(shù)目為25的部件拆卸為例，其零部件優(yōu)先順序如圖3所示，拆卸時間、需求和危害等信息見文獻[19]，工作節(jié)拍CT為18s。

表3列出了現(xiàn)有算法在DLBP上所優(yōu)化的經(jīng)典解，本文所得優(yōu)化解如圖4所示。從表3中可以看出，文獻[5]在該問題上不能得到較好結果，說明隨著拆卸規(guī)模的增大，其求解精度下降。本文算法所得優(yōu)化解(f1=9,f2=9,f3=806,f4=74)相比與文獻[7]、文獻[9]和文獻[18]，在工作站數(shù)為理論值且空閑時間f2保持一致的前提下，本文算法所求得的需求指數(shù)f3和盡早拆除危害零部件f4均得到了不同程度的改善，尤其需求指數(shù)f3相對來說有了大幅度下降。根據(jù)支配解的定義，文獻[18]的優(yōu)化結果支配文獻[7]和文獻[9], 而本文得到的解在每一個目標函數(shù)上均優(yōu)于文獻[18]。由本實例可以看出，隨著問題的復雜程度的增加，本文所提算法能夠找到解決多目標DLBP較優(yōu)的拆卸序列。

圖3 25個零部件優(yōu)先拆卸順序

結果來源方法文獻[5]ACO--------文獻[9]PSO9985780續(xù)表3 文獻[18]VNS9982576文獻[7]MOACO911898859992787

圖4 各工作站上作業(yè)元素及時間(f1=9,f2=9,f3=806,f4=74)

從上述實例可以看出，本文所提出的算法可以有效解決DLBP問題，并且隨著問題規(guī)模的增大，可以顯著提高拆卸效率，避免算法易陷入局部最優(yōu)，在平衡多個拆卸目標的同時，給出多種拆卸策略，滿足了不同決策者的實際需要。

5 結束語

本文從經(jīng)濟性和環(huán)保性角度，構建了包含4個決策目標的拆卸線平衡問題數(shù)學模型，并根據(jù)模型特點采用基于維度學習的多目標粒子群算法進行求解。該算法通過動態(tài)的鄰居拓撲結構、最優(yōu)個體維度學習和隨機向導學習策略保證了種群的多樣性，避免種群早熟陷入局部最優(yōu)，有效提高了算法的全局搜索能力。最后，通過對不同規(guī)模的拆卸線平衡問題進行驗證，結果表明本文所提出的方法在處理大規(guī)模拆卸線平衡問題時，能夠為決策者提供多種拆卸策略，在滿足最小工作站要求下，提高拆卸效率，為解決大規(guī)模多目標拆卸線平衡問題提供了一種有效的解決方法。

[1]GungorA,GuptaSM,PochampallyK,etal.Complicationsindisassemblylinebalancing[J].ProceedingsofSPIE-TheInternationalSocietyforOpticalEngineering, 2000, 4193:289-298.

[2]AlekinFT,KandillerL,OzdemirelNE.Disassemblylinebalancingwithlimitedsupplyandsubassemblyavailability[C].Bellingham,Washington:ProceedingsofSPIE,SPIA,2004.

[3]NazarianE,KoJ,WangH.Designofmulti-productmanufacturinglineswiththeconsiderationofproductchangedependentinter-tasktimes,reducedchangeoverandmachineflexibility[J].JournalofManufacturingSystems, 2010, 29(1):35-46.

[4]ChenBW,SongSM,ChenXL.Vehicleroutingproblemwithfuzzydemandsanditsheuristicantcolonyalgorithm[J].JournalofComputerApplications, 2006, 26(11):2639-2638.

[5]McGovernSM,GuptaSM.Antcolonyoptimizationfordisassemblysequencingwithmultipleobjectives[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2006, 30(5):481-496.

[6]KongarE,GuptaSM.Disassemblysequencingusinggeneticalgorithm[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2006, 30(5):497-506.

[7]DingLP,FengYX,TanJR,etal.Anewmulti-objectiveantcolonyalgorithmforsolvingthedisassemblylinebalancingproblem[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2010, 48(5):761-771.

[8]KalayciCB,GuptaSM.Aparticleswarmoptimizationalgorithmwithneighborhood-basedmutationforsequence-dependentdisassemblylinebalancingproblem[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2013, 69(1):197-209.

[9]BentahaML,BattaaO,DolguiA.Asampleaverageapproximationmethodfordisassemblylinebalancingproblemunderuncertainty[J].Computers&OperationsResearch, 2014, 51(3):111-122.

[10]KalayciCB,GuptaSM.Antcolonyoptimizationforsequence-dependentdisassemblylinebalancingproblem[J].JournalofManufacturingTechnologyManagement, 2013, 24(3):413-427.

[11]AwadAR,ChibanSO.Recentadvancesinglobaloptimizationforcombinatorialdiscreteproblems[J].AppliedMathematics, 2015, 6(11):1842-1856.

[12] 王閃閃.基于群智能算法的神經(jīng)網(wǎng)路建模研究[J].電子科技,2017,30(4):56-59.

[13]DouJ,SuC,LiJ.Adiscreteparticleswarmoptimizationalgorithmforassemblylinebalancingproblemoftype1[C].ThirdInternationalConferenceonMeasuringTechnologyandMechatronicsAutomation.IEEE, 2011.

[14]SuganthanPN.Particleswarmoptimizerwithneighborhoodoperator[C].Piscataway,NJ,USA:ProceedingsofIEEECongressonEvolutionaryComputation(CEC), 1999.

[15]LynnN,SuganthanPN.Comprehensivelearningparticleswarmoptimizerwithguidancevectorselection[C].Singapore:IEEESymposiumonSwarmIntelligence, 2013.

[16]RaquelCR,NavalPC.Aneffectiveuseofcrowdingdistanceinmulti-objectiveparticleswarmoptimization[C].WashingtonDC:InGeneticandEvolutionaryComputationConference, 2005.

[17]LuC,HuangHZ,FuhJYH,etal.Amulti-objectivedisassemblyplanningapproachwithantcolonyoptimizationalgorithm[J].ProceedingsoftheInstitutionofMechanicalEngineersPartBJournalofEngineeringManufacture, 2008, 222(11):1465-1474.

[18]TrikiH,MellouliA,HachichaW,etal.Ahybridgeneticalgorithmapproachforsolvinganextensionofassemblylinebalancingproblem[J].InternationalJournalofComputerIntegratedManufacturing, 2015, 29(5):504-519.

[19]KalayciCB,PolatO,GuptaSM.Ahybridgeneticalgorithmforsequence-dependentdisassemblylinebalancingproblem[J].AnnalsofOperationsResearch, 2016, 242(2):321-354.