基于改進人工蜂群算法的云制造服務組合優化方法

胡強，田雨晴，綦浩泉，吳鵬，劉慶雪

（1.青島科技大學信息科學技術學院，山東 青島 266061；2.昆明學院機電工程學院，云南 昆明 650214）

0 引言

作為一種典型的“互聯網+”制造實現模式，云制造通過共享或協同分布式制造資源與能力，快速實現各類產品的定制[1]。企業將自身的制造資源或業務功能進行服務化封裝，發布在各類云平臺，用戶可以按照需求租用云制造服務，彌補自身制造能力的不足，從而便捷地構建和部署新的制造業務。

對于一些復雜的制造需求，云制造服務平臺需要將一組相關的制造服務進行組合，以云制造服務流程的形式實現響應。云平臺中存在許多功能相似的云制造服務，在建立服務組合流程時，每個業務節點都可能存在多個可供選擇的服務，不同的業務節點中的云制造服務之間通過組合，可以產生大量的云制造流程實例[2]。因此，如何從大量的服務組合中求解最優組合流程實例成為云制造領域所面臨的一個難題[3]。

群智能算法是服務組合流程優化的主流解決方法，如遺傳算法（GA,genetic algorithm）[4]、粒子群優化（PSO,particle swarm optimization）算法[5-6]、人工蜂群（ABC,artificial bee colony）算法[7-8]等。為了提高搜索能力和優化質量，研究者在上述算法的基礎上提出了一系列的改進方法，這些方法在組合優化求解過程中已取得不錯效果。然而，已有研究在構建組合優化求解模型時，主要關注服務自身質量屬性，缺乏考慮服務之間的協同質量，此外，在組合流程的尋優質量、效率及穩定性等方面也存在進一步提升的空間。

為此，本文提出一種基于改進人工蜂群算法的云制造服務組合優化方法，主要貢獻如下。

1) 挖掘云制造服務組合場景下的服務協同要素，建立了3 種服務協同質量度量方法，用于評價云制造服務之間的組合關聯強度。

2) 構建了融合云制造服務自身質量與協同質量的組合優化決策模型，提升了云制造服務組合優化的合理性。

3) 設計了一種具有多搜索策略島嶼模型的人工蜂群算法，并將其用于云制造服務組合優化模型的求解。實驗證明所提算法有效提升了組合流程的尋優質量、效率和穩定性。

1 相關工作

服務成本、可靠性、可用性、響應時間等屬性是研究者在構建服務組合優化模型時常考慮的基本要素。例如，考慮到不穩定的QoS 可能會影響服務組合的可靠性，Xie 等[4]通過計算歷史QoS 的偏差值來確定QoS 的穩定性，綜合考慮QoS 穩定性和協作能力來提高服務組合的有效性。Thangaraj 等[9]通過可用性、響應時間、吞吐量和服務之間的互操作性建立組合優化模型評估服務組合的質量，為用戶提供了具有最大吞吐量和互操作性的高可靠性服務組合。

Wang[10]在研究云制造服務組合異常重構時，在傳統服務質量基礎上，將加工質量和服務占用時間等因素作為約束構建優化模型，提出基于強化Harris-Hawks 優化器服務組合重構算法，提高了重構的效率和精確度。任磊等[11]提出了服務合作強度，將其劃分為交易合作關系強度、共同社區強度、物理距離關系強度、資源相關關系強度、社會相似關系強度五類，以傳統服務質量和合作強度的加權最大化為目標構建了服務組合優化模型，提高了流程優化質量。在上述成果的基礎上，本文將進一步挖掘云制造服務組合流程中涉及的協同要素，建立更加科學合理的優化決策模型。

在組合優化模型求解方面，為了解決現有群智能算法在組合優化求解中質量不高、難以兼顧局部與全局最優等問題，研究者從不同角度改進各類算法。例如，Tarawneh 等[12]構建一種蜘蛛猴優化算法，通過使用負載均衡器來分配工作負載，最大限度地減少服務組合的響應時間，很好地平衡虛擬機資源、處理機位置等信息來為用戶推薦最合適的Web 服務。Jin[13]提出一種基于均勻變異和改進鯨魚算法的eagle 搜索策略，利用均勻變異進行全局搜索來保持種群的多樣性，基于改進鯨魚優化算法進行局部搜索，平衡算法的全局和局部搜索能力，提高組合最優解的求解質量。Wu等[14]將花卉授粉算法與快速非支配排序及種群選擇策略相結合，提出一種混合花卉授粉算法，在執行過程引入差分進化策略和隨機干擾策略，提高了服務組合算法的優化能力。

