基于NSGA-Ⅲ算法的云制造服務組合優(yōu)選方法

尹 超,許加晟,李孝斌

(重慶大學 機械傳動國家重點實驗室,重慶 400044)

0 引言

云制造是一種面向服務、高效節(jié)能、基于知識的網絡化智能制造新模式[1]，其利用互聯網和云服務平臺將各類制造資源封裝為網絡化服務，以滿足用戶的個性化制造需求[2]。在云制造環(huán)境下，海量、異構的制造資源與制造能力具有一定的地域性流通、自主性共享、動態(tài)演化等特征[3]。因此，實現制造資源與服務的最優(yōu)組合與配置，避免資源的閑置與浪費，是促進云制造模式向傳統制造產業(yè)深度融合與應用的關鍵技術之一。近年來，國內外學者對云制造服務組合問題不斷探索，取得了一定的研究成果。在組合優(yōu)化QoS指標選擇方面，除對時間、成本、可靠性、可用性等基礎屬性指標進行研究以外[4-7]，ZHOU等[8]考慮了信譽度、可組合性；ZHANG等[9]同時考慮了交付時間和延遲時間；LARTIGAU等[10]從環(huán)境可持續(xù)發(fā)展的角度，將生態(tài)因素納入評價指標體系中。雖然上述研究提出了一些創(chuàng)新性的評價指標，但在對歷史評價屬性指標進行量化考量時缺乏對歷史屬性時效性的考慮。文獻[5-9]將服務可靠性、服務可用性等歷史屬性值指定為歷史事件段內的固定值，并未考慮該類屬性值存在隨時間演變的動態(tài)特性;文獻[10]雖然考慮了服務可用性隨時間變化的特性，但對服務可靠性、服務可持續(xù)性等歷史屬性指標進行量化時未考慮時效性。在優(yōu)化目標求解方面，雖然部分學者研究了云制造環(huán)境下的多目標優(yōu)化問題，但通常是將多目標優(yōu)化函數通過線性加權轉化為單目標優(yōu)化問題并進行求解[5-6,11-14]，此類方法存在如下問題：①各目標函數的權重分配具有較大的主觀性；②各個目標之間通常存在一定的相互矛盾和約束關系，而目標函數僅為各項指標的線性加權和，無法獲得相應的均衡解；③求解過程中各目標的優(yōu)化進度不可觀測且難以調節(jié)?；诖耍瑖鴥韧鈱W者也提出了帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)[15-16]、SPEA2(improving the strength Pareto evolutionary algorithm)[17]、 多目標粒子群算法(Multi-objective Particle Swarm Optimization, MOPSO)[18]和多目標免疫系統算法(Multi-objective Immune System Algorithm, MISA)[19]等智能算法解決包括2維、3維目標的云制造服務組合優(yōu)選與調度問題。但在求解更高維度的服務組合優(yōu)化問題時，上述算法中采用的擁擠算子[15-16]、聚類算子[17]仍然不能評價候選解的多樣性。

綜上所述，現有云制造服務組合優(yōu)選方法通常在對歷史評價信息進行量化考量時忽略了其時效性和動態(tài)性特征，同時所提出的算法在解決多維目標優(yōu)化問題時，結果客觀性較差，無法充分評價候選解的多樣性及單個指標所產生的影響。為此，本文結合NSGA-Ⅲ算法在保持種群多樣性及高維目標求解代價等方面的優(yōu)勢，提出基于NSGA-Ⅲ的云制造服務組合優(yōu)選方法。首先，構建云制造服務的非功能屬性與歷史評價屬性評價模型；在非功能屬性中以總時間、總費用為優(yōu)化目標，在歷史評價屬性中以歷史服務滿意度、歷史服務可靠度、歷史服務質量為優(yōu)化目標，建立云制造服務多目標優(yōu)選組合模型。最后，基于NSGA-Ⅲ算法對所構建的多目標優(yōu)選組合模型進行求解，并在團隊所研發(fā)的云制造服務平臺中驗證所提模型的可行性和算法的有效性。

