基于NSGA-Ⅱ和TOPSIS算法的云制造服務組合優選模型

葉宗鑫，徐雷，余方超，高涵

（四川大學機械工程學院，成都 610065）

0 引言

隨著物聯網、云計算、大數據、5G通訊技術等新一代信息技術的快速發展及其與制造業的不斷融合，各制造強國紛紛頒布了一系列以“智能制造”為主題的國家戰略，例如美國工業互聯網計劃、德國工業4.0及中國制造2025等[1]。我國正面臨向制造強國轉型的階段，整個制造行業資源使用率和共享程度會是一個關鍵突破點。云制造是在現有制造技術的基礎上，受到云計算思想的啟發，結合信息技術發展起來的一個新概念[2]。云制造通過建立制造資源共享系統，充分利用社會制造資源，實現了制造資源的集成共享[3]。云制造服務組合是在云制造環境下完成制造任務的主要實現方式[4]，如何從大量云服務組合中選擇出最符合要求的服務組合方案，是目前云制造服務組合面臨的難題。

近些年來，對于云制造服務組合問題的研究，已經獲得了階段性的成果[5]。如Seghir等[6]構建了時間、成本、可靠性、可用性綜合最優的云制造資源模型，將遺傳算法與果蠅算法相結合，提高了算法的搜索效率；Lartigau等[7]除考慮服務質量等參數外，還將范圍擴展到制造資源的物理位置，通過自適應人工蜂群算法進行優化。如馬文龍等[8]通過服務質量評估模型進行服務組合優選，運用改進蟻群算法在動態環境中減少轉移時間和成本；易安斌等[9]對于云制造環境下制造資源異地的服務組合優選問題，建立了以時間、成本、可靠性的多目標模型；姚錫凡等[10]對人工蜂群算法進行了改進，引入食物源擾動的協同機制，來處理復雜的服務組合優選問題。

本文綜合考慮服務需求方和云制造系統的利益，提出了一種新的云制造資源組合數學模型，該模型以執行時間、服務成本、交付物質量、云平臺能耗、服務滿意度為指標體系，運用NSGA-Ⅱ算法對該模型進行求解。對于求得的Pareto解集，采用TOPSIS法對解集中的所有組合方案進行排序，為選取最優服務組合提供參考。

1 云制造服務組合問題描述

云制造系統服務組合優選流程如圖1所示。云制造系統包括服務需求方、服務提供方和平臺運營方3個主體，在云制造環境下，服務需求方發送制造服務要求到云制造服務組合要經歷任務分解、子任務搜索匹配、服務組合優選3個階段。在任務分解階段，服務需求方上傳任務需求到云制造系統，云平臺調用任務解析工具對整個需求按照一定的規則進行分解，分解得到的每個子任務能夠被單個候選資源集滿足；在子任務搜索匹配階段，通過調用搜索匹配工具為每個子任務匹配相應的候選云制造資源集合，得到一系列候選資源集；在服務組合優選階段，平臺在多目標和多約束的條件下在各候選資源集中選取一個候選資源得到云制造服務優選組合，該服務組合用來執行服務需求方提交的總任務，整個服務組合過程由云制造系統進行跟蹤和反饋。

圖1 云制造服務組合優選過程

2 云制造服務組合數學建模

考慮云制造平臺在服務執行過程中的動態性、不穩定性，為方便建立數學優化模型，作出以下假設：1）服務組合過程中不存在一個云制造資源同時為多個制造子任務服務的情況；2）以順序結構作為云制造服務組合的研究對象。

2.1 約束指標

2.1.1 服務需求方約束指標

本文充分考慮服務需求方的需求和云制造服務運行特點，并結合指標的可量化性，選取執行時間、服務成本、交付物質量3個指標，構建服務需求方指標約束體系[11]。

1）執行時間T。服務需求方提交服務請求到取得服務結果所花費的總時間。表達式為

防止服務過程出現風險，云制造系統會對服務提供方的服務滿意度P進行約束。為了減少環境破壞，發展低能耗、低排放的低碳經濟，云平臺運營方會增加對供應商的能耗E評估[12]。

1）能耗E。云制造平臺在生產制造過程中產生的能源消耗E的計算公式為

2.2 多目標組合優選模型

云制造服務組合的總體目標是使得所優化指標，即服務需求方的QOS最小、云制造平臺的能耗最低、服務滿意度最高來完成制造任務。綜合考慮服務需求方和云平臺的約束指標，建立云制造服務組合數學模型：

5個約束分別表示模型中的執行時間T不超過服務需求者規定的最長時間Tmax，服務成本C不超過服務需求者規定的最高成本Cmax，交付物質量Q不低于服務需求者規定的最低交付物質量Qmin，能耗E不超過云平臺運營方要求的云制造服務組合過程中產生的最大能耗Emax，服務滿意度P不低于云平臺規定的最低服務滿意度Pmin。

3 模型求解

3.1 NSGA-II算法

本文所構建的云制造服務組合模型是一個多目標優化問題，與單目標優化相比，多目標優化問題在求解時，由于優化的多個目標存在著相互制約的關系，某些目標函數值的改進可能會削弱其余目標函數，所以不可能同時讓多個目標達到最優。多目標優化的解通常是一組Pareto解集，其特點是在改進任一目標函數時，必然會導致至少一個其余目標函數的劣化。本文所選NSGA-II算法[13]是一種基于Pareto最優思想的多目標智能優化算法，它是由Deb和Srinivas在NSGA的基礎上提出的，與NSGA相比，NSGA-II主要有以下三方面改進[14]：1）提出了新的非支配排序算法，算法復雜度下降了一個量級；2）精英保留策略，父代和子代種群共同競爭，選取最優良的個體來組成下一代的種群，保證了種群的整體水平；3）采取擁擠距離比較算子，確定同一層級個體中不同個體的擁擠度值，并且將其視為同級個體的比較標準，確保種群的多樣性。使用NSGAII算法求解云制造服務優選組合模型的具體步驟如圖2所示。

