邵一凡, 禹春霞, 禹嘉誠

(1.中國石油大學(xué) (北京)經(jīng)濟管理學(xué)院,北京 102249; 2.廈門大學(xué) 管理學(xué)院,福建 廈門 361005; 3.北京體育大學(xué)體育商學(xué)院,北京 100084)

0 引言

云制造的概念最早由李伯虎院士提出[1]，是一種面向服務(wù)的網(wǎng)絡(luò)化制造新模式，其以客戶為核心、以知識為支撐，構(gòu)建了一個虛擬化、分布式、按需分配的資源共享平臺[2]。在云制造模式下，分布式制造資源被封裝到不同的云服務(wù)中，形成服務(wù)池，由云制造平臺按需調(diào)配，極大地提高了制造資源的利用效率及社會生產(chǎn)力，為實現(xiàn)我國制造強國的目標(biāo)提供了有力支撐。近年來，隨著制造任務(wù)日益復(fù)雜，單一的云制造服務(wù)已無法滿足生產(chǎn)需求，云制造平臺需要將復(fù)雜制造任務(wù)分解為若干子任務(wù)，為各個子任務(wù)匹配合適的云服務(wù)，形成云服務(wù)組合，并在眾多服務(wù)組合中選擇最優(yōu)組合供用戶使用，這個過程稱為云服務(wù)組合優(yōu)化，是云制造平臺亟需關(guān)注的問題。

在云制造平臺中，針對同一個子任務(wù)有大量功能屬性相同但非功能屬性不同的云服務(wù)，云服務(wù)的非功能性屬性通常用QoS(服務(wù)質(zhì)量)來描述[3]。在實際應(yīng)用中，云制造服務(wù)的QoS指標(biāo)眾多，因此云制造服務(wù)組合優(yōu)化問題應(yīng)被看作高維多目標(biāo)優(yōu)化問題。當(dāng)前關(guān)于云服務(wù)組合優(yōu)化問題的求解方式大致分為以下三種：第一種是將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題進行求解[4～6]，第二種是直接利用多目標(biāo)優(yōu)化算法進行求解[7～9]，第三種是將所有組合枚舉出來利用多屬性評價方法選擇最優(yōu)組合[10]。在實際應(yīng)用中，QoS指標(biāo)間往往是相互沖突的，且轉(zhuǎn)化為單目標(biāo)優(yōu)化問題進行求解時極容易陷入局部最優(yōu)解，因此第一種方式可能會造成結(jié)果不準(zhǔn)確，且非常依賴各指標(biāo)權(quán)重；第三種方式在子任務(wù)及備選服務(wù)較多時會造成運算量呈指數(shù)型增長，不適用于大規(guī)模的云服務(wù)組合優(yōu)化；第二種方式相對更加合理。但是當(dāng)前采用第二種方式的多目標(biāo)優(yōu)化模型的目標(biāo)函數(shù)的維度往往比較低，而云服務(wù)組合的評價指標(biāo)眾多，僅靠少數(shù)目標(biāo)函數(shù)進行組合優(yōu)化會相對片面。因此，本文提出的云制造服務(wù)組合優(yōu)化問題的求解算法具有以下創(chuàng)新點：

(1)本文將云制造服務(wù)組合優(yōu)化轉(zhuǎn)化為高維多目標(biāo)優(yōu)化問題，從線上、線下兩方面構(gòu)建QoS評價體系。

(2)對多目標(biāo)優(yōu)化算法NSGA-II進行改進，提出一種基于nα支配的NSGA-II算法，使算法能夠更好地處理高維多目標(biāo)優(yōu)化問題并消除量綱影響。

1 云制造服務(wù)組合優(yōu)化模型

1.1 QoS評價指標(biāo)體系

云制造服務(wù)包括線上交易與線下生產(chǎn)兩部分，相對于普通制造服務(wù)來說，云制造服務(wù)需要更多地考慮網(wǎng)絡(luò)性能以滿足線上交易的需求；相對于基于web的云服務(wù)來說，云制造服務(wù)需要更側(cè)重于線下生產(chǎn)制造的能力。因此，本文將云制造服務(wù)的評價體系分為線上和線下兩部分，構(gòu)建新的基于云制造的云服務(wù)QoS評價體系。

1.1.1 線上指標(biāo)

