基于NSGA-Ⅱ和TOPSIS算法的云制造服務(wù)組合優(yōu)選模型

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

（四川大學(xué)機(jī)械工程學(xué)院，成都 610065）

0 引言

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

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

本文綜合考慮服務(wù)需求方和云制造系統(tǒng)的利益，提出了一種新的云制造資源組合數(shù)學(xué)模型，該模型以執(zhí)行時(shí)間、服務(wù)成本、交付物質(zhì)量、云平臺(tái)能耗、服務(wù)滿意度為指標(biāo)體系，運(yùn)用NSGA-Ⅱ算法對(duì)該模型進(jìn)行求解。對(duì)于求得的Pareto解集，采用TOPSIS法對(duì)解集中的所有組合方案進(jìn)行排序，為選取最優(yōu)服務(wù)組合提供參考。

1 云制造服務(wù)組合問題描述

云制造系統(tǒng)服務(wù)組合優(yōu)選流程如圖1所示。云制造系統(tǒng)包括服務(wù)需求方、服務(wù)提供方和平臺(tái)運(yùn)營(yíng)方3個(gè)主體，在云制造環(huán)境下，服務(wù)需求方發(fā)送制造服務(wù)要求到云制造服務(wù)組合要經(jīng)歷任務(wù)分解、子任務(wù)搜索匹配、服務(wù)組合優(yōu)選3個(gè)階段。在任務(wù)分解階段，服務(wù)需求方上傳任務(wù)需求到云制造系統(tǒng)，云平臺(tái)調(diào)用任務(wù)解析工具對(duì)整個(gè)需求按照一定的規(guī)則進(jìn)行分解，分解得到的每個(gè)子任務(wù)能夠被單個(gè)候選資源集滿足；在子任務(wù)搜索匹配階段，通過調(diào)用搜索匹配工具為每個(gè)子任務(wù)匹配相應(yīng)的候選云制造資源集合，得到一系列候選資源集；在服務(wù)組合優(yōu)選階段，平臺(tái)在多目標(biāo)和多約束的條件下在各候選資源集中選取一個(gè)候選資源得到云制造服務(wù)優(yōu)選組合，該服務(wù)組合用來執(zhí)行服務(wù)需求方提交的總?cè)蝿?wù)，整個(gè)服務(wù)組合過程由云制造系統(tǒng)進(jìn)行跟蹤和反饋。

圖1 云制造服務(wù)組合優(yōu)選過程

2 云制造服務(wù)組合數(shù)學(xué)建模

考慮云制造平臺(tái)在服務(wù)執(zhí)行過程中的動(dòng)態(tài)性、不穩(wěn)定性，為方便建立數(shù)學(xué)優(yōu)化模型，作出以下假設(shè)：1）服務(wù)組合過程中不存在一個(gè)云制造資源同時(shí)為多個(gè)制造子任務(wù)服務(wù)的情況；2）以順序結(jié)構(gòu)作為云制造服務(wù)組合的研究對(duì)象。

2.1 約束指標(biāo)

2.1.1 服務(wù)需求方約束指標(biāo)

本文充分考慮服務(wù)需求方的需求和云制造服務(wù)運(yùn)行特點(diǎn)，并結(jié)合指標(biāo)的可量化性，選取執(zhí)行時(shí)間、服務(wù)成本、交付物質(zhì)量3個(gè)指標(biāo)，構(gòu)建服務(wù)需求方指標(biāo)約束體系[11]。

1）執(zhí)行時(shí)間T。服務(wù)需求方提交服務(wù)請(qǐng)求到取得服務(wù)結(jié)果所花費(fèi)的總時(shí)間。表達(dá)式為

防止服務(wù)過程出現(xiàn)風(fēng)險(xiǎn)，云制造系統(tǒng)會(huì)對(duì)服務(wù)提供方的服務(wù)滿意度P進(jìn)行約束。為了減少環(huán)境破壞，發(fā)展低能耗、低排放的低碳經(jīng)濟(jì)，云平臺(tái)運(yùn)營(yíng)方會(huì)增加對(duì)供應(yīng)商的能耗E評(píng)估[12]。

1）能耗E。云制造平臺(tái)在生產(chǎn)制造過程中產(chǎn)生的能源消耗E的計(jì)算公式為

2.2 多目標(biāo)組合優(yōu)選模型

云制造服務(wù)組合的總體目標(biāo)是使得所優(yōu)化指標(biāo)，即服務(wù)需求方的QOS最小、云制造平臺(tái)的能耗最低、服務(wù)滿意度最高來完成制造任務(wù)。綜合考慮服務(wù)需求方和云平臺(tái)的約束指標(biāo)，建立云制造服務(wù)組合數(shù)學(xué)模型：

