袁東維 鳳飛龍

（①西北政法大學(xué)管理學(xué)院，陜西 西安710122；②陜西師范大學(xué)物理學(xué)與信息技術(shù)學(xué)院，陜西 西安710119）

隨著全球經(jīng)濟一體化的發(fā)展，單一的制造服務(wù)已經(jīng)無法滿足生產(chǎn)需求。云制造作為一種面向服務(wù)的網(wǎng)絡(luò)化制造新模式，其以客戶為核心、以知識為支撐，構(gòu)建了一個虛擬化、分布式以及按需分配的資源共享平臺[1]，企業(yè)將自身的技術(shù)設(shè)備等制造資源和業(yè)務(wù)功能進(jìn)行服務(wù)化封裝，發(fā)布到云制造服務(wù)平臺，由平臺按需調(diào)配，極大程度地盤活了制造資源，提高了企業(yè)的競爭力。

當(dāng)單個云制造服務(wù)無法滿足日漸復(fù)雜的制造任務(wù)時，云平臺會根據(jù)現(xiàn)有云制造服務(wù)的粒度，將制造任務(wù)分解為若干子任務(wù)，從眾多功能屬性相同而服務(wù)質(zhì)量（quality of services， QoS）不同的云服務(wù)集[2]中為每個子任務(wù)匹配相應(yīng)的服務(wù)，形成云服務(wù)組合。如何獲得QoS 最優(yōu)且契合用戶需求的服務(wù)組合是目前國內(nèi)外學(xué)者關(guān)注的重點。

群智能算法是當(dāng)下解決云服務(wù)組合優(yōu)化的主流方法[3-7]，Pan W 等[4]將遺傳算法和混沌思想相結(jié)合實現(xiàn)種群優(yōu)化，提高了服務(wù)組合的效率，但組合的可靠性沒有明顯改善；Seghir F 等[6]采用人工蜂群算法提高算法的搜索能力，優(yōu)化結(jié)果顯著提高，但其在構(gòu)建組合優(yōu)化求解模型時，主要關(guān)注服務(wù)自身的QoS 屬性；齊琦等[7]采用鄰域搜索和模擬退火算法來改進(jìn)NSGA-II 算法的局部搜索能力，其云服務(wù)組合能力得到極大的提升，但NSGA-II 算法在目標(biāo)維數(shù)過高時，算法運行效率低，優(yōu)化效果不明顯；賴文星等[8]提出了基于支配強度的改進(jìn)NSGA-II 算法，該算法在多個領(lǐng)域取得較好的結(jié)果。本文改進(jìn)了支配強度的概念，提出了基于改進(jìn)NSGA-II 算法的云制造服務(wù)組合優(yōu)化方法，具有以下特點：

（1）針對多目標(biāo)優(yōu)化Pareto 前沿解集過大，改進(jìn)了支配強度的概念，可以快速有效地確定個體的優(yōu)劣。

（2）優(yōu)化局部搜索能力，在算法前期重點搜索優(yōu)秀個體，加速算法收斂，算法后期則對稀疏個體融合鄰域搜索與模擬退火算法來增加種群多樣性，使算法能夠更好地處理多目標(biāo)優(yōu)化問題。

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

在云制造服務(wù)組合中，用戶需求被抽象表示為一個制造任務(wù)T，每個制造任務(wù)在云平臺中被分解為n個子任務(wù)，即T={S T1,S T2,···,S Tn}，子任務(wù)在云平臺中對應(yīng)的服務(wù)集合為{CS1,CS2, ···,CSn}，其中第i個子任務(wù)的候選服務(wù)集合CSi={CSi1,CSi2, ···,CS im}，表示第i個子任務(wù)共有m個候選制造服務(wù)，它們都能完成相同的功能屬性。

云制造服務(wù)組合就是從各候選服務(wù)集合中選擇一個具體的制造服務(wù)來完成用戶需求。

1.1 QoS 評價指標(biāo)

