邵一凡, 禹春霞, 禹嘉誠(chéng)
(1.中國(guó)石油大學(xué) (北京)經(jīng)濟(jì)管理學(xué)院,北京 102249; 2.廈門(mén)大學(xué) 管理學(xué)院,福建 廈門(mén) 361005; 3.北京體育大學(xué)體育商學(xué)院,北京 100084)
云制造的概念最早由李伯虎院士提出[1],是一種面向服務(wù)的網(wǎng)絡(luò)化制造新模式,其以客戶為核心、以知識(shí)為支撐,構(gòu)建了一個(gè)虛擬化、分布式、按需分配的資源共享平臺(tái)[2]。在云制造模式下,分布式制造資源被封裝到不同的云服務(wù)中,形成服務(wù)池,由云制造平臺(tái)按需調(diào)配,極大地提高了制造資源的利用效率及社會(huì)生產(chǎn)力,為實(shí)現(xiàn)我國(guó)制造強(qiáng)國(guó)的目標(biāo)提供了有力支撐。近年來(lái),隨著制造任務(wù)日益復(fù)雜,單一的云制造服務(wù)已無(wú)法滿足生產(chǎn)需求,云制造平臺(tái)需要將復(fù)雜制造任務(wù)分解為若干子任務(wù),為各個(gè)子任務(wù)匹配合適的云服務(wù),形成云服務(wù)組合,并在眾多服務(wù)組合中選擇最優(yōu)組合供用戶使用,這個(gè)過(guò)程稱(chēng)為云服務(wù)組合優(yōu)化,是云制造平臺(tái)亟需關(guān)注的問(wèn)題。
在云制造平臺(tái)中,針對(duì)同一個(gè)子任務(wù)有大量功能屬性相同但非功能屬性不同的云服務(wù),云服務(wù)的非功能性屬性通常用QoS(服務(wù)質(zhì)量)來(lái)描述[3]。在實(shí)際應(yīng)用中,云制造服務(wù)的QoS指標(biāo)眾多,因此云制造服務(wù)組合優(yōu)化問(wèn)題應(yīng)被看作高維多目標(biāo)優(yōu)化問(wèn)題。當(dāng)前關(guān)于云服務(wù)組合優(yōu)化問(wèn)題的求解方式大致分為以下三種:第一種是將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題進(jìn)行求解[4~6],第二種是直接利用多目標(biāo)優(yōu)化算法進(jìn)行求解[7~9],第三種是將所有組合枚舉出來(lái)利用多屬性評(píng)價(jià)方法選擇最優(yōu)組合[10]。在實(shí)際應(yīng)用中,QoS指標(biāo)間往往是相互沖突的,且轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解時(shí)極容易陷入局部最優(yōu)解,因此第一種方式可能會(huì)造成結(jié)果不準(zhǔn)確,且非常依賴各指標(biāo)權(quán)重;第三種方式在子任務(wù)及備選服務(wù)較多時(shí)會(huì)造成運(yùn)算量呈指數(shù)型增長(zhǎng),不適用于大規(guī)模的云服務(wù)組合優(yōu)化;第二種方式相對(duì)更加合理。但是當(dāng)前采用第二種方式的多目標(biāo)優(yōu)化模型的目標(biāo)函數(shù)的維度往往比較低,而云服務(wù)組合的評(píng)價(jià)指標(biāo)眾多,僅靠少數(shù)目標(biāo)函數(shù)進(jìn)行組合優(yōu)化會(huì)相對(duì)片面。因此,本文提出的云制造服務(wù)組合優(yōu)化問(wèn)題的求解算法具有以下創(chuàng)新點(diǎn):
(1)本文將云制造服務(wù)組合優(yōu)化轉(zhuǎn)化為高維多目標(biāo)優(yōu)化問(wèn)題,從線上、線下兩方面構(gòu)建QoS評(píng)價(jià)體系。
(2)對(duì)多目標(biāo)優(yōu)化算法NSGA-II進(jìn)行改進(jìn),提出一種基于nα支配的NSGA-II算法,使算法能夠更好地處理高維多目標(biāo)優(yōu)化問(wèn)題并消除量綱影響。
云制造服務(wù)包括線上交易與線下生產(chǎn)兩部分,相對(duì)于普通制造服務(wù)來(lái)說(shuō),云制造服務(wù)需要更多地考慮網(wǎng)絡(luò)性能以滿足線上交易的需求;相對(duì)于基于web的云服務(wù)來(lái)說(shuō),云制造服務(wù)需要更側(cè)重于線下生產(chǎn)制造的能力。因此,本文將云制造服務(wù)的評(píng)價(jià)體系分為線上和線下兩部分,構(gòu)建新的基于云制造的云服務(wù)QoS評(píng)價(jià)體系。
1.1.1 線上指標(biāo)
云制造服務(wù)的線上部分要求其具備良好的網(wǎng)絡(luò)服務(wù)性能,這一部分與web云服務(wù)非常相似,本文主要基于web云服務(wù)的QoS常用評(píng)價(jià)指標(biāo),從云制造的網(wǎng)絡(luò)能力及線上服務(wù)能力兩方面進(jìn)行考慮,篩選出對(duì)云服務(wù)影響較大的四個(gè)指標(biāo):
(1)服務(wù)可用性(C1):云服務(wù)在特定時(shí)間內(nèi)能夠被成功訪問(wèn)的可能性。
(2)服務(wù)安全性(C2):云服務(wù)商為防止信息泄露,對(duì)用戶數(shù)據(jù)傳輸進(jìn)行保護(hù)及加密的能力。
(3)服務(wù)信譽(yù)度(C3):用戶在制造完成后對(duì)云服務(wù)商提供信息的準(zhǔn)確性及制造過(guò)程誠(chéng)信度的整體評(píng)價(jià)。
(4)信息共享能力(C4):云服務(wù)商將其在平臺(tái)中的制造及服務(wù)信息共享給其他共同協(xié)作服務(wù)商的準(zhǔn)確性與及時(shí)性。
1.1.2 線下指標(biāo)
云制造服務(wù)的線下制造部分要求其確保服務(wù)的價(jià)格及工期合理,且能夠準(zhǔn)確交貨。對(duì)于復(fù)雜制造任務(wù)來(lái)說(shuō),需要各個(gè)服務(wù)間協(xié)同配合,因此物流運(yùn)輸能力對(duì)各個(gè)云服務(wù)也非常重要。本文選取的主要線下指標(biāo)包括以下四個(gè):
(1)價(jià)格(C5):用戶獲取制造服務(wù)所需的成本,包括制造價(jià)格、服務(wù)價(jià)格等。
(2)交貨準(zhǔn)確性(C6):包括云服務(wù)商交貨的準(zhǔn)時(shí)性、質(zhì)量及數(shù)量等方面的準(zhǔn)確性。
(3)工期(C7):云服務(wù)商的交貨時(shí)長(zhǎng)。
(4)運(yùn)輸能力(C8):云服務(wù)商在交貨或運(yùn)送到其他服務(wù)商時(shí)運(yùn)輸?shù)陌踩约皽?zhǔn)時(shí)性。
如圖1所示,云制造服務(wù)組合工作流程的基本模式包括四種:順序、并行、選擇和循環(huán)[11],其中,CSSt表示第t個(gè)子任務(wù)的備選云服務(wù)集,θt表示選擇執(zhí)行第t個(gè)子任務(wù)的概率,k為循環(huán)結(jié)構(gòu)的循環(huán)次數(shù)。對(duì)于云制造服務(wù)的四種執(zhí)行結(jié)構(gòu),不同結(jié)構(gòu)下的QoS屬性值計(jì)算公式[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ù)信譽(yù)度、信息共享能力、交貨準(zhǔn)確性、運(yùn)輸能力6個(gè)指標(biāo)盡可能達(dá)到最大化。考慮到相鄰任務(wù)的各個(gè)云制造服務(wù)之間物流成本及時(shí)間,總成本(C)應(yīng)包含制造的價(jià)格及物流成本,總時(shí)間(T)應(yīng)包括制造工期及物流時(shí)間,目標(biāo)函數(shù)(2)表示要使總成本及總時(shí)間盡可能最小。約束(3)和(4)表示云制造服務(wù)組合的總成本及總時(shí)間要低于用戶提出的最大值限制。
在目標(biāo)函數(shù)維度較高時(shí),基于帕累托支配的多目標(biāo)進(jìn)化算法會(huì)遇到收斂度顯著下降的問(wèn)題[15]。由于目標(biāo)維度高,當(dāng)一個(gè)個(gè)體A在極少維度下稍劣于另一個(gè)體B,但在其他維度上都明顯優(yōu)于B,此時(shí)理應(yīng)認(rèn)為A優(yōu)于B,但按照帕累托支配的定義,這兩個(gè)個(gè)體之間互不支配,這就很難找到一個(gè)個(gè)體支配另一個(gè)個(gè)體,導(dǎo)致帕累托前沿上的解集過(guò)大,使得算法的尋優(yōu)能力大大降低。因此,在本文中將支配方式進(jìn)行調(diào)整,利用α支配策略對(duì)個(gè)體進(jìn)行分層。α支配的本質(zhì)是在目標(biāo)間進(jìn)行折中,使得當(dāng)個(gè)體x在某個(gè)維度上稍劣于個(gè)體y,但在其他維度上明顯優(yōu)于個(gè)體y時(shí),允許x支配y。
以n個(gè)目標(biāo)最小化為例,f1(x),f2(x),…,fn(x)為各個(gè)目標(biāo)函數(shù)值,其中x∈X,X為優(yōu)化問(wèn)題的可行域。相對(duì)適應(yīng)度定義為:
(5)
其中,x,y∈X。當(dāng)?i,hi(x,y)≤0,且?i使hi(x,y)<0,則稱(chēng)x支配y[16,17]。當(dāng)αij=0時(shí)為帕累托支配。
文獻(xiàn)[17]利用DTLZ函數(shù)測(cè)試,驗(yàn)證了將標(biāo)準(zhǔn)α支配策略應(yīng)用于NSGA-II算法的優(yōu)越性能。但在實(shí)際問(wèn)題中,需要考慮各個(gè)目標(biāo)函數(shù)的計(jì)算方式及輸入數(shù)據(jù)的量綱區(qū)別,利用標(biāo)準(zhǔn)α支配顯然不合理,因此本文基于標(biāo)準(zhǔn)化思想,提出一種改進(jìn)的α支配方法,記為nα支配,以去除量綱的影響且不影響最終輸出結(jié)果。本文定義的相對(duì)適應(yīng)度為:
(6)
其中,maxfi為第i個(gè)目標(biāo)函數(shù)的最大值,minfi為第i個(gè)目標(biāo)函數(shù)的最小值,以此來(lái)消除量綱,使得算法應(yīng)用于實(shí)際問(wèn)題時(shí)更為合理。
本文利用基于nα支配的NSGA-II算法對(duì)云服務(wù)組合優(yōu)化問(wèn)題的多目標(biāo)優(yōu)化模型進(jìn)行求解,具體步驟如下:
Step1構(gòu)建多目標(biāo)優(yōu)化模型,采用整數(shù)編碼的方式,根據(jù)備選云服務(wù)的序號(hào)對(duì)各個(gè)云服務(wù)進(jìn)行編碼。
Step2初始化種群參數(shù),設(shè)置種群規(guī)模、進(jìn)化代數(shù)、交叉概率、變異概率及α的值,產(chǎn)生種群大小為N的初始父代種群Pt,t為種群代數(shù),對(duì)所有個(gè)體進(jìn)行基于nα支配的快速非支配排序及擁擠度計(jì)算。
Step3對(duì)父代種群Pt進(jìn)行錦標(biāo)賽選擇。根據(jù)文獻(xiàn)[18]的研究,在錦標(biāo)賽選擇策略中每次選擇種群規(guī)模的60%~80%個(gè)體進(jìn)行比較的效果最好,因此在本文中將每次比較的個(gè)體設(shè)置為種群規(guī)模的60%,選擇非支配序小且擁擠度大的個(gè)體。由于本文的目的是求解一個(gè)組合優(yōu)化實(shí)際問(wèn)題,因此本文選用更加適合整數(shù)編碼的均勻兩點(diǎn)交叉[19]及鄰近變異[20]產(chǎn)生子代,得到種群大小為N的子代種群Qt。
Step4將父代種群與子代種群進(jìn)行合并。由于交叉及變異有一定概率,有些個(gè)體未進(jìn)行交叉變異,且由于整數(shù)編碼的特點(diǎn),在交叉變異時(shí)可能會(huì)產(chǎn)生相同的個(gè)體,在多次實(shí)驗(yàn)中發(fā)現(xiàn)合并種群中重復(fù)個(gè)體較多,這嚴(yán)重影響種群了多樣性。因此需要在種群合并后剔除重復(fù)的個(gè)體,若剔除重復(fù)個(gè)體后的種群規(guī)模小于N,則需要生成新的個(gè)體進(jìn)行補(bǔ)位。
Step5對(duì)種群進(jìn)行基于nα支配的快速非支配排序及擁擠度計(jì)算,篩選出種群大小為N的下一代父代種群Pt+1。
Step6判斷是否達(dá)到進(jìn)化代數(shù)的最大值,若達(dá)到則運(yùn)行結(jié)束,輸出非支配解集;否則令t=t+1,返回Step 3繼續(xù)進(jìn)行迭代直至達(dá)到進(jìn)化代數(shù)的最大值。
在得到非支配解集后,需要從解集中挑選滿足用戶偏好的最優(yōu)云制造服務(wù)組合。AHP法能夠充分基于用戶的偏好對(duì)權(quán)重進(jìn)行合理分配,通過(guò)構(gòu)建層次結(jié)構(gòu)模型,獲取用戶兩兩比較判斷矩陣,對(duì)指標(biāo)重要程度按照1到9標(biāo)度法進(jìn)行比較賦值,最終求解出各指標(biāo)權(quán)重。由于各個(gè)優(yōu)化目標(biāo)間不可相互補(bǔ)償,為防止出現(xiàn)云制造服務(wù)組合由于某一目標(biāo)下的值極好而將其他較差目標(biāo)掩蓋的情況,本文選取典型的非補(bǔ)償算法ELECTRE對(duì)非支配解集進(jìn)行優(yōu)選。ELECTRE的原理是通過(guò)兩兩比較以獲得決策集的二元關(guān)系,具有多種分支,不同類(lèi)型的ELECTRE算法適用于解決不同類(lèi)型的問(wèn)題[21]。由于本文需要充分考慮用戶的權(quán)重偏好對(duì)非支配解集中的服務(wù)組合進(jìn)行排序擇優(yōu),因此ELECTREIII算法更加適合本文問(wèn)題的求解。
綜上所述,本文通過(guò)AHP-ELECTRE III模型,基于用戶對(duì)各個(gè)指標(biāo)的偏好,對(duì)得到的非支配解集進(jìn)行優(yōu)選,具體步驟如下:
Step1基于評(píng)價(jià)指標(biāo)體系C={C1,C2,…,Cn},如表A2所示按照1~9標(biāo)度法獲得專(zhuān)家對(duì)各個(gè)指標(biāo)重要程度的兩兩比較矩陣F=(fij)n×n,i=1,2,…,n;j=1,2,…,n。
Step2計(jì)算最大特征根λmax及特征向量W,并進(jìn)行一致性檢驗(yàn)。
Step3將解集標(biāo)準(zhǔn)化。
(7)
Step4計(jì)算可信度得分[22]。
由于傳統(tǒng)的ELECTRE III的蒸餾過(guò)程具有復(fù)雜性,Wang[23]引入了一致可信度、非一致可信度和凈可信度的概念,簡(jiǎn)化了方案的排序過(guò)程。
(8)
(9)
(10)
Step6根據(jù)Φi按照降序?qū)Ψ桨缸龀雠判?,選出最優(yōu)云服務(wù)組合方案。
本節(jié)以一個(gè)電機(jī)制造任務(wù)為例,驗(yàn)證云制造服務(wù)組合優(yōu)化模型的可行性。由于尚未有公開(kāi)的數(shù)據(jù)集,本文采用在合理范圍內(nèi)隨機(jī)生成的模擬數(shù)據(jù)驗(yàn)證模型的可行性和優(yōu)越性。如圖2所示,云制造平臺(tái)將電機(jī)制造任務(wù)分解為六個(gè)子任務(wù),構(gòu)成子任務(wù)集STS={ST1,ST2,ST3,ST4,ST5,ST6}。同時(shí)企業(yè)要求總成本不超過(guò)850,總時(shí)間不超過(guò)90個(gè)單位時(shí)間。云制造平臺(tái)為每個(gè)子任務(wù)匹配到7個(gè)符合制造要求的云服務(wù),各個(gè)云服務(wù)的指標(biāo)評(píng)價(jià)值及云服務(wù)間的物流成本、時(shí)間如表A3~表A8所示,其中子任務(wù)1不包括C8評(píng)價(jià)值。
圖2 電機(jī)制造工藝流程圖
4.2.1 可行性分析
根據(jù)整體任務(wù)結(jié)構(gòu)及各個(gè)QoS值計(jì)算方式,算例構(gòu)建多目標(biāo)優(yōu)化模型。子任務(wù)1與子任務(wù)2、3、4之間不涉及物流運(yùn)輸,其中,lc表示物流成本,例如lc35表示子任務(wù)3與子任務(wù)5相應(yīng)云服務(wù)之間的物流成本,lc6end表示子任務(wù)6與用戶之間的物流成本。lt表示物流時(shí)間,例如lt35示子任務(wù)3與子任務(wù)5相應(yīng)云服務(wù)之間的物流時(shí)間,lt6end表示子任務(wù)6與用戶之間的物流成本。
本文在Matlab 2017b環(huán)境中進(jìn)行多目標(biāo)優(yōu)化模型求解,種群規(guī)模為150,進(jìn)化代數(shù)200,交叉概率0.95,變異概率0.05,α=0.3,生成初始種群。按照2.2節(jié)所述步驟繼續(xù)進(jìn)行,直到輸出非支配解集。輸出的非支配解集及目標(biāo)函數(shù)值如表1所示。其中服務(wù)組合中的數(shù)字表示對(duì)應(yīng)子任務(wù)下備選云服務(wù)的編號(hào),Ai為組合序號(hào)。
表1 非支配解集
基于得到的非支配解集,進(jìn)行云服務(wù)組合優(yōu)選,按照第3節(jié)所述流程,首先獲得用戶的兩兩比較矩陣,如表A9所示。
計(jì)算各個(gè)指標(biāo)的權(quán)重并檢驗(yàn)一致性,得到個(gè)指標(biāo)權(quán)重如表2所示。一致性比率CR=0.0556<0.1,一致性檢驗(yàn)通過(guò)。
表2 QoS指標(biāo)權(quán)重
對(duì)非支配解集進(jìn)行標(biāo)準(zhǔn)化,并取α=0.1,β=4,γ=0.6,計(jì)算出凈可信度Φi,根據(jù)Φi按照降序?qū)Ψ桨缸鞒雠判?,結(jié)果如表3所示。
表3 備選云服務(wù)組合排序結(jié)果
4.2.2 對(duì)比分析
為了驗(yàn)證本文提出的基于nα支配的NSGA-II優(yōu)化算法在高維多目標(biāo)優(yōu)化情境下的優(yōu)越性,本節(jié)對(duì)提出算法與標(biāo)準(zhǔn)NSGA-II算法、r-NSGA-II算法[24]和基于模糊支配的NSGA-II算法[25](以下簡(jiǎn)記為f-NSGA-II)進(jìn)行對(duì)比實(shí)驗(yàn)。在Matlab 2017b中,分別設(shè)置種群規(guī)模(N)為50、100、150、200,進(jìn)化代數(shù)200,交叉概率0.95,變異概率0.05。在nα-NSGA-II算法中,取α=0.3;在r-NSGA-II算法中,參考點(diǎn)取為各個(gè)目標(biāo)可以達(dá)到的最優(yōu)值,即(0.932,0.98,0.987,0.938,698,0.923,65,0.939),各個(gè)目標(biāo)權(quán)重均取0.125,閾值取0.3;在f-NSGA-II算法中,閾值取0.3。
由于進(jìn)化算法每次輸出結(jié)果有差異,因此本文在每個(gè)種群規(guī)模下采用四種算法分別獨(dú)立進(jìn)行10次實(shí)驗(yàn),取非支配解集中各個(gè)優(yōu)化目標(biāo)的平均值,如表4所示,得到的平均最優(yōu)解集的大小如圖3所示。
表4 不同種群規(guī)模下四種算法目標(biāo)函數(shù)值對(duì)比
圖3 四種算法最優(yōu)解集個(gè)體數(shù)量對(duì)比
實(shí)驗(yàn)結(jié)果表明,基于nα支配的NSGA-II算法通過(guò)進(jìn)化篩選出了整體更為優(yōu)質(zhì)的解集,在各個(gè)種群規(guī)模中,幾乎所有目標(biāo)函數(shù)平均值均優(yōu)于或約等于其他算法。與其他算法相比,基于nα支配的NSGA-II算法非支配解集個(gè)體數(shù)目隨種群規(guī)模擴(kuò)大上漲不大,解集明顯較小,大大減小了后續(xù)云服務(wù)組合優(yōu)選的計(jì)算量。這是由于標(biāo)準(zhǔn)NSGA-II算法基于帕累托支配,在高維度情況下很難確定支配關(guān)系,從而導(dǎo)致解集占據(jù)了整個(gè)種群,進(jìn)而使得各個(gè)目標(biāo)下的平均函數(shù)值更差;r-NSGA-II算法非常依賴于參考點(diǎn)位置,解集收斂在參考點(diǎn)附近從而減小了種群多樣性,在一定程度上影響了解集的目標(biāo)函數(shù)值,隨著迭代次數(shù)增加也使得解集中個(gè)體數(shù)量隨之增加;f-NSGA-II算法的解集規(guī)模依賴于閾值的取值,閾值越大解集規(guī)模越小,但也會(huì)導(dǎo)致大量個(gè)體被分到最后一個(gè)層級(jí)無(wú)法區(qū)分;而基于nα支配的NSGA-II算法在高維多目標(biāo)優(yōu)化中能夠根據(jù)α的取值在各個(gè)目標(biāo)間折中,對(duì)種群進(jìn)行更為有效分層,且不會(huì)向局部收斂,保證了種群多樣性,得到更為優(yōu)質(zhì)的解集。
云制造的發(fā)展使得云制造任務(wù)日趨復(fù)雜,進(jìn)而要求從更多維度對(duì)服務(wù)組合進(jìn)行篩選。本文針對(duì)云制造線上交易、線下制造的特點(diǎn),構(gòu)建了包含線上線下兩部分的新評(píng)價(jià)指標(biāo)體系。此外,本文基于新評(píng)價(jià)指標(biāo)體系構(gòu)建了高維多目標(biāo)優(yōu)化模型,并對(duì)多目標(biāo)優(yōu)化算法NSGA-II進(jìn)行改進(jìn),提出了基于nα支配的NSGA-II算法。最后,本文通過(guò)一個(gè)電機(jī)制造的算例驗(yàn)證了本文提出模型的可行性,并通過(guò)與其他改進(jìn)方法的對(duì)比實(shí)驗(yàn)證明了本文提出算法的優(yōu)越性。
在實(shí)際生產(chǎn)中,可能會(huì)存在目標(biāo)間相互關(guān)聯(lián)的情況,因此需要進(jìn)一步研究目標(biāo)間相互關(guān)聯(lián)時(shí)的多目標(biāo)組合優(yōu)化問(wèn)題。同時(shí),隨著云制造平臺(tái)的規(guī)模擴(kuò)大,需要求解的組合規(guī)模及目標(biāo)維度可能更大,因此在未來(lái)的研究中應(yīng)考慮多種算法融合以提高算法性能。