在眾多的群智能算法中，人工蜂群算法因參數少、收斂快、計算簡便等特點在各類優化問題中備受青睞。為提高人工蜂群算法的性能，Zhou 等[15]通過構造精英群體，在雇傭蜂和觀察蜂階段分別改進解搜索方法，并基于精英群體改進鄰域搜索算子，更好地實現探索和開發能力之間的平衡。Arunachalam 等[16]提出了一種基于綜合概率多搜索解決方案的人工蜂群優化方法，能夠有效地確定工作流圖的源頂點和匯頂點之間存在的最佳路徑，利用接受規則和多搜索概率參數來解決服務組合的全局優化。Ye 等[17]提出了一種基于隨機鄰域結構的高效搜索人工蜂群算法，為每個解設計獨立且大小隨機的鄰域結構，并在隨機鄰域結構上改進搜索策略，采用深度優先搜索方法來增強觀察蜂的探索能力，使該算法具有更優的性能。

2 云制造服務組合優化模型

云平臺中存在許多相似的云制造服務，對于服務組合流程，流程中每個節點都存在一組滿足需求的候選服務，形成候選響應服務集合。從每個候選響應服務集合中選擇一個服務，即可組合成為用戶所需的云制造服務流程實例。如圖1 所示，若流程模型包含4 個服務節點，每個節點對應的候選響應服務集合中的服務數目分別為w、x、y和z個，則可形成wxyz種服務組合。

圖1 流程實例優化示意

隨著流程中服務節點數量的增多，可滿足用戶需求的云制造服務組合流程數量將呈指數級增加，這些服務組合流程的質量各異，因此，如何從候選響應服務集合中構建高質量的服務組合流程是云制造流程響應所面臨的一個重要問題。

2.1 組合優化決策要素

在構建服務組合流程時，流程的服務質量包含兩類，一類是組成服務本身所固有的質量屬性，質量屬性在大量服務計算相關研究文獻中均有介紹，不再詳述。本文選取制造周期（MT）、價格（SC）、信譽（SP）、可靠性（SR）參與流程優化。另一類是服務節點之間的協同質量，在構建服務組合流程時，服務之間的歷史合作關系、當前的政策以及遷移代價都會對相鄰服務節點選擇產生影響，從而影響最終服務組合流程的質量。

本文將服務節點之間的協同質量歸結為遷移代價（MC）、合作強度（CI）、合作意向（CP）這三類。由于存在量綱與數值上的差異，所有決策要素的質量求解均采用最大最小歸一化后的屬性值。

1) 遷移代價。不同領域的云制造服務遷移代價度量要素不同，通常情況下，遷移代價主要包含遷移時間、遷移成本和遷移損耗。令mt、mc 和ml分別表示歸一化后的遷移時間、遷移成本和遷移損耗，遷移代價計算方法為。

2) 合作強度。存在合作關系的服務形成了事實上的交互協作，具有服務組合質量上的潛在優勢，再次合作的可能性會更大，因此合作強度是服務關聯質量屬性的重要評估要素。合作強度通常采用合作頻次比來計算，但此類方法忽視了時間對合作強度的影響。同樣的合作頻次比，近期合作次數多的2 個服務的合作強度應該更大，基于上述考慮，本文構建了式(2)所示的合作強度計算方法。

其中，tc 和tk 分別為當前時間段和tk 時間段，Ctk(si,sj)為tk 時間段服務si與sj的合作次數，e-(tc-tk)為時間修正因子，通過tk 與tc 的差值大小來調節不同時間段中的合作次數在合作強度中的貢獻大小。

3) 合作意向。合作意向由歷史合作滿意度和政策扶持度共同決定。歷史合作滿意度高的服務之間通常具備更優的服務組合質量，同時，受國家政策扶持力度大的服務通常具備服務質量上的優勢。歷史合作滿意度hc 和政策扶持度ps 均采用等級分制進行評價。