云制造服務(wù)的線上部分要求其具備良好的網(wǎng)絡(luò)服務(wù)性能，這一部分與web云服務(wù)非常相似，本文主要基于web云服務(wù)的QoS常用評價指標(biāo)，從云制造的網(wǎng)絡(luò)能力及線上服務(wù)能力兩方面進行考慮，篩選出對云服務(wù)影響較大的四個指標(biāo)：

(1)服務(wù)可用性(C1)：云服務(wù)在特定時間內(nèi)能夠被成功訪問的可能性。

(2)服務(wù)安全性(C2)：云服務(wù)商為防止信息泄露，對用戶數(shù)據(jù)傳輸進行保護及加密的能力。

(3)服務(wù)信譽度(C3)：用戶在制造完成后對云服務(wù)商提供信息的準(zhǔn)確性及制造過程誠信度的整體評價。

(4)信息共享能力(C4)：云服務(wù)商將其在平臺中的制造及服務(wù)信息共享給其他共同協(xié)作服務(wù)商的準(zhǔn)確性與及時性。

1.1.2 線下指標(biāo)

云制造服務(wù)的線下制造部分要求其確保服務(wù)的價格及工期合理，且能夠準(zhǔn)確交貨。對于復(fù)雜制造任務(wù)來說，需要各個服務(wù)間協(xié)同配合，因此物流運輸能力對各個云服務(wù)也非常重要。本文選取的主要線下指標(biāo)包括以下四個：

(1)價格(C5)：用戶獲取制造服務(wù)所需的成本，包括制造價格、服務(wù)價格等。

(2)交貨準(zhǔn)確性(C6)：包括云服務(wù)商交貨的準(zhǔn)時性、質(zhì)量及數(shù)量等方面的準(zhǔn)確性。

(3)工期(C7)：云服務(wù)商的交貨時長。

(4)運輸能力(C8)：云服務(wù)商在交貨或運送到其他服務(wù)商時運輸?shù)陌踩约皽?zhǔn)時性。

1.2 云制造服務(wù)組合模式與計算方式

如圖1所示，云制造服務(wù)組合工作流程的基本模式包括四種：順序、并行、選擇和循環(huán)[11]，其中，CSSt表示第t個子任務(wù)的備選云服務(wù)集，θt表示選擇執(zhí)行第t個子任務(wù)的概率，k為循環(huán)結(jié)構(gòu)的循環(huán)次數(shù)。對于云制造服務(wù)的四種執(zhí)行結(jié)構(gòu)，不同結(jié)構(gòu)下的QoS屬性值計算公式[12～14],如表A1所示。

圖1 云服務(wù)組合結(jié)構(gòu)

本文構(gòu)建的云制造服務(wù)組合優(yōu)化模型如下:

max[C1,C2,C3,C4,C6,C8]T

(1)

min[C,T]T

(2)

s.t.C≤Cmax

(3)

T≤Tmax

(4)

目標(biāo)函數(shù)(1)表示云制造服務(wù)組合的服務(wù)可用性、服務(wù)安全性、服務(wù)信譽度、信息共享能力、交貨準(zhǔn)確性、運輸能力6個指標(biāo)盡可能達到最大化?？紤]到相鄰任務(wù)的各個云制造服務(wù)之間物流成本及時間，總成本(C)應(yīng)包含制造的價格及物流成本，總時間(T)應(yīng)包括制造工期及物流時間，目標(biāo)函數(shù)(2)表示要使總成本及總時間盡可能最小。約束(3)和(4)表示云制造服務(wù)組合的總成本及總時間要低于用戶提出的最大值限制。

2 云制造服務(wù)組合優(yōu)化算法

2.1 nα支配

在目標(biāo)函數(shù)維度較高時，基于帕累托支配的多目標(biāo)進化算法會遇到收斂度顯著下降的問題[15]。由于目標(biāo)維度高，當(dāng)一個個體A在極少維度下稍劣于另一個體B，但在其他維度上都明顯優(yōu)于B，此時理應(yīng)認(rèn)為A優(yōu)于B，但按照帕累托支配的定義，這兩個個體之間互不支配，這就很難找到一個個體支配另一個個體，導(dǎo)致帕累托前沿上的解集過大，使得算法的尋優(yōu)能力大大降低。因此，在本文中將支配方式進行調(diào)整，利用α支配策略對個體進行分層。α支配的本質(zhì)是在目標(biāo)間進行折中，使得當(dāng)個體x在某個維度上稍劣于個體y，但在其他維度上明顯優(yōu)于個體y時，允許x支配y。