1 問題描述與多屬性評價指標體系

1.1 問題描述

云制造是一個由多主體組成的協同制造服務網絡，包括服務需求方(Service Demander, SD)、服務提供方(Service Provider, SP)與云服務平臺(Cloud Service Platform，CSP)。在云制造環(huán)境下，SD首先利用CSP交互接口描述并發(fā)布相應的制造任務；該任務需求信息通過CSP的合規(guī)性審查后，結合平臺中的工藝知識庫，調用任務解析工具對SD提出的制造任務按照原子業(yè)務邏輯進行分解；在此基礎上，通過調用智能搜索與匹配工具，為各子任務匹配相應的可選制造資源集合。云制造服務的組合優(yōu)選則是在候選資源集合中按照順序、并行、選擇、循環(huán)4種任務執(zhí)行邏輯選擇最佳資源進行組合和評價，以確保云制造服務的可靠運行,其業(yè)務邏輯如圖1所示。

首先給出如下定義：

CMT={CMSTi|i=0,1,…,n}表示第i個任務可分解為n個子任務CMST的集合；

CMSGi={CMSij|j=0,1,…,mi}表示符合子任務CMSTi需求的待選制造服務資源集合，其中：mi表示為CMSGi中待選資源的數量，CMSij表示原子任務CMSTi可由CMSGi中的第j個候選資源進行服務；

1.2 云制造服務屬性評價指標

云制造服務評價指標的選取應充分考慮服務需求方服務質量要求、指標選取的全面性、指標實用性等。本文基于云制造服務運行特點及其供需匹配需求，將評價指標劃分為非功能屬性和歷史評價屬性兩個方面，構建云制造資源服務能力評價模型，如圖2所示。

2 云制造服務多目標優(yōu)選組合模型

基于上述分析，本文以服務總費用、服務時間等非功能屬性，以及歷史服務質量、歷史服務滿意度、歷史服務可靠性等歷史服務評價屬性為優(yōu)化目標，建立云制造服務多目標優(yōu)選組合模型。

2.1 目標函數及相關約束

首先定義決策變量xij：

(1)

2.1.1 非功能屬性目標函數

(1)服務時間(T)，包括制造加工時間T1及物流轉運時間T2。其中：T1表示第i個CMSTi的制造加工時間，T2表示從云制造服務CMSij到CMSi+1j*所需的物流轉運時間。服務時間的優(yōu)化目標是使云制造服務組合的總服務時間最短，其目標函數為：

minT=min(T1+T2),

(2)

(3)

(4)

(2)服務成本(C)，包括制造加工成本C1和物流轉運成本C2。其中：C1表示完成制造任務所需支付的費用，為工件單價Cuni與數量的乘積(C1(CMS)=Cuni·Num)；C2表示從云制造服務CMSij到CMSi+1j*所需的物流轉運成本。服務成本的優(yōu)化目標是使云制造服務組合的總服務費用最低，其目標函數為：

minC=min(C1+C2),

(5)

(6)

(7)

2.1.2 歷史評價屬性目標函數

現有組合優(yōu)選方法中對不同時間段的歷史服務評價賦予了同等權重，忽略了云制造服務評價屬性隨時間變化呈現的動態(tài)性。因此，為減少云制造服務資源評價屬性中歷史評價對當前服務組合優(yōu)選的影響[23]，定義一個權重隨時間變化的時間效應函數

f(t)=e-λt。

(8)

該時間效應函數的取值范圍為[0,1]，參數因子λ=1/T0。隨著時間的推移，距當前時間較為久遠的評價信息權重將會逐漸降低，反之評價權重將會增大；參數λ決定了歷史評價屬性的衰變率(每經過T0天衰減為原來的1/2)。為此，本文基于時間衰減函數按時間段進行均勻分割并設計評價窗：以ΔT表示總時間長度；將總時間長度劃分為L個間隔，Δtl表示第l∈{1,2,…,L}個時間間隔，衰減函數如圖3所示。