5個(gè)約束分別表示模型中的執(zhí)行時(shí)間T不超過服務(wù)需求者規(guī)定的最長(zhǎng)時(shí)間Tmax，服務(wù)成本C不超過服務(wù)需求者規(guī)定的最高成本Cmax，交付物質(zhì)量Q不低于服務(wù)需求者規(guī)定的最低交付物質(zhì)量Qmin，能耗E不超過云平臺(tái)運(yùn)營(yíng)方要求的云制造服務(wù)組合過程中產(chǎn)生的最大能耗Emax，服務(wù)滿意度P不低于云平臺(tái)規(guī)定的最低服務(wù)滿意度Pmin。

3 模型求解

3.1 NSGA-II算法

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

圖2 NSGA-II算法流程圖

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

步驟2:通過錦標(biāo)賽法，從種群Pg選取部分個(gè)體交叉變異，產(chǎn)生種群數(shù)量為N的子代種群Qg。

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

步驟4:對(duì)種群Rg的個(gè)體進(jìn)行非支配排序，得到k個(gè)非支配解集F1，F(xiàn)2，…，F(xiàn)k。

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

步驟6:若F1，F(xiàn)2，…，F(xiàn)i中的所有個(gè)體數(shù)目超過N，對(duì)Fi中所有個(gè)體進(jìn)行擁擠度計(jì)算。根據(jù)精英策略，選擇Fi中較好的個(gè)體和F1～Fi-1中的所有個(gè)體合并組成種群數(shù)量為N的新種群Pg+1。

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

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

1）染色體編碼。采用整數(shù)方式編碼，對(duì)每一個(gè)子任務(wù)所對(duì)應(yīng)的候選制造資源進(jìn)行編號(hào)，染色體{3，2，4，1，3}分別對(duì)應(yīng)云制造服務(wù)組合{CMS13，CMS22，CMS34，CMS41，CMS53}，染色體基因編碼串與云制造服務(wù)組合逐一映射，如圖3所示。

圖3 云制造服務(wù)組合與染色體映射關(guān)系圖

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

圖4 單點(diǎn)交叉遺傳操作示意圖

3）變異。依據(jù)變異概率，在染色體編碼串上隨機(jī)選取某個(gè)點(diǎn)進(jìn)行變異，如圖5所示。

圖5 變異操作遺傳示意圖

3.2 服務(wù)組合優(yōu)選算法

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

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

4 算例論證

4.1 算例模型

某企業(yè)用戶將制造任務(wù)和相關(guān)需求提交至云平臺(tái)，云制造系統(tǒng)根據(jù)任務(wù)解析工具將制造任務(wù)分解。5個(gè)子任務(wù)分配的候選資源服務(wù)如表1所示，表2為云制造候選資源指標(biāo)參數(shù)。

表1 候選資源服務(wù)

表2 候選資源評(píng)價(jià)指標(biāo)相關(guān)參數(shù)

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

4.2 算例仿真

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

圖6 Pareto解集示意圖

根據(jù)求得的Pareto解集各服務(wù)組合的指標(biāo)參數(shù)構(gòu)建規(guī)范化決策矩陣，按照服務(wù)需求方的偏好和云制造系統(tǒng)的實(shí)際情況，執(zhí)行時(shí)間、服務(wù)成本、交付物質(zhì)量、云平臺(tái)能耗、服務(wù)滿意度對(duì)應(yīng)的權(quán)重分別為0.15、0.30、0.30、0.10、0.15，應(yīng)用TOPSIS理想解法對(duì)求得的Pareto最優(yōu)服務(wù)組合進(jìn)行排序，表3為求解的最優(yōu)服務(wù)組合。

表3 服務(wù)組合的最優(yōu)Pareto解集

根據(jù)表3結(jié)果，選擇云制造資源［CMS13，CMS21，CMS32，CMS23，CMS44，CMS52］為服務(wù)組合的最優(yōu)解,實(shí)驗(yàn)結(jié)果證明了算法與模型的有效性。此外，服務(wù)需求方可以根據(jù)實(shí)際需求偏好重新向云制造平臺(tái)提交指標(biāo)權(quán)重要求，云制造平臺(tái)只需根據(jù)新的權(quán)重就可對(duì)Pareto解集中的服務(wù)組合重新排序，無需再進(jìn)行求解，節(jié)省了雙方大量時(shí)間。

5 結(jié)論

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