胡強(qiáng)，田雨晴，綦浩泉，吳鵬，劉慶雪

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

0 引言

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

對(duì)于一些復(fù)雜的制造需求，云制造服務(wù)平臺(tái)需要將一組相關(guān)的制造服務(wù)進(jìn)行組合，以云制造服務(wù)流程的形式實(shí)現(xiàn)響應(yīng)。云平臺(tái)中存在許多功能相似的云制造服務(wù)，在建立服務(wù)組合流程時(shí)，每個(gè)業(yè)務(wù)節(jié)點(diǎn)都可能存在多個(gè)可供選擇的服務(wù)，不同的業(yè)務(wù)節(jié)點(diǎn)中的云制造服務(wù)之間通過(guò)組合，可以產(chǎn)生大量的云制造流程實(shí)例[2]。因此，如何從大量的服務(wù)組合中求解最優(yōu)組合流程實(shí)例成為云制造領(lǐng)域所面臨的一個(gè)難題[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ǔ)上提出了一系列的改進(jìn)方法，這些方法在組合優(yōu)化求解過(guò)程中已取得不錯(cuò)效果。然而，已有研究在構(gòu)建組合優(yōu)化求解模型時(shí)，主要關(guān)注服務(wù)自身質(zhì)量屬性，缺乏考慮服務(wù)之間的協(xié)同質(zhì)量，此外，在組合流程的尋優(yōu)質(zhì)量、效率及穩(wěn)定性等方面也存在進(jìn)一步提升的空間。

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 標(biāo)準(zhǔn)ABC 算法

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

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

每個(gè)初始蜜源的蜜源量fiti為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，φ為0.95～1.5 的隨機(jī)數(shù)，步長(zhǎng)stepe1為

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

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

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

其中，φ為–0.45～0.45 的隨機(jī)數(shù)，步長(zhǎng)stepf1為

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

其中，φ為–0.45～0.45 的隨機(jī)數(shù)，步長(zhǎng)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個(gè)島嶼，并為每個(gè)島嶼隨機(jī)分配搜索策略。隨后，在算法達(dá)到最大迭代次數(shù)前，針對(duì)每個(gè)島嶼循環(huán)執(zhí)行以下處理。

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

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

4 實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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