由圖3可知，函數值隨時間的增大而減小，且隨著T0增大，函數值減小的速率逐漸變慢。本文設置總體時間段T0=200，將總時間長度分割為5個區(qū)間，即t∈[0,40)、t∈[40,80)、t∈[80,120)、t∈[120,160)、t∈[160,200)。每個區(qū)間對應衰減函數在該時間段內的函數平均值作為各個時間段的權重，權重計算公式如下：

(9)

即Wl作為每個時間段的動態(tài)權重對歷史服務屬性進行加權計算。

(1)歷史服務可靠性(R) 包括服務成功率R1和服務安全性R2。其中：R1指該時間間隔內，云制造服務成功完成的次數占服務運行總次數的比率；R2指制造資源在提供服務過程中未發(fā)生生產異常的次數與服務總次數的比率。將總時間分割數L中各個時間間隔的制造服務可靠性歷史數據進行加權平均計算，可得：

(10)

(11)

(12)

(13)

(2)歷史服務質量(Q) 包括加工合格率Q1和準時交貨率Q2。其中：Q1指該階段合格產品數與加工總數量的比值；Q2指該階段制造資源在提供服務過程中準時交貨率。將總時間分割數L中各個時間間隔的制造服務可靠性歷史數據進行加權平均計算可得：

(14)

(15)

(16)

(17)

(3)歷史服務滿意度 云制造服務資源的滿意度是服務需求者通過打分方式評定的結果，其評價語言具有模糊性。因此，采用三角模糊數對其進行表示，其評價語言變量和對應的三角模糊數如表1所示。

表1 語言變量和相對應的三角模糊數

首先，將各個時間間隔的云制造服務資源歷史評價信息轉化為三角模糊數：

(18)

然后，將三角模糊數轉為數值，并利用式(19)將處于同一時間間隔內的歷史滿意度進行平均處理。

(19)

最后，將處于不同時間間隔的云制造資源歷史滿意度數據進行加權平均處理。

(20)

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

云制造服務資源組合優(yōu)化的總目標是使完成整個云制造任務的總服務時間最短、總服務費用最少、歷史服務滿意度最高、歷史服務可靠度最高、歷史服務質量最高。該模型為一個五維優(yōu)化目標模型，屬于典型的多目標優(yōu)化問題。因此，所建立的云制造服務組合優(yōu)選多目標優(yōu)化模型為：

F(X)=(minT,minC,maxR,maxQ,maxSa)。

s.t.

T≤Tmax,

C≤Cmax,

R≥Rmin,

Q≥Qmin,

Sa≥Samin。

(21)

其中5個約束分別表示模型中的總服務時間T不超過服務需求者規(guī)定的最長時間Tmax，總服務費用C不超過服務需求者規(guī)定的最高價格Cmax，歷史服務可靠度R不低于服務需求者規(guī)定的最低可靠度Rmin，歷史服務質量Q不低于服務需求者規(guī)定的最低服務質量，歷史服務滿意度Sa不低于服務需求者規(guī)定的最低服務質量Samin。

對于該組合優(yōu)選模型，定義X={CMS1j,…,CMSij,…,CMSnj}T為該多目標優(yōu)化問題的一個可行解。兩個決策向量xa,xb∈X可分別視為兩個制造服務組合方案，當且僅當：{f(xa)≤f(xb)∧-f′(xa)≤-f′(xb)}成立時，即組合方案xa對應的目標函數值均小于等于組合方案xb對應的目標函數值，且組合方案xa至少存在一個目標函數值小于組合方案xb對應目標函數值時，稱xa帕累托占優(yōu)于xb，也稱xa支配xb，記為xa>xb。若不存在任何決策向量帕累托占優(yōu)于組合方案xa，則稱其為帕累托最優(yōu)解(或非支配解)，所有帕累托最優(yōu)解構成帕累托最優(yōu)解集。