歷史合作滿意度hc 的評分規則借鑒文獻[18]中的量化規則，將對關聯服務的滿意度劃分為5 個等級，各級賦分為{(非常不滿意：1 分)，(不滿意：3 分)，(基本滿意：5 分)，(滿意：7 分)，(非常滿意：9 分)}。政策扶持度ps 由政策發布單位等級評分和政策類型評分共同決定。依據政策發布單位級別，賦分為{(國家級：4 分)，(省級：3 分)，(市級：2分)，(地區級：1 分)}；依據政策類型，賦分為{(規劃級：3 分)，(條例級：2 分)，(通知級：1 分)}。令hc 和ps 為歸一化后的歷史合作滿意度和政策扶持度，則合作意向為

2.2 組合優化決策模型

為了便于構建云制造服務組合優化決策模型，首先給出云制造服務組合模型的形式化定義。

定義1云制造服務組合模型

云制造服務組合模型定義為二元組csp，csp 及其組成元素規約形式如下

其中，sn 表示流程業務節點，符號→表示順序關系。csp 表示由sn 節點按照順序結構組成的業務邏輯序列。sn 節點分為流程起始節點sb、流程終止節點se、服務節點s和子流程結構塊sp 這4 種類型。其中，s用于描述云制造服務，sp 用于描述流程需求中存在的選擇、并發或循環結構的子流程。

sp 定義為路由節點rn 與服務節點序列sl 的集合，其中sl 為順序執行的服務節點序列；rn 中的節點成對匹配出現，路由節點對{as,aj}、{os,oj}和{ls,le}分別用于構建并發結構、選擇結構和循環結構。圖2 為一個云制造服務組合模型示例，由3 個云制造服務s1，s2和s3以及子流程結構塊sp1組成。sp1是通過路由節點as1和aj1構建的并發流程結構，對應3 個分支流程sl1、sl2和sl3，每個分支均為順序結構的云制造服務節點序列。

圖2 云制造服務組合模型示例

假設服務組合模型csp 中包含起始節點sb、終止節點se、n個服務節點(s1,s2,…,sn)、m個子流程結構塊(sp1,sp2,…,spm)。子流程結構塊spi所包含的服務數量為ui，其組成服務表示為{spi_s1,spi_s2,…,spi_sui}。為了便于計算流程的服務質量，將sb 和se 分別編號為s0和sn+1。

服務組合的4 種流程結構如圖3 所示，循環結構可以看作重復執行的順序結構，因此多數文獻中將循環結構的服務質量求解等價于順序結構，本文也采取類似處理方式。表1 提供了由n個服務節點組成的4 種流程結構的服務質量計算方法，按照表中提供的求解規則，服務組合模型csp 對應的流程質量模型如式(4)～式(8)所示。

圖3 服務組合流程結構

表1 不同流程結構的服務質量計算方法

包含n個服務節點的csp 對應的遷移代價MC、合作強度CI、合作意向CP 的計算方法如式(9)～式(11)所示。

其中，MC(si,si+1)、CI(si,si+1)和CP(si,si+1)分別為服務節點si與si+1之間的遷移代價、合作強度和合作意向，特別地，s0與s1、sn與sn+1之間的上述質量屬性值均設置為0。

服務節點si和si+1之間加入子流程結構塊，將改變MC(si,si+1)、CI(si,si+1)和CP(si,si+1)的值。將m個子流程結構塊融入流程節點s0,s1,s2,…,sn,sn+1，存在如圖4 所示的3 種融入模式。

圖4 子流程結構塊的融入模式

加入并行子流程結構塊后的服務組合之間的協同質量屬性MC、CI 和CP 計算式如式(12)～式(14)所示。其中，每個計算式的第一行對應在起始節點s0與第一個節點之間加入并行子流程結構塊sp1，此時服務協同質量變為sp1中所有服務節點與s1之間的協同服務質量之和。計算式的第二行表示在節點si與si+1之間加入了并行子流程結構塊spk，服務協同質量變為si與spk以及si+1與spk中所有服務節點的協同質量值之和。計算式的第三行表示在最后一個節點sn與終止節點sn+1之間加入并行子流程結構塊sm，服務協同質量變為sn與sm中所有服務節點的協同質量值之和。