云制造服務(wù)既考慮服務(wù)本身的質(zhì)量，又對線下制造部分充分挖掘，采用的QoS 評價指標(biāo)有以下5 個。

（1）服務(wù)時間C1：指用戶提出服務(wù)請求到服務(wù)執(zhí)行結(jié)束所需要的時間。

（2）服務(wù)成本C2：指用戶獲得服務(wù)所支付的費用，包括制造成本、物流運輸成本和服務(wù)成本。

（3）服務(wù)可靠性C3：指成功執(zhí)行云制造任務(wù)的能力，一般指產(chǎn)品質(zhì)量的達(dá)標(biāo)率。

（4）交工準(zhǔn)時性C4：指云制造服務(wù)商的按時交貨率。

（5）服務(wù)滿意度C5；指用戶在服務(wù)完成后，對云制造服務(wù)商整體服務(wù)的滿意度。滿意度的評分規(guī)則借鑒文獻(xiàn)[9]中的量化規(guī)則，劃分為 5 個等級，各級賦分為非常不滿意（1 分）、不滿意（3 分）、基本滿意（5 分）、滿意（7 分）、非常滿意（9 分）。

1.2 云制造服務(wù)組合優(yōu)選方法及模型

云制造服務(wù)組合工作流程內(nèi)部結(jié)構(gòu)復(fù)雜，但其主要結(jié)構(gòu)包括四種模式：順序、并行、選擇和循環(huán)[10]。不同組合模式下的云制造服務(wù)組合QoS 計算模型見表1，其中， γi是候選云制造服務(wù)Si被選中的概率，且=1； λ為服務(wù)Si的循環(huán)次數(shù)。

表1 不同模式QoS 計算模型

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

式中：QC1表示云制造服務(wù)組合總的時間，QC2、QC3、QC4和QC5分別表示云制造服務(wù)組合總的成本、總的可靠性、總的交工準(zhǔn)時性和總的服務(wù)滿意度。約束條件（3）表示制造服務(wù)組合總時間和成本不能超過用戶給定的最長時間Tmax和最大成本Cmax。

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

云制造服務(wù)組合優(yōu)選問題是一個多目標(biāo)優(yōu)化問題，非支配遺傳算法NSGA-II[11]是目前解決這類問題的最優(yōu)秀的算法之一。但是當(dāng)目標(biāo)函數(shù)的維數(shù)過高時，會導(dǎo)致帕累托前沿上解集過大，算法的收斂度顯著下降；同時NSGA-II 算法自身缺少良好的局部搜索能力，在優(yōu)化過程中容易陷入局部最優(yōu)解。本文通過改進(jìn)支配強度概念來快速有效地確定Pareto 最優(yōu)解個體的優(yōu)劣，在NSGA-II 算法的基礎(chǔ)上構(gòu)建靈活的局部搜索策略。算法流程圖如圖1 所示，算法實現(xiàn)步驟如下。

圖1 算法流程圖

步驟1：初始化種群，為保證初始種群有足夠的數(shù)量，隨機生成種群大小為N的1.2 倍的初始種群P0，檢查約束條件（3），刪除違反約束條件或者重復(fù)的個體，然后對種群進(jìn)行快速非支配排序[8]，計算個體的非支配等級、支配強度和擁擠距離。

步驟2：對當(dāng)前種群Pt（t為種群代數(shù)）進(jìn)行錦標(biāo)賽選擇，選出種群Pt中的優(yōu)秀個體，并對其進(jìn)行均勻兩點交叉和基本位變異，得出子代種群Ps。

步驟3：合并父代種群Pt和子代種群Ps，對混合種群進(jìn)行非支配排序，計算其中個體的的非支配等級、支配強度和擁擠距離，選出規(guī)模大小為N的新種群Pg。

步驟4：取新種群的部分個體進(jìn)行局部搜索，將其得到的非支配解加入到外來種群當(dāng)中。

步驟5：將外來種群與新種群Pg合并，淘汰不良個體，得到規(guī)模大小為N下一代種群Pt+1。