在該多目標優(yōu)化問題的求解過程中，某目標函數值的優(yōu)化可能伴隨著其他目標函數值的劣化。由于多個目標間的相互約束關系，不可能存在一個解使得所有目標都達到最優(yōu)，而通常是一個解的集合，即該模型的求解是找到一個最接近帕累托最優(yōu)解集的解集。為此，本文基于NSGA-Ⅲ算法在高維目標優(yōu)化求解問題的性能優(yōu)勢，對所構建模型進行求解。

3 基于NSGA-Ⅲ的組合優(yōu)選模型求解

本文所提模型本質上是一個多目標組合優(yōu)化問題，為解決此類問題，DEB等[15-16]提出了NSGA-Ⅱ，該算法引入精英策略提高種群的采樣，引入排擠機制使解得到均勻分布，并利用快速非支配排序降低了運算的復雜度。然而當遇到高維(三維以上)目標優(yōu)化問題時，種群中非支配解占整個種群的比例成倍增加，使得種群中沒有足夠的位置容納新解，導致算法收斂變慢且最優(yōu)解過于集中。同時，當目標函數數量增加時，算法擁擠距離算子的計算成本較高。而NSGA-Ⅲ算法加入了基于參考點的方法，在保持種群多樣性的同時，能有效降低高維目標函數的計算代價，為本文所構建模型提供了有效的求解思路。

3.1 NSGA-Ⅲ算法求解步驟

使用NSGA-Ⅲ算法求解云制造服務優(yōu)選組合模型的具體步驟如圖4所示。

步驟1初始化算法參數，包括總迭代次數、變異率、交叉率等。

步驟2確定編碼規(guī)則并初始化種群Pt，設置迭代次數的初始值為0。

步驟3基于各維度目標上的等分數與目標函數個數生成分布均勻的參考點。

步驟4計算種群個體的適應度，并根據模型的約束處理規(guī)則修復種群中越界個體。

步驟5利用交叉變異操作生成子代種群Qt，計算每個子代種群中個體的適應度，并根據約束規(guī)則修復種群中的越界個體。

步驟6將種群Pt與子代種群Qt進行合并，合并后的種群規(guī)模為2N。

步驟7將合并后的種群進行快速非支配排序，得到若干非支配層F1,F2,F3,…,FL。

步驟8將優(yōu)先級較高的非支配層加入下一代種群，直到將第L層的全部個體都選擇到下一種群中，若下一代種群規(guī)模等于N則執(zhí)行步驟11；若下一代種群規(guī)模大于N，則執(zhí)行步驟9。

步驟9將前L層的個體進行歸一化處理，使其取值在[0,1]之間。

步驟10計算前L層所有個體與參考點的垂直距離，找到與每個個體相關聯的參考點，若個體到某個參考點的垂直距離最小，則認為該個體與該參考點相關聯。計算第j個參考點的小生境，并基于此從L層中選擇K個個體進入下一代種群，使種群規(guī)模等于N，同時迭代次數增1。

步驟11判斷是否達到設定的迭代次數，若是則終止迭代；否則重復步驟5～步驟10。

(1)編碼

采用整數編碼方法建立基因編碼與服務組合方案之間的映射關系。在云制造環(huán)境中，一個復雜制造任務分解為n個子任務，每個子任務匹配一個候選制造資源集合，則服務組合由n個單一制造資源云服務組合而成。因此，一個云制造服務組合可表示為包含n個基因的染色體片段，如圖5所示。

(2)種群初始化

種群初始化的步驟為：①定義種群大小為N，制造子任務數量n，子任務序號為i；②令初始序號i=0；③根據每個子任務序號對應的資源集合個數mi生成N維隨機數k∈{1,2,…,mi}的列向量；④令i=i+1，判斷i是否大于n，若是則將多個列向量疊加形成N×n維的種群初始矩陣，否則返回繼續(xù)執(zhí)行③；⑤判斷矩陣是否出現重復編碼，若是則刪除重復個體并補充新個體，否則輸出初始種群矩陣，矩陣可表示為：

