基于改進人工蜂群算法的云制造服務(wù)組合優(yōu)化方法

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

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

0 引言

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

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

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

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

1) 挖掘云制造服務(wù)組合場景下的服務(wù)協(xié)同要素，建立了3 種服務(wù)協(xié)同質(zhì)量度量方法，用于評價云制造服務(wù)之間的組合關(guān)聯(lián)強度。

2) 構(gòu)建了融合云制造服務(wù)自身質(zhì)量與協(xié)同質(zhì)量的組合優(yōu)化決策模型，提升了云制造服務(wù)組合優(yōu)化的合理性。

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

1 相關(guān)工作

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

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

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

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

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

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

圖1 流程實例優(yōu)化示意

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

2.1 組合優(yōu)化決策要素

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

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

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

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

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

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

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

2.2 組合優(yōu)化決策模型

為了便于構(gòu)建云制造服務(wù)組合優(yōu)化決策模型，首先給出云制造服務(wù)組合模型的形式化定義。

定義1云制造服務(wù)組合模型

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

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

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

圖2 云制造服務(wù)組合模型示例

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

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

圖3 服務(wù)組合流程結(jié)構(gòu)

表1 不同流程結(jié)構(gòu)的服務(wù)質(zhì)量計算方法

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

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

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

圖4 子流程結(jié)構(gòu)塊的融入模式

加入并行子流程結(jié)構(gòu)塊后的服務(wù)組合之間的協(xié)同質(zhì)量屬性MC、CI 和CP 計算式如式(12)～式(14)所示。其中，每個計算式的第一行對應(yīng)在起始節(jié)點s0與第一個節(jié)點之間加入并行子流程結(jié)構(gòu)塊sp1，此時服務(wù)協(xié)同質(zhì)量變?yōu)閟p1中所有服務(wù)節(jié)點與s1之間的協(xié)同服務(wù)質(zhì)量之和。計算式的第二行表示在節(jié)點si與si+1之間加入了并行子流程結(jié)構(gòu)塊spk，服務(wù)協(xié)同質(zhì)量變?yōu)閟i與spk以及si+1與spk中所有服務(wù)節(jié)點的協(xié)同質(zhì)量值之和。計算式的第三行表示在最后一個節(jié)點sn與終止節(jié)點sn+1之間加入并行子流程結(jié)構(gòu)塊sm，服務(wù)協(xié)同質(zhì)量變?yōu)閟n與sm中所有服務(wù)節(jié)點的協(xié)同質(zhì)量值之和。

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

基于融入子流程結(jié)構(gòu)塊后的MC、CI 和CP 計算方法，cps 對應(yīng)的服務(wù)協(xié)同質(zhì)量的QoS 值的計算式為

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

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

3 云制造服務(wù)組合優(yōu)化求解

3.1 標準ABC 算法

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

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

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

其中，fi為所需解決問題的優(yōu)化函數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，φ為0.95～1.5 的隨機數(shù)，步長stepe1為

若低于當前蜜源的適應(yīng)度，搜索式為

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

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

其中，φ為–0.45～0.45 的隨機數(shù)，步長stepf1為

鄰域適應(yīng)度低于當前蜜源適應(yīng)度時，搜索式為

其中，φ為–0.45～0.45 的隨機數(shù)，步長stepf2為

基于MSSIABC 的云制造服務(wù)組合流程優(yōu)化求解算法如算法1 所示。

算法1基于MSSIABC 的云制造服務(wù)組合流程優(yōu)化求解算法

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

輸出流程響應(yīng)集合RespServ，流程服務(wù)質(zhì)量QoS(csp)

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

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

當?shù)螖?shù)到max_iter 時，步驟30)～步驟32)將島嶼中的最優(yōu)解xbest及其適應(yīng)度作為最終的返回結(jié)果CSS 和QoS(csp)。

4 實驗

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

圖5 服務(wù)組合模型

在對比不同算法優(yōu)化得到的流程服務(wù)質(zhì)量時，100次迭代內(nèi)，每10次迭代監(jiān)測一次流程服務(wù)質(zhì)量；100～500 次迭代過程中，每100 次迭代監(jiān)測一次流程服務(wù)質(zhì)量。

圖6～圖9 為4 個數(shù)據(jù)集下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）的迭代次數(shù)–服務(wù)質(zhì)量的對比。從 4 個折線圖中可以看出，本文MSSIABC 算法在500 次迭代過程中，在4 個數(shù)據(jù)集的56 個監(jiān)測點中，僅有3 個監(jiān)測點（圖6 迭代次數(shù)為30 次時，圖7 迭代次數(shù)為20 次時，圖9迭代次數(shù)為300 次時）的服務(wù)質(zhì)量與MABCM 重合，其他53 個監(jiān)測點均高于其他算法優(yōu)化得到的服務(wù)質(zhì)量，因此，MSSIABC 算法在模型尋優(yōu)質(zhì)量上得到明顯提升。

圖6 MSSIABC 與ABC 改進算法在數(shù)據(jù)集1 中流程優(yōu)化質(zhì)量對比

圖7 MSSIABC 與ABC 改進算法在數(shù)據(jù)集2 中流程優(yōu)化質(zhì)量對比

圖8 MSSIABC 與ABC 改進算法在數(shù)據(jù)集3 中流程優(yōu)化質(zhì)量對比

圖9 MSSIABC 與ABC 改進算法在數(shù)據(jù)集4 中流程優(yōu)化質(zhì)量對比

此外，從圖6～圖9 可以看出，相比其他ABC改進算法，MSSIABC 算法能夠在較少迭代輪次內(nèi)獲得較高的適應(yīng)度值，收斂速度較快，效率較高。圖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 Ⅲ）的迭代次數(shù)–服務(wù)質(zhì)量的對比。在4 個數(shù)據(jù)集的56 個監(jiān)測點中，本文MSSIABC 算法均高于其他類型算法獲得的流程服務(wù)質(zhì)量。相比ABC 類算法，非ABC 類算法的求解得到的流程服務(wù)質(zhì)量與MSSIABC 算法的求解得到的流程服務(wù)質(zhì)量差距較大，這說明MSSIABC 算法的尋優(yōu)能力顯著高于實驗中非ABC 類群智能算法。

圖11 MSSIABC 與其他類型群智能算法在數(shù)據(jù)集2 中流程優(yōu)化質(zhì)量對比

圖12 MSSIABC與其他類型群智能算法在數(shù)據(jù)集3 中流程優(yōu)化質(zhì)量對比

圖13 MSSIABC與其他類型群智能算法在數(shù)據(jù)集4 中流程優(yōu)化質(zhì)量對比

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

表2 數(shù)據(jù)集1 中各算法穩(wěn)定性對比

表3 數(shù)據(jù)集2 中各算法穩(wěn)定性對比

表4 數(shù)據(jù)集3 中各算法穩(wěn)定性對比

表5 數(shù)據(jù)集4 中各算法穩(wěn)定性對比

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

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

5 結(jié)束語

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

后續(xù)研究工作將進一步完善組合優(yōu)化模型中服務(wù)協(xié)同質(zhì)量的度量方法，探討島嶼個數(shù)與搜索策略之間的關(guān)系，以進一步提升云制造服務(wù)組合的優(yōu)化質(zhì)量、效率和穩(wěn)定性。