以n個目標(biāo)最小化為例，f1(x),f2(x),…,fn(x)為各個目標(biāo)函數(shù)值，其中x∈X，X為優(yōu)化問題的可行域。相對適應(yīng)度定義為:

(5)

其中，x,y∈X。當(dāng)?i,hi(x,y)≤0，且?i使hi(x,y)<0，則稱x支配y[16,17]。當(dāng)αij=0時為帕累托支配。

文獻[17]利用DTLZ函數(shù)測試，驗證了將標(biāo)準(zhǔn)α支配策略應(yīng)用于NSGA-II算法的優(yōu)越性能。但在實際問題中，需要考慮各個目標(biāo)函數(shù)的計算方式及輸入數(shù)據(jù)的量綱區(qū)別，利用標(biāo)準(zhǔn)α支配顯然不合理，因此本文基于標(biāo)準(zhǔn)化思想，提出一種改進的α支配方法，記為nα支配，以去除量綱的影響且不影響最終輸出結(jié)果。本文定義的相對適應(yīng)度為:

(6)

其中，maxfi為第i個目標(biāo)函數(shù)的最大值，minfi為第i個目標(biāo)函數(shù)的最小值，以此來消除量綱，使得算法應(yīng)用于實際問題時更為合理。

2.2 基于nα支配的NSGA-II算法

本文利用基于nα支配的NSGA-II算法對云服務(wù)組合優(yōu)化問題的多目標(biāo)優(yōu)化模型進行求解，具體步驟如下：

Step1構(gòu)建多目標(biāo)優(yōu)化模型，采用整數(shù)編碼的方式，根據(jù)備選云服務(wù)的序號對各個云服務(wù)進行編碼。

Step2初始化種群參數(shù)，設(shè)置種群規(guī)模、進化代數(shù)、交叉概率、變異概率及α的值，產(chǎn)生種群大小為N的初始父代種群Pt，t為種群代數(shù)，對所有個體進行基于nα支配的快速非支配排序及擁擠度計算。

Step3對父代種群Pt進行錦標(biāo)賽選擇。根據(jù)文獻[18]的研究，在錦標(biāo)賽選擇策略中每次選擇種群規(guī)模的60%～80%個體進行比較的效果最好，因此在本文中將每次比較的個體設(shè)置為種群規(guī)模的60%，選擇非支配序小且擁擠度大的個體。由于本文的目的是求解一個組合優(yōu)化實際問題，因此本文選用更加適合整數(shù)編碼的均勻兩點交叉[19]及鄰近變異[20]產(chǎn)生子代，得到種群大小為N的子代種群Qt。

Step4將父代種群與子代種群進行合并。由于交叉及變異有一定概率，有些個體未進行交叉變異，且由于整數(shù)編碼的特點，在交叉變異時可能會產(chǎn)生相同的個體，在多次實驗中發(fā)現(xiàn)合并種群中重復(fù)個體較多，這嚴(yán)重影響種群了多樣性。因此需要在種群合并后剔除重復(fù)的個體，若剔除重復(fù)個體后的種群規(guī)模小于N，則需要生成新的個體進行補位。

Step5對種群進行基于nα支配的快速非支配排序及擁擠度計算，篩選出種群大小為N的下一代父代種群Pt+1。

Step6判斷是否達到進化代數(shù)的最大值，若達到則運行結(jié)束，輸出非支配解集；否則令t=t+1，返回Step 3繼續(xù)進行迭代直至達到進化代數(shù)的最大值。

3 云制造服務(wù)組合優(yōu)選模型

在得到非支配解集后，需要從解集中挑選滿足用戶偏好的最優(yōu)云制造服務(wù)組合。AHP法能夠充分基于用戶的偏好對權(quán)重進行合理分配，通過構(gòu)建層次結(jié)構(gòu)模型，獲取用戶兩兩比較判斷矩陣，對指標(biāo)重要程度按照1到9標(biāo)度法進行比較賦值，最終求解出各指標(biāo)權(quán)重。由于各個優(yōu)化目標(biāo)間不可相互補償，為防止出現(xiàn)云制造服務(wù)組合由于某一目標(biāo)下的值極好而將其他較差目標(biāo)掩蓋的情況，本文選取典型的非補償算法ELECTRE對非支配解集進行優(yōu)選。ELECTRE的原理是通過兩兩比較以獲得決策集的二元關(guān)系，具有多種分支，不同類型的ELECTRE算法適用于解決不同類型的問題[21]。由于本文需要充分考慮用戶的權(quán)重偏好對非支配解集中的服務(wù)組合進行排序擇優(yōu)，因此ELECTREIII算法更加適合本文問題的求解。