(3)參考點生成方法

NSGA-Ⅲ算法需預先生成一組參考點以保證解的多樣性，本文參考文獻[27]中的方法生成內層與外層的參考點。

4)合并內層與外層參考點集合，得到最終的參考點集合S=S1∪S2。

(4)目標函數歸一化方法

1)定義M為優(yōu)化目標的數目，令j∈{1,2,…,m}；

(5)基于參考點的個體選擇方法

步驟如下：

1)令k=1，K為需要尋找的最后一個前沿面?zhèn)€體的個數，定義ρj為前L-1層中與第j個參考點相關聯的個體的數目。

3)若第L層沒有個體與參考點相關聯，即Ij為空集，則該代中不考慮參考點j。否則，考慮兩種情況：

若前L-1層無個體與第j個參考點關聯，而第L層中至少有一個個體與第j個參考點相關，則將與第j個參考點垂直距離最短的個體選擇到下一代中，且第j個參考點相關的小生境數增加1，即ρj=ρj+1；

若前L-1層至少有一個個體與第j個參考點關聯，則隨機從L層中選擇一個個體添加到下一代中且第j個參考點相關的小生境數增加1，即ρj=ρj+1

4)令k=k+1，判斷是否k≤K，若是則重復步驟2)～步驟4)，否則，輸出選擇操作后的種群。

3.2 多目標算法評價指標

為了評價多目標優(yōu)化算法，選取世代距離(Generational Distance, GD)、反轉世代距離(Inverted Generational Distance, IGD)兩種多目標算法評價指標來評估算法性能。

(1)世代距離GD

GD為一元評價指標[28-29]，通過計算算法求解出的非支配解集到真實帕累托前沿的平均最小歐式距離，從而評估解集的收斂性。GD值越小，收斂性越佳。計算公式如下：

(22)

式中：d(x*,X)表示解x*∈P*到X中的最小歐式距離，|P|表示P內解的個數。

(2)反轉世代距離IGD

IGD為二元評價指標[30]，通過計算真實帕累托前沿中所有解與算法求解出非支配解的平均歐式距離，從而評估解集的收斂性與多樣性。IGD值越小，解集越逼近真實帕累托前沿且分布均勻，解集的收斂性與多樣性愈佳。計算公式如下：

(23)

式中：d(x*,X)表示解x*∈P*到X中的最小歐式距離，|P*|表示P*內解的個數。

4 算法測試與算例分析

為驗證所提模型及方法的可行性和有效性，本文分別設計了算法測試和應用算例。實驗在MATLAB R2016a軟件上實現，系統為Windows 10，內存8 GB。

4.1 算法測試

選取DTLZ函數作為算法測試函數，分別為DTLZ1，DTLZ2，DTLZ3，DTLZ4。選取NSGA-Ⅱ算法作為對比算法，設置種群為100，交叉概率為1，變異概率為1/D，交叉參數為20，變異參數為20。分別測試M=3,5,8,10,15這五組實驗，每組實驗運行20次，其結果如表2和表3所示。

表2 世代距離對比表

續(xù)表2

表3 反轉世代距離對比表

從兩表可以看出：在處理DTLZ1～DTLZ4函數過程中，若目標維度超過三維，NSGA-Ⅲ的GD與IGD的值均比NSGA-Ⅱ更小，證明在處理高維多目標優(yōu)化問題中，NSGA-Ⅲ相較于NSGA-Ⅱ具備更好的性能。

4.2 算例驗證

