汪正山,楊志學(xué),湯 勇,許 斌
(1.南京郵電大學(xué) 自動(dòng)化學(xué)院,江蘇 南京 210023;2.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院,江蘇 南京 210023)
目前,制造業(yè)作為工業(yè)生產(chǎn)的基本組成部分,是現(xiàn)代工業(yè)不可缺少的一環(huán)。隨著社會(huì)分工細(xì)化,社會(huì)競爭逐漸激烈,使得單一的制造企業(yè)很難高效完成復(fù)雜的制造任務(wù)和滿足市場多樣化需求[1]。越來越多的中小型制造企業(yè)通過共享制造資源來提高市場競爭力。在這一背景下,云制造模式作為一種新型的智能化網(wǎng)絡(luò)制造模式被適時(shí)提出并得到廣泛關(guān)注[2]。云制造是一種結(jié)合云計(jì)算技術(shù)、物聯(lián)網(wǎng)技術(shù)和現(xiàn)代信息制造技術(shù)的新型制造模式。它實(shí)現(xiàn)了各種制造資源和制造能力的虛擬化和服務(wù)化,并實(shí)現(xiàn)管理和操作的智能化,達(dá)到制造業(yè)各種資源的優(yōu)化配置和應(yīng)用,為制造的整個(gè)生命周期提供最佳的配置和應(yīng)用[3-4]。
實(shí)現(xiàn)云制造的關(guān)鍵技術(shù)在于云制造資源的優(yōu)化配置。即通過在每個(gè)類別下聚合候選服務(wù),在給定服務(wù)和候選服務(wù)類型中選取合適的服務(wù)以實(shí)現(xiàn)QoS的最大化。例如,文獻(xiàn)[5]提出了基于知識(shí)差異計(jì)算的云計(jì)算服務(wù)組合,文獻(xiàn)[6]提出了QoS感知的多粒度服務(wù)組合,以及文獻(xiàn)[7]提出了基于社交網(wǎng)絡(luò)的動(dòng)態(tài)QoS感知物流服務(wù)組合算法。對(duì)于制造資源的評(píng)價(jià)問題,文獻(xiàn)[8]構(gòu)建了制造資源服務(wù)評(píng)價(jià)指標(biāo)體系。然而在實(shí)際情況中,由于服務(wù)信息具有不確定性,不合適的服務(wù)組合難以滿足客戶需求。因此,目前的服務(wù)組合質(zhì)量評(píng)估體系還需進(jìn)一步優(yōu)化升級(jí)。除優(yōu)化配置外,隨著經(jīng)濟(jì)的快速發(fā)展,制造業(yè)造成的環(huán)境污染日益嚴(yán)重,國家為了緩解這種現(xiàn)象,在重大規(guī)劃《中國制造2025》中提出了實(shí)施綠色制造工程,加快構(gòu)建綠色制造體系,發(fā)揮綠色制造先進(jìn)典型的示范帶動(dòng)作用,因此對(duì)服務(wù)的環(huán)保指標(biāo)展開研究成為一個(gè)很有價(jià)值的問題。
針對(duì)制造業(yè)普遍存在的環(huán)境污染問題并結(jié)合《中國制造2025》對(duì)綠色制造工程的迫切需求,建立了一個(gè)針對(duì)企業(yè)的環(huán)保信譽(yù)評(píng)估模型。用參與服務(wù)的企業(yè)環(huán)保信譽(yù)的代數(shù)和表示服務(wù)的環(huán)保值,隨后將環(huán)保信譽(yù)值納入QoS評(píng)估模型中。使用SGWO求解基于環(huán)保信譽(yù)的服務(wù)組合優(yōu)化問題,達(dá)到既滿足服務(wù)需求,又使得社會(huì)資源消耗最低化的Pareto有效配置的目的[9]。
文中貢獻(xiàn)主要有兩點(diǎn):
(1)為了鼓勵(lì)企業(yè)進(jìn)行產(chǎn)業(yè)升級(jí),提出智能云制造環(huán)境下企業(yè)的環(huán)保信譽(yù)評(píng)價(jià)模型。并將環(huán)保信譽(yù)指標(biāo)納入QoS模型,在生產(chǎn)中優(yōu)先選擇環(huán)保信譽(yù)高的企業(yè),增強(qiáng)環(huán)保企業(yè)的競爭力,鼓勵(lì)企業(yè)優(yōu)化產(chǎn)業(yè),這可以緩解制造業(yè)對(duì)環(huán)境造成的問題。
(2)提出一種SGWO算法,在GWO中引入擾動(dòng)變異因子、收斂因子和動(dòng)態(tài)權(quán)重策略,能有效避免陷入局部最優(yōu)且增強(qiáng)收斂速度。
可持續(xù)發(fā)展一直是當(dāng)今發(fā)展的主題,服務(wù)的環(huán)保度問題也是云制造服務(wù)組合問題的一個(gè)重點(diǎn)。在云制造場景下,每個(gè)服務(wù)被拆分為幾個(gè)子服務(wù),每個(gè)子服務(wù)由相應(yīng)的備選企業(yè)完成。文中用參與服務(wù)企業(yè)環(huán)保信譽(yù)的代數(shù)和來表示服務(wù)的環(huán)保值。針對(duì)企業(yè)環(huán)保信譽(yù)評(píng)估,提出了一個(gè)企業(yè)環(huán)保信譽(yù)評(píng)估模型,并將其融入到QoS評(píng)估模型中。圖1說明了企業(yè)環(huán)保信譽(yù)評(píng)估模型在整體結(jié)構(gòu)中的作用。
圖1 云制造整體示意
1.1.1 GC評(píng)級(jí)標(biāo)準(zhǔn)
該模型將企業(yè)的環(huán)保信譽(yù)(Green credit,GC)分為四個(gè)等級(jí),滿分為100分。A,B,C,D型企業(yè)分別對(duì)應(yīng)優(yōu)秀,良好,一般,惡劣。令企業(yè)總得分為Aall,評(píng)分和等級(jí)關(guān)系如下:
根據(jù)企業(yè)具體情況,文中確定的評(píng)分標(biāo)準(zhǔn)可適當(dāng)浮動(dòng),但都應(yīng)著重考核企業(yè)的主要環(huán)境指標(biāo),并以此確定企業(yè)的環(huán)保信譽(yù)等級(jí)。評(píng)分標(biāo)準(zhǔn)分為四塊,污染物排放得分A1,環(huán)境違法行為A2,繳納排污費(fèi)A3,信訪投訴A4??偟梅諥all=A1+A2+A3+A4
綠色環(huán)保度評(píng)估模型如圖2所示。
1.1.2 評(píng)估流程
在Oracle上開發(fā)數(shù)據(jù)庫管理系統(tǒng),對(duì)企業(yè)的環(huán)保信息進(jìn)行采集、錄入、儲(chǔ)存、評(píng)估、共享。企業(yè)每月定期進(jìn)行排污數(shù)據(jù)采集,環(huán)保部門不定期抽查,得到企業(yè)真實(shí)可信的環(huán)保數(shù)據(jù)。由數(shù)據(jù)庫管理員定期錄入從環(huán)保部門獲取的企業(yè)綠色評(píng)估數(shù)據(jù),在數(shù)據(jù)庫上進(jìn)行儲(chǔ)存。通過GC評(píng)級(jí)標(biāo)準(zhǔn),對(duì)企業(yè)環(huán)保度進(jìn)行評(píng)價(jià),實(shí)現(xiàn)了對(duì)企業(yè)環(huán)保信譽(yù)度的評(píng)估。由于Oracle的數(shù)據(jù)共享特性,可以實(shí)現(xiàn)企業(yè)環(huán)保信譽(yù)度與云制造平臺(tái)的結(jié)合,將服務(wù)環(huán)保信譽(yù)度指標(biāo)納入QoS評(píng)估模型。
圖2 綠色環(huán)保度評(píng)估模型
制造服務(wù)組合優(yōu)化模型的目的是在服務(wù)組合中滿足用戶對(duì)QoS的需求,并有效利用資源。對(duì)于某一個(gè)制造任務(wù)T,T={ST1,ST2,…,STn}是一個(gè)復(fù)雜的制造任務(wù),某個(gè)子任務(wù)STk對(duì)應(yīng)i個(gè)候選服務(wù)Si,i=1,2,…,x??紤]資源利用與云制造產(chǎn)品質(zhì)量需求的特點(diǎn),選取云服務(wù)的時(shí)間(Time,Ti)、可靠性(Reliability,Re)、成本(Cost,Co)、企業(yè)信譽(yù)度(Green Credit,Gc)作為衡量QoS的指標(biāo)。由于GC為等級(jí)而非代數(shù)值,為方便處理,A等級(jí)轉(zhuǎn)換為代數(shù)值4,B等級(jí)轉(zhuǎn)換為代數(shù)值3,C等級(jí)轉(zhuǎn)換為代數(shù)值2,D等級(jí)轉(zhuǎn)換為代數(shù)值1。根據(jù)每個(gè)指標(biāo)的特性,計(jì)算方式如表1所示。
表1 指標(biāo)計(jì)算方式
為了更加合理地求解模型,使結(jié)果更具有可行性,建立適合多目標(biāo)參數(shù)的QoS模型:
QoS =(Ti,Co,Re,Gc)
(1)
假設(shè)一個(gè)制造任務(wù)所能接受的最大響應(yīng)時(shí)間為Timax,所能接受的最高成本為Comax,所能允許的最小可靠性為Remin,信譽(yù)度不小于Gcmin,于是建立的約束條件如下:
(2)
所謂的最優(yōu)解模型就是對(duì)其他所有解都形成支配的解,但不一定會(huì)得到支配解,最后可能會(huì)產(chǎn)生多組解,彼此之間無法形成支配與被支配的關(guān)系。
多目標(biāo)優(yōu)化的決策向量X=(X1,X2,…,Xi),一般包括p個(gè)等式的約束、q個(gè)不等式的約束以及r個(gè)目標(biāo)函數(shù),公式如下:
等式約束:
fj(X)=0,j=1,2,…,p
(3)
不等式約束:
gn(X)≤0,n=1,2,…,q
(4)
目標(biāo)函數(shù):
h(X)=[h1(X),h2(X),…,hr(X)]
(5)
其中,h=[h1,h2,…,hr]是目標(biāo)向量。
目前,大多數(shù)研究者采用將多目標(biāo)轉(zhuǎn)換成單目標(biāo)的方法,盡管轉(zhuǎn)換而成的線性求解法在求解形式上解決了多個(gè)目標(biāo)合理協(xié)調(diào)的問題,但是求解結(jié)果無法直觀地顯示各個(gè)指標(biāo)的情況,并且由于人為的主觀性,多目標(biāo)轉(zhuǎn)線性的過程中權(quán)重的配置一直是一大難題,事實(shí)上直接采用多目標(biāo)優(yōu)化的辦法來處理會(huì)有更加貼切的效果。
但是經(jīng)過大自然長時(shí)間的自然選擇,狼群通過不斷地適應(yīng)與集體合作,在行動(dòng)時(shí)表現(xiàn)出了很高效的活動(dòng)形式?;诶侨旱膮f(xié)作捕獵方式,人們提出了灰狼優(yōu)化算法[10]。
灰狼種群等級(jí)一般分為四層,從上而下分別為α,β,δ,ω。α狼位于頂層,β狼次之,緊接著的是δ狼。最底層也就是第四層的ω狼負(fù)責(zé)平衡種群內(nèi)部關(guān)系。GWO算法里前三組依次是適應(yīng)度最好的三組,這三組指導(dǎo)其他的狼(ω)向著目標(biāo)搜索。在優(yōu)化迭代過程中,狼群不斷更新α,β,δ和ω的位置。式6表示個(gè)體之間的距離計(jì)算方式,式7表示灰狼個(gè)體向量的更新方式。
D=|C*X*(t)-X(t)|,C=2r1
(6)
X(t+1)=X*(t)-A*D,A=2a*r2-a
(7)
a=2-2*t/max
(8)
其中,X*表示獵物的位置;X表示灰狼個(gè)體的位置;D表示個(gè)體與獵物的距離與方向;t表示算法當(dāng)前迭代次數(shù)。A控制每次前進(jìn)步數(shù)的大小,其大小由收斂因子a和r2共同決定。其中r1,r2都為0~1間的隨機(jī)數(shù),收斂因子a隨著迭代次數(shù)從2線性減少到0,max是最大迭代次數(shù)。
當(dāng)灰狼判斷出獵物的位置時(shí),頭狼α帶領(lǐng)β和δ指導(dǎo)狼群對(duì)獵物進(jìn)行包圍,因?yàn)棣?β,δ最靠近獵物,所以利用這三頭狼的位置判斷獵物大致位置并逼近獵物,以α,β,δ為指導(dǎo)狼,更新步驟為:
Dα=|C1*Xα(t)-X(t)|,X1=Xα-A1*Dα
(9)
Dβ=|C2*Xβ(t)-X(t)|,X2=Xβ-A2*Dβ
(10)
Dδ=|C3*Xδ(t)-X(t)|,X3=Xδ-A3*Dδ
(11)
X(t+1)=(X1+X2+X3)/3
(12)
其中,Xα,Xβ,Xδ分別為α狼、β狼、δ狼的當(dāng)前位置。
現(xiàn)有GWO算法存在著很多問題,如收斂性不強(qiáng)、易陷入局部最優(yōu)。為了解決上述問題,文獻(xiàn)[11]提出了一種基于Powell局部搜索的灰狼算法(COIGWO),文獻(xiàn)[12]提出了基于鄰域影響的粒子群算法(AOI),文獻(xiàn)[13]提出了一種基于非線性收斂因子策略和動(dòng)態(tài)權(quán)值策略的灰狼算法。受上述算法啟發(fā),為提高多目標(biāo)灰狼優(yōu)化算法的性能,以更好地解決QoS問題,文中提出了基于基礎(chǔ)GWO算法的SGWO。
2.3.1 引入擾動(dòng)變異因子
為改善GWO算法種群的多樣性并避免狼群解集陷入局部最優(yōu)解,在算法中加入擾動(dòng)變異操作。變異概率為:
(13)
其中,max為最大迭代次數(shù);η為變異因子,它控制變異概率降低的速度。
在算法的早期階段,對(duì)應(yīng)著全局搜索,變異概率越高,種群的多樣性越高,而在算法后期,較小的值有利于種群的穩(wěn)定和算法的收斂。
為了使算法擁有更大的搜索范圍和更快的收斂速度,隨著迭代次數(shù)的增加,變異幅度應(yīng)逐漸減小。這里將變異概率應(yīng)用于變異幅度,變異幅度m為:
m=Pt*(Xmax,d-Xmin,d)
(14)
其中,Xmax,d為個(gè)體在第d維上的最大取值;Xmin,d為個(gè)體在第d維上的最小取值。
可見,隨著迭代次數(shù)的增加,變異幅度也會(huì)逐漸減小。為防止更新后的灰狼超出預(yù)先設(shè)定的變異值范圍,需要進(jìn)行限幅操作:
(15)
(16)
其中,Xt,d為個(gè)體變異前的位置,變異后新灰狼個(gè)體的位置向量為:
(17)
其中,α為0~1間的隨機(jī)數(shù)。
2.3.2 引進(jìn)收斂因子策略和動(dòng)態(tài)權(quán)重策略
式8中收斂因子a隨著迭代次數(shù)的增加而線性減小,文獻(xiàn)[13]為了提高前期的搜索范圍且增強(qiáng)后期的收斂速度,將a改為:
(18)
其中,e是自然對(duì)數(shù)的底數(shù);t是當(dāng)前迭代次數(shù);max是最大迭代數(shù)。
通過上述方法可以保證在迭代前期收斂因子a的遞減速度較為緩慢,有利于全局搜索。而隨著迭代次數(shù)的增加,收斂因子a減小速度增加,收斂加快。
在式9~12中,由于算法的局限性,α狼不一定是全局最優(yōu)點(diǎn),隨著迭代次數(shù)的增加,其他ω狼不斷地向這三頭狼逼近,這樣很容易導(dǎo)致陷入全局最優(yōu)點(diǎn)。文獻(xiàn)[13]通過調(diào)整位置向量模值的比例權(quán)重,不僅保證了全局搜索能力,而且增強(qiáng)了局部搜索能力,加快了算法的收斂。
文中提出的權(quán)重比例計(jì)算公式如下:
w1對(duì)應(yīng)于ω狼對(duì)α狼的學(xué)習(xí)率:
w2對(duì)應(yīng)于ω狼對(duì)β狼的學(xué)習(xí)率:
w3對(duì)應(yīng)于ω狼對(duì)δ狼的學(xué)習(xí)率:
對(duì)應(yīng)式12的更新方式,引入動(dòng)態(tài)權(quán)重的更新方式為:
X(t+1)=w1*X1+w2*X2+w3*X3
(19)
2.3.3 基于SGWO的服務(wù)組合優(yōu)化
針對(duì)SGWO算法可用于解決基于環(huán)境保護(hù)的服務(wù)組合優(yōu)化問題,在算法基礎(chǔ)上引入兩個(gè)機(jī)制:
(1)Pareto存檔。SGWO算法在每個(gè)周期中產(chǎn)生新的解集。因此,需要使用帕累托存檔來存儲(chǔ)這些新的解的帕累托解,從而在存儲(chǔ)和檢索優(yōu)化過程中實(shí)現(xiàn)帕累托最優(yōu)解的最佳逼近。指定文件的大小是Nbp,當(dāng)存儲(chǔ)的帕累托解的數(shù)量超過Nbp時(shí),它根據(jù)擁擠距離來進(jìn)行裁剪。
(2)Pareto解集存儲(chǔ)空間更新。新解決方案支配檔案中的一個(gè)或多個(gè)解決方案。在這種情況下,剔除檔案中被支配的解決方案,新的解決方案將能夠進(jìn)入檔案庫;如果新解決方案和存檔成員都不支配,則應(yīng)將新解決方案添加到存檔中;如果存檔已滿,采用歐氏距離計(jì)算各支配方案之間的相似度,找到相似度最高的兩個(gè)或多個(gè)方案,省略其中一個(gè)解決方案。新的解決方案的相似度應(yīng)該較低,以提高最終逼近帕累托最優(yōu)前沿的多樣性。
云制造環(huán)境下基于環(huán)保度的服務(wù)適配被量化為多目標(biāo)灰狼算法中的個(gè)體狼逼近獵物所處的位置,一種位置對(duì)應(yīng)一種服務(wù)適配方案。具體如以下所示。
SGWO算法服務(wù)適配:
Input:QWS數(shù)據(jù)集,包含2 507個(gè)實(shí)際存在的服務(wù)的各個(gè)參數(shù)屬性,如響應(yīng)時(shí)間、可靠性和成本等,由于企業(yè)環(huán)保信譽(yù)值目前無法得到,這里采用隨機(jī)生成的方式對(duì)QWS數(shù)據(jù)集進(jìn)行擴(kuò)充;
Output:與企業(yè)信譽(yù)相關(guān)的一組Pareto解集。
1.在狼群變量的上界和下界中初始化隨機(jī)狼群ΔXi(i=1,2,…,n)
2.定義優(yōu)化指標(biāo)的維度
3.定義非劣解存檔大小
4.計(jì)算所有狼的適應(yīng)度值
5.選擇前三個(gè)最好的狼將它們保存為α、β、δ
6.更新參數(shù)a、A、C
7.使用式19更新其他狼(ω),根據(jù)變量的邊界檢查并更正新的位置
8.根據(jù)獲得的非支配解決方案更新檔案
9.如果存檔已滿,運(yùn)行存檔維護(hù)機(jī)制以省略當(dāng)前存檔成員之一,將新解決方案添加到存檔
10.使用式13~17對(duì)狼群進(jìn)行變異操作
11.是否達(dá)到迭代次數(shù),若不滿足結(jié)束條件轉(zhuǎn)到步驟4
12.結(jié)束,輸出非劣解檔案
QWS數(shù)據(jù)集:在線可用的現(xiàn)實(shí)服務(wù)的QoS各種度量值,該數(shù)據(jù)集由Guelph大學(xué)的Al-Masri和Mahmoud收集[14]。文中選擇的是QWS2.0版本的數(shù)據(jù)集,包含實(shí)際服務(wù)的2 507個(gè)參數(shù),例如響應(yīng)時(shí)間、可用性、吞吐量、可靠性。這些數(shù)據(jù)均由網(wǎng)站的各類搜索引擎搜集而來。數(shù)據(jù)集中的絕大多數(shù)服務(wù)都是可以從互聯(lián)網(wǎng)上直接獲取的,以保證實(shí)驗(yàn)數(shù)據(jù)的真實(shí)性以及可復(fù)刻性,便于相關(guān)工作者研究、對(duì)比實(shí)驗(yàn)結(jié)果。由于企業(yè)環(huán)保信譽(yù)值目前無法得到,文中采取的是隨機(jī)生成的方式。
為了驗(yàn)證SGWO在求解基于綠色環(huán)保度動(dòng)態(tài)更新模型的服務(wù)組合優(yōu)化問題上的有效性,在滿足約束條件的情況下進(jìn)行仿真實(shí)驗(yàn),并與灰狼算法(GWO)、粒子群算法(PSO)以及遺傳算法(NSGA-II)的運(yùn)行結(jié)果進(jìn)行比較。設(shè)定種群規(guī)模為100,迭代次數(shù)為500,1 000,服務(wù)適配最優(yōu)解數(shù)目100,對(duì)比多個(gè)多目標(biāo)優(yōu)化算法在相同迭代數(shù)下的IGD[15]指標(biāo),如圖3所示。IGD計(jì)算方式中所用到的Pareto前沿采取文獻(xiàn)[15]的方式,將四種算法(PSO,NSGA_II,SGWO,GWO)迭代5 000次分別生成四個(gè)解集,將四個(gè)解集按照Pareto修剪規(guī)則合并成新解集,作為Pareto近似前沿解。
圖3 算法IGD對(duì)比
可見,SGWO算法相比于其他算法更接近Pareto前沿面。
實(shí)驗(yàn)中SGWO參數(shù)設(shè)置為:種群大小100,迭代次數(shù)總數(shù)1 000,服務(wù)適配解的數(shù)量100,服務(wù)組合評(píng)估指標(biāo)為時(shí)間、成本、可靠性與環(huán)保信譽(yù)屬性。GWO和SGWO的收斂性對(duì)比如圖4所示。
可見,在初期,由于SGWO中變異因子和收斂因子的影響,GWO短暫表現(xiàn)優(yōu)于SGWO,但在迭代200次后,SGWO的表現(xiàn)逐漸優(yōu)于GWO。
圖5為SGWO算法生成的Pareto前沿,由于模型中有四個(gè)指標(biāo),為了直觀地表現(xiàn)Pareto前沿解,選取成本、企業(yè)信譽(yù)、響應(yīng)時(shí)間三個(gè)維度做三維圖。
圖4 GWO和SGWO收斂對(duì)比
圖5 Pareto前沿解示意
文中提出的QoS模型涉及響應(yīng)時(shí)間、成本、可靠性與環(huán)保信譽(yù)屬性。在選擇每個(gè)列時(shí),對(duì)相應(yīng)的數(shù)據(jù)進(jìn)行預(yù)處理。響應(yīng)時(shí)間大于1 000 ms,可用性和可靠性低于百分之五十的服務(wù)將被放棄。上述QoS屬性由于其范圍、單位均不相同,因此不具備可比性。對(duì)于滿足約束條件的數(shù)據(jù)集,對(duì)可用性、響應(yīng)時(shí)間、可行性、吞吐率進(jìn)行歸一化處理[16],把求解基于企業(yè)信譽(yù)度的服務(wù)組合適配問題轉(zhuǎn)化為求解適應(yīng)度最大值問題。
針對(duì)目前制造業(yè)中忽略環(huán)境指標(biāo)的現(xiàn)象提出GC評(píng)估方案,通過對(duì)企業(yè)環(huán)保信譽(yù)的評(píng)估,并把環(huán)保信譽(yù)評(píng)分高的企業(yè)提高選擇的優(yōu)先級(jí),可以有效鼓勵(lì)企業(yè)進(jìn)行污染整治等工作。文中提出的SGWO很好地應(yīng)對(duì)了多目標(biāo)優(yōu)化中遇到的NP難問題,實(shí)驗(yàn)結(jié)果表明,比起PSO、GWO、NSGA算法,SGWO在上述模型中具有更好的優(yōu)化效果。但該方法也存在收斂速度較慢且非劣解分布不均勻的缺陷,在以后的研究中還有待進(jìn)一步改進(jìn)。