綜上所述，本文通過AHP-ELECTRE III模型，基于用戶對各個指標(biāo)的偏好，對得到的非支配解集進行優(yōu)選，具體步驟如下：

Step1基于評價指標(biāo)體系C={C1,C2,…,Cn}，如表A2所示按照1～9標(biāo)度法獲得專家對各個指標(biāo)重要程度的兩兩比較矩陣F=(fij)n×n,i=1,2,…,n;j=1,2,…,n。

Step2計算最大特征根λmax及特征向量W，并進行一致性檢驗。

Step3將解集標(biāo)準(zhǔn)化。

(7)

Step4計算可信度得分[22]。

由于傳統(tǒng)的ELECTRE III的蒸餾過程具有復(fù)雜性，Wang[23]引入了一致可信度、非一致可信度和凈可信度的概念，簡化了方案的排序過程。

(8)

(9)

(10)

Step6根據(jù)Φi按照降序?qū)Ψ桨缸龀雠判?，選出最優(yōu)云服務(wù)組合方案。

4 實驗與結(jié)果分析

4.1 算例描述

本節(jié)以一個電機制造任務(wù)為例，驗證云制造服務(wù)組合優(yōu)化模型的可行性。由于尚未有公開的數(shù)據(jù)集，本文采用在合理范圍內(nèi)隨機生成的模擬數(shù)據(jù)驗證模型的可行性和優(yōu)越性。如圖2所示，云制造平臺將電機制造任務(wù)分解為六個子任務(wù)，構(gòu)成子任務(wù)集STS={ST1,ST2,ST3,ST4,ST5,ST6}。同時企業(yè)要求總成本不超過850，總時間不超過90個單位時間。云制造平臺為每個子任務(wù)匹配到7個符合制造要求的云服務(wù)，各個云服務(wù)的指標(biāo)評價值及云服務(wù)間的物流成本、時間如表A3～表A8所示，其中子任務(wù)1不包括C8評價值。

圖2 電機制造工藝流程圖

4.2 結(jié)果分析

4.2.1 可行性分析

根據(jù)整體任務(wù)結(jié)構(gòu)及各個QoS值計算方式，算例構(gòu)建多目標(biāo)優(yōu)化模型。子任務(wù)1與子任務(wù)2、3、4之間不涉及物流運輸，其中，lc表示物流成本，例如lc35表示子任務(wù)3與子任務(wù)5相應(yīng)云服務(wù)之間的物流成本，lc6end表示子任務(wù)6與用戶之間的物流成本。lt表示物流時間，例如lt35示子任務(wù)3與子任務(wù)5相應(yīng)云服務(wù)之間的物流時間，lt6end表示子任務(wù)6與用戶之間的物流成本。

本文在Matlab 2017b環(huán)境中進行多目標(biāo)優(yōu)化模型求解，種群規(guī)模為150，進化代數(shù)200，交叉概率0.95，變異概率0.05，α=0.3，生成初始種群。按照2.2節(jié)所述步驟繼續(xù)進行，直到輸出非支配解集。輸出的非支配解集及目標(biāo)函數(shù)值如表1所示。其中服務(wù)組合中的數(shù)字表示對應(yīng)子任務(wù)下備選云服務(wù)的編號，Ai為組合序號。

表1 非支配解集

基于得到的非支配解集，進行云服務(wù)組合優(yōu)選，按照第3節(jié)所述流程，首先獲得用戶的兩兩比較矩陣，如表A9所示。

計算各個指標(biāo)的權(quán)重并檢驗一致性，得到個指標(biāo)權(quán)重如表2所示。一致性比率CR=0.0556<0.1，一致性檢驗通過。

表2 QoS指標(biāo)權(quán)重