結合課題組前期開發(fā)的云制造服務平臺中的制造服務運行情況對方法的可行性進行驗證。首先將云制造任務劃分為6個子任務，各子任務按照順序結構執(zhí)行，依次表示為{CMST1,CMST2,CMST3,CMST4,CMST5,CMST6}；根據子任務的需求為其匹配相應的制造服務待選；最后為每個子任務選擇一個資源進行隨機組合，通過所選算法求出最優(yōu)的組合方案集合。各子任務的服務資源候選集合如表4所示。

為了驗證NSGA-Ⅲ算法的有效性和性能，本文設計3組實驗，并將NSGA-Ⅲ算法所得結果與NSGA-Ⅱ算法進行比對分析。3組實驗的目標函數分別為：

實驗1：總時間最低、總費用最少；

實驗2：歷史服務滿意度最高、歷史服務可靠度最高、歷史服務質量最高；

實驗3：總時間最低、總費用最少、歷史服務滿意度最高、歷史服務可靠度最高、歷史服務質量最高。

在實驗中，設置時間間隔L=5，設置約束條件為：總成本C≤120千元；總時間T≤350 h；歷史服務滿意度Q≥0.5；歷史服務可靠度R≥0.85；歷史服務質量Q≥0.85。云制造子任務候選服務資源集合的相關信息分別如表4～表6所示。

表4 待選資源集合

表5 非功能屬性評價指標值表

表6 歷史評價屬性指標值表

在實驗1～3中，將總時間長度分割為5個間隔，使用Wl=f(t)=e-Δtl/50計算每個間隔時間段的指標權重，得到Δt1-5的權重W1-5分別為1,0.45,0.2,0.09,0.04；ωR1,ωR2,ωQ1,ωQ2分別設為0.6,0.4,0.55,0.45。取初始種群N=126，最大迭代次數Generation=300，交叉概率Pc=1，變異概率為Pm=0.10，優(yōu)化目標M=2,3,5。

如圖6與圖7所示為NSGA-Ⅲ與NSGA-Ⅱ算法在實驗1中的測試結果，兩者得到的Cost-Time Pareto解集與平均適應度幾乎相同，并沒有明顯差異。

圖8～圖10展示了NSGA-Ⅲ與NSGA-Ⅱ算法在實驗2中的測試結果。從箱型圖中可看出，在解決3目標優(yōu)化問題時NSGA-Ⅲ與NSGA-Ⅱ各自在一個方向上的Q2明顯優(yōu)于對方，兩者異常值的分布幾乎相同，但NSGA-Ⅲ所求得的正常值分布性更廣，收斂性更佳。

在求解高維目標優(yōu)化問題方面，采用兩種算法優(yōu)化該問題，求解后的平均適應度、數據的分布如圖11～圖14所示。從圖11、圖12與圖14中均可看出，采用NSGA-Ⅲ算法獲得的4個方向的優(yōu)化結果都比NSGA-Ⅱ算法獲得優(yōu)化結果更好。因此，本文所使用的NSGA-Ⅲ算法能夠很好地解決高維多目標優(yōu)化問題，所獲取的帕累托解集即服務組合可為擁有不同偏好的服務需求者提供更優(yōu)的服務組合。

5 結束語

本文提出了一種基于歷史屬性動態(tài)特性的制造服務組合優(yōu)選模型。綜合考慮非功能屬性和歷史評價屬性，在非功能屬性中以總時間最低、總費用最少為優(yōu)化目標，在歷史評價屬性中以歷史服務滿意度最高、歷史服務可靠度最高、歷史服務質量最高為優(yōu)化目標構建了云制造制造服務多目標優(yōu)選組合模型。在此基礎上，應用NSGA-Ⅲ算法對所構建的多目標優(yōu)化模型進行求解。通過算法測試和算例實驗表明：相比于NSGA-Ⅱ，NSGA-Ⅲ能夠更好地實現制造服務在高維目標上的求解。下一步將結合云邊協同理論，重點對制造服務數據云邊協同處理、制造任務云邊協同調度，以及車間高頻擾動下制造服務云邊協同調控方法等相關理論技術展開研究。