加入選擇子流程結構塊后的流程服務之間的協同質量屬性MC、CI 和CP 計算式如式(15)～式(17)所示，計算式中每一行的含義與式(14)～式(16)相同，但由于是選擇結構的子流程結構塊，在進行協同質量處理時不再是匯總求和，而是根據質量屬性的不同，分別取最大值或最小值。

基于融入子流程結構塊后的MC、CI 和CP 計算方法，cps 對應的服務協同質量的QoS 值的計算式為

式(19)為本文基于服務屬性（制造周期MT、價格SC、信譽SP、可靠性SR）和服務協同屬性（遷移代價MC、合作強度CI、合作意向CP）建立起的服務組合流程的質量優化決策模型。

文獻[11]指出，復雜制造業務過程中廣泛存在著資源運輸、信息傳遞和知識共享問題，服務之間也存在社會協作關系，因此，將本文構建的包含遷移代價、合作強度、合作意向3 個要素的協同質量融入組合優化模型中，使優化模型更合理，最終求得的最優流程實例將優于不考慮這些要素的傳統組合優化模型。

3 云制造服務組合優化求解

3.1 標準ABC 算法

設D為問題的維數，SN 為蜜源總量（解空間數量），xi=(xi,1,xi,2,…,xi,D)為一個蜜源（解向量），其中，xi,d為xi的第d維值。xi,d∈(Ld,Hd)，Hd和Ld分別為xi,d的上限和下限，算法迭代次數為CSN，蜜源耗盡上限limit 為SNDc(c為0～1 的參數)。

1) 初始化階段。利用式(20)生成初始蜜源。

每個初始蜜源的蜜源量fiti為

其中，fi為所需解決問題的優化函數。

2) 雇傭蜂階段。利用式(22)更新蜜源，計算蜜源量，用貪婪算法保留較好的蜜源，丟棄較差的蜜源。

其中，xk=(xk,1,xk,2,…,xk,D)為xi的鄰域蜜源，vi,d為蜜源更新后的第d維值，φi,d為值域在[–SF,SF]的均勻分布函數，用于控制xi,d的更新步長，其中SF 為尺度因子，在標準ABC 算法中SF 設置為1。

3) 觀察蜂階段。利用式(23)計算蜜源概率。

其中，NP 為雇傭蜂的總量。根據Pi選擇蜜源對其進行局部搜索，用貪婪算法保留最優解，局部搜索無法提高適應度，計數器trial 加1。

偵查蜂階段。檢查計數器trial 最大的值，若超過蜜源耗盡上限limit，則用式(20)重新生成新蜜源。

在ABC 算法的3 個階段中，雇傭蜂隨機搜索蜜源并把信息分享給觀察蜂，觀察蜂對依據Pi選擇的蜜源進一步搜索，如果蜜源質量得不到提高，雇傭蜂或觀察蜂轉化為偵查蜂進行新蜜源的開采。在這3 個階段中，每種蜜蜂都有其各自的功能，雇傭蜂用來開發新蜜源，觀察蜂用來對優秀蜜源進行進一步探索，偵查蜂用來擺脫局部最優。

3.2 融合多搜索策略島嶼模型的ABC 算法

標準ABC 算法優化求解時，往往存在收斂過早、陷入局部最優等問題。引入島嶼模型，通過多島嶼演化的方式可增加解的多樣性，是解決上述問題的一種有效方法。然而，現有基于島嶼模型的ABC 算法通常在每個島嶼（子種群）中采用相同的搜索方式，獨立尋優的能力有待提高。

為增加種群多樣性和豐富島嶼演化模式，提升ABC 算法的尋優能力，本文設計了一種融合精英種群與最優解指導的搜索策略，并結合其他已有的三類搜索策略，構建了一種融合多搜索策略島嶼模型的ABC 算法（MSSIABC）。在MSSIABC 的島嶼演化中，為每個島嶼隨機選用以下搜索策略。