對非支配解集進行標(biāo)準(zhǔn)化，并取α=0.1，β=4，γ=0.6，計算出凈可信度Φi，根據(jù)Φi按照降序?qū)Ψ桨缸鞒雠判?，結(jié)果如表3所示。

表3 備選云服務(wù)組合排序結(jié)果

4.2.2 對比分析

為了驗證本文提出的基于nα支配的NSGA-II優(yōu)化算法在高維多目標(biāo)優(yōu)化情境下的優(yōu)越性，本節(jié)對提出算法與標(biāo)準(zhǔn)NSGA-II算法、r-NSGA-II算法[24]和基于模糊支配的NSGA-II算法[25](以下簡記為f-NSGA-II)進行對比實驗。在Matlab 2017b中，分別設(shè)置種群規(guī)模(N)為50、100、150、200，進化代數(shù)200，交叉概率0.95，變異概率0.05。在nα-NSGA-II算法中，取α=0.3；在r-NSGA-II算法中，參考點取為各個目標(biāo)可以達到的最優(yōu)值，即(0.932，0.98，0.987，0.938，698，0.923，65，0.939)，各個目標(biāo)權(quán)重均取0.125，閾值取0.3；在f-NSGA-II算法中，閾值取0.3。

由于進化算法每次輸出結(jié)果有差異，因此本文在每個種群規(guī)模下采用四種算法分別獨立進行10次實驗，取非支配解集中各個優(yōu)化目標(biāo)的平均值，如表4所示，得到的平均最優(yōu)解集的大小如圖3所示。

表4 不同種群規(guī)模下四種算法目標(biāo)函數(shù)值對比

圖3 四種算法最優(yōu)解集個體數(shù)量對比

實驗結(jié)果表明，基于nα支配的NSGA-II算法通過進化篩選出了整體更為優(yōu)質(zhì)的解集，在各個種群規(guī)模中，幾乎所有目標(biāo)函數(shù)平均值均優(yōu)于或約等于其他算法。與其他算法相比，基于nα支配的NSGA-II算法非支配解集個體數(shù)目隨種群規(guī)模擴大上漲不大，解集明顯較小，大大減小了后續(xù)云服務(wù)組合優(yōu)選的計算量。這是由于標(biāo)準(zhǔn)NSGA-II算法基于帕累托支配，在高維度情況下很難確定支配關(guān)系，從而導(dǎo)致解集占據(jù)了整個種群，進而使得各個目標(biāo)下的平均函數(shù)值更差；r-NSGA-II算法非常依賴于參考點位置，解集收斂在參考點附近從而減小了種群多樣性，在一定程度上影響了解集的目標(biāo)函數(shù)值，隨著迭代次數(shù)增加也使得解集中個體數(shù)量隨之增加；f-NSGA-II算法的解集規(guī)模依賴于閾值的取值，閾值越大解集規(guī)模越小，但也會導(dǎo)致大量個體被分到最后一個層級無法區(qū)分；而基于nα支配的NSGA-II算法在高維多目標(biāo)優(yōu)化中能夠根據(jù)α的取值在各個目標(biāo)間折中，對種群進行更為有效分層，且不會向局部收斂，保證了種群多樣性，得到更為優(yōu)質(zhì)的解集。

5 結(jié)論

云制造的發(fā)展使得云制造任務(wù)日趨復(fù)雜，進而要求從更多維度對服務(wù)組合進行篩選。本文針對云制造線上交易、線下制造的特點，構(gòu)建了包含線上線下兩部分的新評價指標(biāo)體系。此外，本文基于新評價指標(biāo)體系構(gòu)建了高維多目標(biāo)優(yōu)化模型，并對多目標(biāo)優(yōu)化算法NSGA-II進行改進，提出了基于nα支配的NSGA-II算法。最后，本文通過一個電機制造的算例驗證了本文提出模型的可行性，并通過與其他改進方法的對比實驗證明了本文提出算法的優(yōu)越性。

在實際生產(chǎn)中，可能會存在目標(biāo)間相互關(guān)聯(lián)的情況，因此需要進一步研究目標(biāo)間相互關(guān)聯(lián)時的多目標(biāo)組合優(yōu)化問題。同時，隨著云制造平臺的規(guī)模擴大，需要求解的組合規(guī)模及目標(biāo)維度可能更大，因此在未來的研究中應(yīng)考慮多種算法融合以提高算法性能。