步驟6：判斷當(dāng)前迭代次數(shù)t與最大迭代次數(shù)Gmax的大小，若t≤Gmax，則轉(zhuǎn)步驟2 ；否則跳出循環(huán)，按綜合評價值降序輸出 Pareto 最優(yōu)解集。

2.1 編碼方式

根據(jù)云制造服務(wù)組合的特征，采用自然數(shù)編碼方式，對各子任務(wù)對應(yīng)的候選云服務(wù)集中的服務(wù)進(jìn)行編碼，每個子任務(wù)選擇的服務(wù)編碼作為相應(yīng)染色體上的基因位。例如云制造服務(wù)組合序列CS13-CS26-CS32-CS47-CS52，表示的編碼序列為[3 6 2 7 2]。

2.2 支配強度及個體間的比較

當(dāng)目標(biāo)函數(shù)維度過高時，基于Pareto 支配尋優(yōu)很難評判個體優(yōu)劣，導(dǎo)致Pareto 前沿解集過大，使算法的性能下降。引用支配強度[9]來比較非支配集中個體的優(yōu)劣。因為本文同時有最大值和最小值優(yōu)化，所以對非支配集中個體i的支配強度定義如下：

式中：Ckmax、Ckmin分別代表第k個子目標(biāo)的最大值和最小值。

改進(jìn)后的NSGA-II 算法經(jīng)過非支配排序、支配強度計算及擁擠距離計算后，每個個體就有了三個屬性：非支配等級Ranki、支配強度 ξi和擁擠距離Di。對于任意兩個個體i和j有以下的的優(yōu)先級關(guān)系：

2.3 局部搜索

由于NSGA-II 算法前期仍然存在搜索隨機性差、收斂速度慢、算法后期解的分布均勻性較差[12]等問題，針對這種情況，本文提出與進(jìn)化代數(shù)相關(guān)的局部搜索策略。在進(jìn)化代數(shù)的前半部分，對優(yōu)秀個體進(jìn)行鄰域搜索，以加速算法收斂；而在算法后半部分，選擇擁擠距離最大的個體，采用鄰域搜索和模擬退火算法來增加解集的廣泛性。局部搜索流程如圖2 所示，R為執(zhí)行局部搜索的次數(shù)，種群的規(guī)模為N。

圖2 局部搜索流程圖

2.3.1 鄰域搜索

算法中每個基因位對應(yīng)的是具體的云制造服務(wù)，本文采用隨機選擇1-opt 交換、2-opt 和3-opt 交換的鄰域搜索方式，對候選云制造服務(wù)組合進(jìn)行搜索，具體操作如圖3 所示。

圖3 鄰域搜索方式

2.3.2 模擬退火操作

在當(dāng)前非支配解中以擁擠距離最大的解作為稀疏解，引入模擬退火操作對其進(jìn)行局部搜索。由于模擬退火算法是單目標(biāo)優(yōu)化算法，對于多目標(biāo)優(yōu)化問題，算法隨機選取一個目標(biāo)函數(shù)作為搜索方向，將所獲新個體放入外來種群。

2.4 優(yōu)選策略

得到非支配解集后，需要選擇滿足用戶偏好的最優(yōu)云制造服務(wù)組合。對于用戶偏好的權(quán)重分配，本文借鑒文獻(xiàn)[13]的方法，由用戶及行業(yè)專家對QoS 指標(biāo)進(jìn)行兩兩對比，得到n階初始矩陣A=(Cij)n*n，其中：

對A中的每一行求和得到模糊矩陣：Q=(q1,q2,···,qn)T

其中：

各目標(biāo)函數(shù)的權(quán)重向量依次為

由于云制造服務(wù)的QoS 指標(biāo)量綱不同，不能直接進(jìn)行選優(yōu)，因此使用歸一化方法對各指標(biāo)進(jìn)行規(guī)范化處理，見式（1），其中QC1、QC2為成本型目標(biāo)函，QC3、QC4、QC5為效益型目標(biāo)函數(shù)。