1) 標準人工蜂群搜索策略。在雇傭蜂階段和觀察蜂階段采用相同的搜索方式，如式(24)所示，該策略雖然局部搜索能力較弱，但其較強的全局搜索能力能提供多樣化的蜜源。

2) 基于精英種群的搜索策略[15]。選取前10%的最優的蜜源作為精英種群，在每次迭代時都計算本次迭代中最優的蜜源，采用更高密度的搜索方式進行尋優，增強局部搜索能力。

其中，φ為0～1 的隨機數；MR 為修正率，用于控制擾動頻率，本文取值為0.5。

3) 融合精英種群與最優解指導的搜索策略。雇傭蜂階段沿用標準ABC 算法搜索式。在觀察蜂階段，搜索式采用式(25)和式(26)，分別采用精英種群和當前全局最優解指導蜜源開發，在每迭代m次后選取前n個優秀蜜源對指導方向進行調整。該策略可有效提升局部搜索能力。

4) 自適應的搜索策略[18]。根據蜜源更新情況，動態改變尋優方向以提高更新成功率、加快算法的收斂速度，在雇傭蜂的搜索階段，當鄰域xk的適應度高于當前蜜源的適應度時，搜索式為

其中，φ為0.95～1.5 的隨機數，步長stepe1為

若低于當前蜜源的適應度，搜索式為

其中，ψ為1.2～1.6 的隨機數，φ為0.5～1.5 的隨機數，步長stepe2為

在觀察蜂階段，鄰域適應度高于當前蜜源的適應度時，搜索式為

其中，φ為–0.45～0.45 的隨機數，步長stepf1為

鄰域適應度低于當前蜜源適應度時，搜索式為

其中，φ為–0.45～0.45 的隨機數，步長stepf2為

基于MSSIABC 的云制造服務組合流程優化求解算法如算法1 所示。

算法1基于MSSIABC 的云制造服務組合流程優化求解算法

輸入組合模型 csp，候選響應服務集合CandiServ，最大迭代次數max_iter,島嶼數量ln,遷移頻率Fm，遷移比例Rm

輸出流程響應集合RespServ，流程服務質量QoS(csp)

步驟1)～步驟4)根據組合模型csp 和候選響應服務集合Candiserv 完成解空間的初始化，構建流程服務質量的適應度函數，然后將解空間劃分為ln個島嶼，并為每個島嶼隨機分配搜索策略。隨后，在算法達到最大迭代次數前，針對每個島嶼循環執行以下處理。

步驟8)～步驟11)執行所在島嶼分配的雇傭蜂階段搜索策略，產生新的解并根據貪婪算法選擇適應度最優的解。步驟12)～步驟19)根據式(25)計算出的Pi選擇觀察蜂階段需要進一步開發的解xi，通過島嶼所對應的搜索方式產生新的解向量，根據貪婪算法選擇適應度更優的解，當解空間的適應度不再提高時，令trial+1，直至trial 達到更新失敗閾值上限limi（t本文取值為20）。步驟20)～步驟28)，當trail 達到limit 時，進入偵查蜂階段開發新解。每迭代Fm 次，將島嶼中適應度最差的Rm 個解向量轉移到相鄰島嶼，直到達到max_iter。

當迭代次數到max_iter 時，步驟30)～步驟32)將島嶼中的最優解xbest及其適應度作為最終的返回結果CSS 和QoS(csp)。

4 實驗

為驗證本文方法在服務組合中的尋優質量、效率和穩定性，構建如圖5 所示的服務組合模型。為測試在不同規模數據的算法性能，數據集1～數據集4 中每個節點的候選響應服務集合中服務數量分別設置為50、100、300 和600。實驗選取近3 年發表論文中的8 種算法進行對比，包含4 種ABC 改進算法和4 種非ABC 類型的群智能算法。取50 次運行結果的平均值確定最終結果，將組合流程中節點屬性設置為相同的權值。

圖5 服務組合模型

在對比不同算法優化得到的流程服務質量時，100次迭代內，每10次迭代監測一次流程服務質量；100～500 次迭代過程中，每100 次迭代監測一次流程服務質量。