圖2 NSGA-II算法流程圖

步驟1:g=0，隨機生成初始化種群Pg，種群數量為N，對種群Pg進行非支配排序和所有個體擁擠度的計算。

步驟2:通過錦標賽法，從種群Pg選取部分個體交叉變異，產生種群數量為N的子代種群Qg。

步驟3:合并Pg和Qg，形成種群數量為2N的種群Rg。

步驟4:對種群Rg的個體進行非支配排序，得到k個非支配解集F1，F2，…，Fk。

步驟5: 按照非支配解集排序從組合種群Rg依次選取種群個體，直到種群數量大于N，假設此時的非支配解集為Fi。

步驟6:若F1，F2，…，Fi中的所有個體數目超過N，對Fi中所有個體進行擁擠度計算。根據精英策略，選擇Fi中較好的個體和F1～Fi-1中的所有個體合并組成種群數量為N的新種群Pg+1。

步驟7:令g=g+1，反復迭代步驟2～步驟6，直至滿足流程終止條件。此時求解出云制造服務組合模型的Pareto解集。

根據云制造服務組合模型的特點，本文構造了NSGA-II算法的染色體基因編碼、交叉和變異過程，具體表示如下:

1）染色體編碼。采用整數方式編碼，對每一個子任務所對應的候選制造資源進行編號，染色體{3，2，4，1，3}分別對應云制造服務組合{CMS13，CMS22，CMS34，CMS41，CMS53}，染色體基因編碼串與云制造服務組合逐一映射，如圖3所示。

圖3 云制造服務組合與染色體映射關系圖

2）交叉。用單點交叉處理處理云制造服務組合的交叉操作。單點交叉為在染色體編碼串中隨機選取一個點，在該點處相互交換兩個個體的部分染色體，如圖4所示。

圖4 單點交叉遺傳操作示意圖

3）變異。依據變異概率，在染色體編碼串上隨機選取某個點進行變異，如圖5所示。

圖5 變異操作遺傳示意圖

3.2 服務組合優選算法

TOPSIS法是一種接近理想點的排序算法，由K. Yoon和C. L. Hwang于1981年提出，其基本原理是找出評價對象的正理想與負理想方案，依次計算各個方案與正、負理想方案的距離，確定各個方案與理想方案的接近程度，最后通過各個方案的滿意度排序選取一組最優解[15]。本文運用TOPSIS法對Pareto解集中的多個服務組合方案進行求解，得到最優云制造服務組合，其算法處理流程如下：

步驟1:NSGA-II算法求得的Pareto解集構成初始化決策矩陣X=（xij）m×n。zi=A+，則Ci=1；zi=A－，則Ci=0；Ci的值越高，方案的滿意度越好。

4 算例論證

4.1 算例模型

某企業用戶將制造任務和相關需求提交至云平臺，云制造系統根據任務解析工具將制造任務分解。5個子任務分配的候選資源服務如表1所示，表2為云制造候選資源指標參數。

表1 候選資源服務

表2 候選資源評價指標相關參數

根據服務需求方的制造需求和云制造系統的相關約束，服務組合中所需的算例參數分別為：WT=0.2，WC=0.4，WQ=0.4；Tmax=250 h，Cmax=2000 元，Qmin=0.95，Emax=400 kW·h，Pmin=0.87。結合式（8）可得云制造優選服務組合模型，并用NSGA-Ⅱ和TOPSIS算法求解。

4.2 算例仿真

采取最大迭代次數Gmax=200，交叉率Pc=0.9，變異率Pm=0.1，種群數量Np=50。通過算例仿真求解，實驗結果如圖6所示。圖中每個圓點代表一個Pareto最優服務組合方案，可以看出通過NSGAII算法求解模型所得的服務組合數量為22個。

圖6 Pareto解集示意圖

根據求得的Pareto解集各服務組合的指標參數構建規范化決策矩陣，按照服務需求方的偏好和云制造系統的實際情況，執行時間、服務成本、交付物質量、云平臺能耗、服務滿意度對應的權重分別為0.15、0.30、0.30、0.10、0.15，應用TOPSIS理想解法對求得的Pareto最優服務組合進行排序，表3為求解的最優服務組合。

表3 服務組合的最優Pareto解集

根據表3結果，選擇云制造資源［CMS13，CMS21，CMS32，CMS23，CMS44，CMS52］為服務組合的最優解,實驗結果證明了算法與模型的有效性。此外，服務需求方可以根據實際需求偏好重新向云制造平臺提交指標權重要求，云制造平臺只需根據新的權重就可對Pareto解集中的服務組合重新排序，無需再進行求解，節省了雙方大量時間。

5 結論

如何減少在云制造模式下的能耗，實現經濟的可持續發展是未來國家智能制造發展的主要關注點。本文分析了云制造服務組合的重要性和服務流程，在充分考慮云制造平臺在服務過程的不確定性前提下，提出了一種以執行時間最少、服務成本最低、交付物質量最優、云平臺能耗最小、服務滿意度最高的云制造服務組合優化模型，為了使多個目標同時達到優化，運用快速非支配排序遺傳算法（NSGA-Ⅱ）對多目標數學模型求解，對于NSGA-Ⅱ求得的Pareto解集，采用TOPSIS優劣解距離法對解集中的服務組合進行綜合排序，選取最符合服務需求方和云制造平臺利益的服務組合。通過算例實驗論證，驗證了所提模型和求解算法在解決云制造服務組合問題的有效性和可行性。