則在最后的Pareto 最優(yōu)解集中，第h個候選云制造服務(wù)組合的綜合評價值為

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

3.1 實驗描述與分析

本節(jié)以一個小型電動車驅(qū)動系統(tǒng)制造任務(wù)為例，驗證本文算法進(jìn)行云制造服務(wù)組合優(yōu)化的可行性。云平臺將電動車驅(qū)動系統(tǒng)制造任務(wù)分解成5 個制造子任務(wù)，如圖4 所示，每個子任務(wù)匹配到5 個符合制造要求的云服務(wù)，各候選云服務(wù)集參數(shù)見表2。

圖4 電動車制造工藝流程圖

表2 候選云制造服務(wù)集相關(guān)參數(shù)

本文在Matlab 2017 環(huán)境下進(jìn)行多目標(biāo)優(yōu)化求解，企業(yè)要求總成本不超過18 000 元，服務(wù)周期不超過320 個單位時間。設(shè)置實驗種群規(guī)模N=100，交叉概率0.95，變異概率0.04，最大進(jìn)化代數(shù)Gmax=100，生成初始種群，按照第2 節(jié)所述步驟進(jìn)行，直到輸出非支配解集。對用戶偏好進(jìn)行兩兩對比得到5 階初始矩陣A：

對A中的每一行求和，計算得到QoS 各指標(biāo)權(quán)重見表3。

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

計算非支配解集的綜合評價值 Φ，輸出的非支配解集見表4。

表4 非支配解集

基于用戶偏好，本文提出的算法最后選擇第3組云制造服務(wù)組合，組合序列為[44242]，即CS14-CS24-CS32-CS44-CS52為最終的優(yōu)選方案。若用戶的需求偏好發(fā)生變化，可以重新對比QoS 權(quán)重，再對上述非支配解集重新排序，這樣不僅節(jié)約了服務(wù)組合時間，還提高了算法解決問題的靈活性。

3.2 對比分析

為了驗證本文算法解決云制造服務(wù)組合問題的有效性，分別與采用自然數(shù)編碼的基本NSGA-II[11]算法，基于模糊支配的f-NSGA-II 算法[14]、NSGA-IIARSBX 算法[15]和多目標(biāo)粒子群優(yōu)化算法MOPSO[16]分別對該實例進(jìn)行求解。

為保證公平性，設(shè)置最大進(jìn)化代數(shù)Gmax=100，種群規(guī)模為100，交叉概率0.95，變異概率0.04，四種算法分別獨立進(jìn)行10 次以上實驗，各優(yōu)化指標(biāo)取非支配解集中的最優(yōu)值和平均值，最終得到本文算法和這四種算法結(jié)果比較，見表5。

表5 算法結(jié)果比較

實驗結(jié)果表明，本文算法在各項指標(biāo)中篩選出的最優(yōu)值和平均值均優(yōu)于或等于其他算法，說明本文算法的求解性能良好。從非支配解的個數(shù)來看,本文算法有更多的非支配解，說明該算法本身有較強的全局搜索能力。從總體上說，該算法擁有更好的綜合性能。

4 結(jié)語

日趨復(fù)雜的制造任務(wù)使得對云制造服務(wù)組合的篩選從更多個維度進(jìn)行，當(dāng)目標(biāo)函數(shù)維度過高時，基于Pareto 支配尋優(yōu)很難評判個體優(yōu)劣。本文通過改進(jìn)支配強度的概念區(qū)分Pareto 最優(yōu)解集的優(yōu)劣，通過靈活的局部搜索策略提高了NSGA-II 算法的性能。最后的實例驗證了該算法的可行性及優(yōu)越性。

在制造生產(chǎn)中，云制造服務(wù)組合之間存在著極大的關(guān)聯(lián)性，后續(xù)的研究工作將重點研究這種關(guān)聯(lián)性對其他QoS 指標(biāo)的影響。