圖6～圖9 為4 個數據集下MSSIABC 與4 種ABC 改進算法MGABC[15]（multi-elite guidance artificial bee colony）、MABCM[19]（multi-subpopulations artificial bee colony with memory）、SFABC[20]（self-learning artificial bee colony）、IABC[21]（island artificial bee colony）的迭代次數–服務質量的對比。從 4 個折線圖中可以看出，本文MSSIABC 算法在500 次迭代過程中，在4 個數據集的56 個監測點中，僅有3 個監測點（圖6 迭代次數為30 次時，圖7 迭代次數為20 次時，圖9迭代次數為300 次時）的服務質量與MABCM 重合，其他53 個監測點均高于其他算法優化得到的服務質量，因此，MSSIABC 算法在模型尋優質量上得到明顯提升。

圖6 MSSIABC 與ABC 改進算法在數據集1 中流程優化質量對比

圖7 MSSIABC 與ABC 改進算法在數據集2 中流程優化質量對比

圖8 MSSIABC 與ABC 改進算法在數據集3 中流程優化質量對比

圖9 MSSIABC 與ABC 改進算法在數據集4 中流程優化質量對比

此外，從圖6～圖9 可以看出，相比其他ABC改進算法，MSSIABC 算法能夠在較少迭代輪次內獲得較高的適應度值，收斂速度較快，效率較高。圖10～圖13 為MSSIABC 與非ABC 類群智能算法SCRIHHO[10]（service composition reconfiguration based on harris hawks optimizer ）、IGSA[11]（improved gravitational search algorithm ）、GA-HH[22]（genetic algorithm based hyper-heuristic）、A-NSGA-III[23]（adaptive non-dominated sorting genetic algorithm Ⅲ）的迭代次數–服務質量的對比。在4 個數據集的56 個監測點中，本文MSSIABC 算法均高于其他類型算法獲得的流程服務質量。相比ABC 類算法，非ABC 類算法的求解得到的流程服務質量與MSSIABC 算法的求解得到的流程服務質量差距較大，這說明MSSIABC 算法的尋優能力顯著高于實驗中非ABC 類群智能算法。

圖11 MSSIABC 與其他類型群智能算法在數據集2 中流程優化質量對比

圖12 MSSIABC與其他類型群智能算法在數據集3 中流程優化質量對比

圖13 MSSIABC與其他類型群智能算法在數據集4 中流程優化質量對比

除了擁有較好的尋優能力之外，MSSIABC 算法表現出優秀的穩定性。表2～表5 給出了迭代次數為20 時，各算法在多輪次運行時求得服務流程值的最差值、最優值、平均值和標準差。選擇第20次迭代時的數據做穩定性對比是因為在4 個數據集中，迭代輪次為20 時，流程服務質量對應的折線形態變化均最顯著。

表2 數據集1 中各算法穩定性對比

表3 數據集2 中各算法穩定性對比

表4 數據集3 中各算法穩定性對比

表5 數據集4 中各算法穩定性對比

從表2～表5 中的數據可以看出，與其他8 種算法相比，MSSIABC 在4 個數據集上的最優值均最高，這說明了MSSIABC 的尋優能力優于所有對比算法。從標準差反映的優化穩定性角度來看，MSSIABC 在4 個數據集中的標準差均小于ABC 類對比算法，這說明MSSIABC 提高了ABC 算法的優化穩定性。

與4 種非ABC 類的群智能算法相比，MSSIABC僅在數據集3 中的標準差略高于GA-HH 算法，在其他對比數據集中MSSIABC 均取得了較低的標準差，這也進一步證明了MSSIABC 算法的優化穩定性。

5 結束語

本文提出一種基于改進人工蜂群算法的云制造服務組合優化方法。從遷移代價、合作強度與合作意向3 個方面建立服務協同質量度量方法，構建了融合服務質量與協同質量的服務組合優化決策模型，提升了組合優化的合理性。設計了具有多搜索策略島嶼模型的人工蜂群算法，實驗表明，該算法的組合流程的尋優質量、效率和穩定性均優于對比方法，能有效提升云制造服務組合的優化效果。

后續研究工作將進一步完善組合優化模型中服務協同質量的度量方法，探討島嶼個數與搜索策略之間的關系，以進一步提升云制造服務組合的優化質量、效率和穩定性。