張宏國，陳 陽，馬 超，方 舟，黃 海

(1.哈爾濱理工大學 計算機科學與技術(shù)學院，哈爾濱 150080；2.哈爾濱理工大學 軟件與微電子學院，哈爾濱 150080；3.黑龍江省網(wǎng)絡(luò)空間研究中心，哈爾濱 150001)

0 引 言

面向服務(wù)計算[1](service oriented computing, SOC)是一種實現(xiàn)復雜軟件服務(wù)系統(tǒng)的流行范式。在SOC范式中，復雜軟件服務(wù)系統(tǒng)的業(yè)務(wù)功能被封裝到可互操作的軟件服務(wù)中，并通過標準的發(fā)布，發(fā)現(xiàn)與聚合過程直接重用于新的復雜軟件服務(wù)系統(tǒng)[2]。作為SOC范式的關(guān)鍵方法，服務(wù)聚合是對互聯(lián)網(wǎng)上可用的軟件服務(wù)進行動態(tài)選擇與編排，以按需提供組合軟件服務(wù)[3]。這種組合軟件服務(wù)能夠滿足單個軟件服務(wù)無法滿足的大規(guī)模的、個性化的用戶要求，從而為用戶提供更高的服務(wù)價值。

目前，互聯(lián)網(wǎng)上存在大量功能方面相似但是非功能方面不同的軟件服務(wù)，如何快速發(fā)現(xiàn)和組合這些軟件服務(wù)成為現(xiàn)如今研究的熱點。為了解決這一問題，基于群體智能的啟發(fā)式算法被廣泛應(yīng)用于服務(wù)選擇過程。以遺傳算法[4]、粒子群算法[5]、蟻群算法[6]和人工蜂群算法[7]為代表。其中，人工蜂群[8](artificial bee colony, ABC)算法憑易于理解、應(yīng)用方便等特點，以及在解決連續(xù)數(shù)值優(yōu)化問題時展現(xiàn)的突出性能而受到越來越多的關(guān)注。文[9]利用Sigmoid函數(shù)將任意實數(shù)映射到(0,1)之間，再以一定概率變換為0或1，將經(jīng)典的ABC算法應(yīng)用到二進制離散優(yōu)化問題中，提出了離散型ABC算法。文[10]則利用一系列邏輯運算，改進了離散型ABC算法，將其擴展到一般n值離散化問題。但它們與經(jīng)典的解決連續(xù)域問題的ABC算法一樣，均不適用與解決服務(wù)選擇問題。服務(wù)選擇問題雖然屬于離散域問題，但是離散域的空間巨大，并且多維空間中每一維的元素又是多維的離散值，這無疑增加了問題解決的難度。

目前，已有學者在應(yīng)用ABC算法解決服務(wù)選擇問題方面做了一些研究，并取得一定的研究成果。文[11]為了有效解決服務(wù)選擇問題，引入了一個數(shù)學模型，并采用帶有混沌因子的禁忌策略增強了ABC算法。文[12]介紹了最優(yōu)連續(xù)性概念的定義，并提出了基于閾值的算法(TBA)和基于距離的算法(DBA)。文[13]提出了對ABC算法的一種增強，它使用動態(tài)選擇和替換鄰居。這種選擇和替換過程的目的是平衡算法的探索和開發(fā)機制。

然而，由于當前互聯(lián)網(wǎng)上可用的軟件服務(wù)數(shù)量呈現(xiàn)爆炸性增加的趨勢，導致ABC算法需要搜索的空間越來越大。與此同時，用戶的需求呈現(xiàn)出個性化、動態(tài)化的趨勢，對ABC算法的性能提出了更高的要求。為此，本文提出了一種混合增強ABC算法-HEABC。HEABC算法將K-means算法、KNN算法與ABC算法融合，保證ABC算法在離散解空間更新解時，保持連續(xù)性。進一步地，算法通過增加蜜蜂群體之間信息共享這一能力，增強了蜜蜂群體的探索和開發(fā)能力。最后，通過數(shù)值仿真實驗，驗證了HEABC算法的性能。

1 服務(wù)選擇問題描述

目前，在企業(yè)開發(fā)復雜軟件服務(wù)系統(tǒng)的實踐中，普遍利用互聯(lián)網(wǎng)基礎(chǔ)設(shè)施來集成異構(gòu)平臺上的不同軟件服務(wù)，以實現(xiàn)高效滿足用戶需求這一目標。面向服務(wù)的架構(gòu)[14](service-oriented architecture, SOA)提供了可用于從功能性方面滿足用戶需求的標準解決方案，利用它可以將異構(gòu)平臺上的軟件服務(wù)統(tǒng)一封裝成Web服務(wù)。Web服務(wù)[15]具有可互操作的、松散耦合的、定義良好的和即時集成等特征。

用戶的功能性需求可以采用不同結(jié)構(gòu)的工作流模式表示。針對不同的功能性需求，有4種典型的模式，如圖1所示。在順序模式中，用戶需求按順序被滿足；在并行模式中，某些用戶需求同時被滿足；在條件模式中，某些用戶需求以特定概率P被滿足；在循環(huán)模式中，某些用戶需求可能需要被滿足多次。一般的說，用戶的功能性需求由上述4種模式中的一種或幾種聚合而成，圖2給出了一個包含10個抽象軟件服務(wù)AS的復雜工作流實例。

圖1 工作流模式Fig.1 Workflow patterns

圖2 復雜工作流實例Fig.2 An example of complex workflow

服務(wù)選擇問題的表示有n個抽象軟件服務(wù)，每個抽象軟件服務(wù)都有來自不同服務(wù)提供者的m個具體軟件服務(wù)，這些具體軟件服務(wù)在功能上相似，均可以滿足對應(yīng)的抽象軟件服務(wù)的任務(wù)需求，因此，可能解的個數(shù)等于n×m，如圖3所示。

圖3 服務(wù)選擇問題表示Fig.3 service selection problem representation

如上所述，用戶的功能性需求可以通過綜合利用四種典型的工作流模式，聚合n個抽象軟件服務(wù)來表示，接著針對n個抽象軟件服務(wù)，依次從對應(yīng)的候選集(由m個功能相似的具體軟件服務(wù)構(gòu)成)中隨機選擇一個來實現(xiàn)抽象的軟件服務(wù)，即可完成服務(wù)聚合過程。

但是抽象軟件服務(wù)的候選集中不同的具體軟件服務(wù)可能具有不同的非功能性特征，通過隨機選擇方法構(gòu)成的解決方案可能無法滿足用戶的非功能性需求，為此，需要具體刻畫軟件服務(wù)的非功能性特征。傳統(tǒng)的服務(wù)質(zhì)量[16](quality of service, QoS)語義不足以完全的描述軟件服務(wù)的非功能性需求。為了解決這一問題，本文引入服務(wù)契約[17]這一概念，利用契約條款來更加充分的刻畫軟件服務(wù)的非功能性需求。

如圖4所示，組合軟件服務(wù)(composite software service)由一系列原子軟件服務(wù)(atomic software service)按照一定結(jié)構(gòu)模式聚合而成，它們均具有自己的服務(wù)契約(service contract)。服務(wù)契約由一系列契約條款(contractual terms)組合構(gòu)成。這些契約條款從服務(wù)質(zhì)量QoS、法律領(lǐng)域(legal aspects)、知識產(chǎn)權(quán)(intellectual property)和業(yè)務(wù)領(lǐng)域(business aspects)等4個方面描述軟件服務(wù)的非功能特性。例如，當我們從非功能性方面刻畫一個軟件服務(wù)時，不僅可以從響應(yīng)時間、吞吐量、可靠性等服務(wù)質(zhì)量QoS的角度對其進行描述，還可以從業(yè)務(wù)領(lǐng)域的角度描述軟件服務(wù)的使用價格，從法律領(lǐng)域的角度描述軟件服務(wù)的數(shù)據(jù)安全等級要求。

圖4 服務(wù)契約概念模型Fig.4 Concept model of service contract

綜上所述，為了滿足用戶在服務(wù)契約條款方面的要求，我們從功能性和非功能性方面刻畫了用戶需求和軟件服務(wù)，那么服務(wù)選擇問題就可以定義為針對能夠體現(xiàn)用戶需求的抽象軟件服務(wù)流程，從n×m大小的離散解空間中，選擇最優(yōu)化的解方案。

2 ABC算法

ABC算法[18]由Karaboga等提出，其是模擬蜜蜂覓食行為的群體智能算法。算法包含3個不同階段的搜索過程：在階段1——雇傭階段中，雇傭蜂探索解空間，尋找更好的解；在階段2——跟隨階段中，跟隨蜂等待雇傭蜂探索的解，根據(jù)解的質(zhì)量來選擇跟隨的對象。在前兩個階段中，蜜蜂僅記錄每次迭代中當前的最優(yōu)解。在階段3——偵查階段中，如果搜尋次數(shù)超出預先設(shè)計的閾值后，當前解的質(zhì)量仍未改善，就會派遣偵察蜂來隨機的尋找新的解。

在搜索開始階段，雇傭蜂在食物源周圍根據(jù)式(1)搜索產(chǎn)生新食物源，即

vij=xij+r(xij-xkj)

(1)

其中：xij為當前的可行解，j∈{1,2,3,…,D}為隨機選擇的需要修改的維度，D為解的維度；xkj為隨機選擇的相鄰解，i,k∈{1,2,3,…,S}，S為雇傭蜂的數(shù)量，i≠k；r為[-1,1]的隨機數(shù)。

隨后雇傭蜂計算搜索出食物源的質(zhì)量，當所有跟隨蜂完成式(1)的運算后，會飛回到信息交流區(qū)共享當前的食物源信息，跟隨蜂根據(jù)式(2)選擇跟隨雇傭蜂進行進一步的尋優(yōu)。文[19]在經(jīng)典ABC算法的基礎(chǔ)上提出了一種優(yōu)化的計算食物源選擇被選擇概念的方法，即

(2)

其中：fi為雇傭蜂搜尋出食物源的適應(yīng)度值；fbest為當前種群中適應(yīng)度的最佳值。

隨后跟隨蜂采用與雇傭蜂相同的搜索方式進行鄰域搜索，尋找出新的可行解，并計算其適應(yīng)度值，然后記錄當前找到的最優(yōu)解。雇傭蜂和跟隨蜂進行比較，保留兩個可行解中較好的一個。偵察蜂監(jiān)視雇傭蜂和跟隨蜂的搜索過程，如果迭代的次數(shù)超出了預先設(shè)定的閾值，所得到的當前可行解的質(zhì)量不再有改善，這一可行解將會被放棄，然后雇傭蜂轉(zhuǎn)換成偵察蜂，隨機初始化一個新的解。

在本研究中，我們將K-means算法和KNN算法融合到ABC算法中，在保證更新解的連續(xù)性的情況下，通過賦予蜜蜂共享信息的能力，在蜜蜂之間建立信息共享機制，增加蜂群的探索能力。

3 HEABC算法

對于ABC算法來說，初始種群的優(yōu)劣直接影響算法本身的收斂速度。對于先驗知識匱乏的契約感知服務(wù)選擇問題，初始解分布應(yīng)盡可能均勻[20]。為此，在進行HEABC算法的種群初始化時，本文利用K-means算法對D個候選軟件服務(wù)集進行聚類分析，令K=SN，SN是雇傭峰、跟隨蜂的個數(shù)，也是初始解的個數(shù)，然后從K個類別的子集中依次選取候選食物源作為初始解，以此來保證初始解分布的均勻性。

ABC算法最初是針對連續(xù)域問題而設(shè)計的，然而契約感知服務(wù)選擇是離散域中的優(yōu)化問題。因此，在利用ABC算法求解這一問題時，必須對其進行離散化處理，即HEABC算法是離散型的ABC算法。本文在利用HEABC算法求解契約感知服務(wù)選擇問題時，蜂群從第一個抽象軟件服務(wù)開始并跳轉(zhuǎn)直到它們到達最后一個抽象軟件服務(wù)。在每次跳轉(zhuǎn)時，蜂群將一個具體的軟件服務(wù)添加到解決方案路徑中。在后續(xù)迭代中，蜂群會嘗試提高解決方案質(zhì)量并記錄解決方案未被改善的次數(shù)，如果沒有改進的次數(shù)超過了設(shè)定的閾值，就利用偵查蜂拓展新的解，選擇和替換過程如圖5所示。

圖5 選擇和替換過程示意圖Fig.5 The schematic diagram of selection and replacement process

Pr=Ord(CSi,j,h)/H*Coe

(3)

因為在更新參數(shù)維度時，采用隨機選取的方式會缺乏導向性。所以為了提高HEABC算法的開發(fā)能力，本文增加了種群個體之間進行信息共享的能力，通過計算當前解和從種群中隨機抽取的另一個解間的歐式距離來表征二者之間的差異度。

全局差異度，即兩個解在D維空間上的總體差異度，其計算為

(4)

局部差異度，即兩個解在D維空間中的某一維上的差異度，其計算為

(5)

為了更好的平衡算法的開發(fā)能力和探索能力，本文根據(jù)全局差異度的大小制定更新維度的選取策略。

策略1.當GD≥Th時，對D個LDj進行降序排列，從前一半中隨機選擇一維更新；

策略2.當GD

在設(shè)計契約感知服務(wù)選擇問題的優(yōu)化目標時，我們一方面要考慮法律領(lǐng)域、知識產(chǎn)權(quán)和業(yè)務(wù)領(lǐng)域維度的參數(shù)對優(yōu)化目標的限制，另一方面也要將服務(wù)質(zhì)量QoS維度的參數(shù)兼容進來，下面給出了一個常見的契約感知服務(wù)選擇問題的優(yōu)化目標。

F=(w1g1(RT)+w2g2(T)+w3g3(R))⊕

IsSat(DS)

(6)

其中：RT為響應(yīng)時間；T為吞吐量；R為可靠性；函數(shù)g為對應(yīng)質(zhì)量參數(shù)的歸一化和計算函數(shù)，其根據(jù)質(zhì)量參數(shù)的正負向，以及抽象軟件服務(wù)的邏輯結(jié)構(gòu)不同而不同；權(quán)重w可以采用層析分析法，在與抽樣的用戶進行充分溝通后，進行確定；DS為數(shù)據(jù)安全要求，即某一個具體軟件服務(wù)被聚合時，對方案中其他軟件服務(wù)在數(shù)據(jù)安全等級是哪個的要求；函數(shù)IsSat(DS)的作用是判斷此方面的約束是否被滿足，如未被滿足，則函數(shù)取值為0。

K-means算法和KNN算法的融入，保證了HEABC算法在雇傭蜂階段和跟隨蜂階段更新解時，始終保證連續(xù)性；而種群間信息共享能力的增加，增強了蜜蜂種群對接的探索和開發(fā)能力。HEABC算法偽代碼如下：

輸入：n個抽象軟件服務(wù)集AS=[AS1,AS2,…,ASn]，以及每個抽象軟件服務(wù)ASn下所包含的m個對候選服務(wù)集CS=[CS1,CS2,…,CSm]。

輸出：最優(yōu)解

初始化：種群數(shù)SN，雇傭蜂eb，跟隨蜂ob，偵查蜂sb，最大尋優(yōu)次數(shù)Limits，算法運行次數(shù)Z

Begin

初始化蜂群中所有蜜蜂的參數(shù)

Limit=0

eb=ob=SN/2

sb=SN

均勻地初始化eb

計算適應(yīng)度值

foriter=0→Z-1

fori=1→eb

利用策略1或者2產(chǎn)生一個新的解

利用式(3)保證新解的連續(xù)性

使用式(6)計算新解x’i的適應(yīng)度值

ifF(X’i)

then

Xi=X’i

else

++Limit[i]

end

使用式(2)計算prob[Xi]

end

forj=1→ob

根據(jù)prob[]選擇一個解

利用策略1或者2產(chǎn)生一個新的解

利用式(3)保證新解的連續(xù)性

使用式(6)計算新解X’i的適應(yīng)度值

ifF(X’i)

Then

Xi=X’i

else

++Limit[i]

end

end

fori=1→sb

ifLimit[i]==Limits

then

隨機初始化一個新的sbi

Limit[i]=0

end

end

保留最優(yōu)解

end

返回最優(yōu)解

End

復雜性分析：算法涉及以下運算：初始化，雇傭蜂與跟隨蜂尋優(yōu)，候選服務(wù)集聚類，類別判斷，重新生成候選集，新舊解距離計算，適應(yīng)度計算，偵查蜂初始化。初始化成本為O(SN×N)，其中SN是種群大小，N是抽象軟件服務(wù)數(shù)。雇傭蜂與跟隨蜂搜索成本復雜度為O(Z×SN×N×D)，其中Z是迭代次數(shù)，D是維度。候選服務(wù)集聚類的復雜度為N×O(K)，其中K為聚類的類別數(shù)，且K=SN。類別的判斷消耗成本為N×O(SN)。重新生成候選集消耗的成本為N×O(SN×H)，H為生成相識度最高候選軟件服務(wù)的個數(shù)。適合度計算時間復雜度為O(Z×SN×N×D)。在最壞情況下，每次尋優(yōu)時均達到Limits時，每次均會派遣偵查蜂，派遣偵查蜂的時間復雜度為O(Z×SN)。由上述可得，HEABC算法的時間復雜度為O(SN×N)+O(Z×SN×N)+N×O(K) +N×O(SN×H)+O(Z×SN×N×D)+O(Z×SN)。

4 仿真實驗

實驗環(huán)境是在一臺裝有英特爾i5處理器和Windows 10操作系統(tǒng)的個人電腦上進行的。我們設(shè)計了仿真實驗以驗證算法的有效性，并與文[12]中的TBA算法和文[13]中的EABC算法進行對比。程序是使用JAVA語言實現(xiàn)的，代碼是在文[12]的基礎(chǔ)上做的優(yōu)化。在初始化解時，首先進行了特征聚類，保證算法執(zhí)行過程中得到的解均在離散空間內(nèi)。在執(zhí)行選擇和替換操作時，對候選服務(wù)集提前分類，將候選解分為不同類別的簇，使用KNN算法從對應(yīng)的簇中對解進行隨機替換，保證解的相似性。

4.1 參數(shù)設(shè)置

我們在不同的兩類數(shù)據(jù)集做了仿真。第一種類型的數(shù)據(jù)集有100個web服務(wù)，它們具有不同數(shù)量的任務(wù)，分別是10、20、30、40、50、60、70、80、90和100。第二種數(shù)據(jù)集有10個任務(wù)，每個任務(wù)對應(yīng)不同數(shù)量的候選服務(wù)集，分別是100、200、300、400、500、600、700、800、900和1000。每種類型有60個數(shù)據(jù)集。這些數(shù)據(jù)集是人工生成的，我們將QoS屬性的值定義在[0,1000]范圍內(nèi)。

算法所使用的控制參數(shù)如表1所示，分別為初始化蜂群數(shù)SN、算法的執(zhí)行次數(shù)Z、最大尋優(yōu)次數(shù)Limits、調(diào)和系數(shù)參數(shù)Coe和相識度最高的候選服務(wù)集個數(shù)參數(shù)H。

對于每個數(shù)據(jù)集，實驗共重復30次，以檢測算法對可能影響算法行為的隨機因素的魯棒性。算法的評價指標為最佳解的平均質(zhì)量和平均執(zhí)行時間。

表1 實驗參數(shù)設(shè)置Tab.1 Experimental parameter settings

4.2 實驗結(jié)果

在第一類數(shù)據(jù)集上進行算法驗證，可知該算法對于不同數(shù)量的Web服務(wù)性能進行實驗，可得到的最優(yōu)解對比圖如圖6所示，在Web服務(wù)數(shù)量較少時(0～100之間)，TBA、EABC和HEABC算法在求解質(zhì)量上一致，并無太大的浮動。但是在Web服務(wù)數(shù)量超過100時，TBA的求解質(zhì)量呈下降趨勢，而EABC和HEABC算法波動不大，但在相同條件下，HEABC算法求解質(zhì)量略高于EABC算法。執(zhí)行時間對比圖如圖7所示，TBA算法在求解的執(zhí)行時間呈上升趨勢，EABC和HEABC算法在執(zhí)行時間上保持一致，整體呈下降趨勢。

圖6 算法對不同數(shù)量的Web服務(wù)的性能Fig.6 Algorithms’ performance for different numbers of web services

圖7 算法對不同數(shù)量的Web服務(wù)性能Fig.7 Algorithms’ performance for different numbers of web services

在第二類數(shù)據(jù)集中對算法驗證，可知該算法對于不同數(shù)量的任務(wù)性能進行實驗，可得到的最優(yōu)解對比圖如圖8所示，在保持整體的Web服務(wù)數(shù)相等時，隨著任務(wù)數(shù)的增多TBA求解質(zhì)量呈下降趨勢。HEABC和EABC算法相較于穩(wěn)定，且HEABC算法求解質(zhì)量略高于EABC算法。執(zhí)行時間的對比圖如圖9所示，在保持整體的Web服務(wù)數(shù)相等時，隨著任務(wù)數(shù)的增多3種算法最終的執(zhí)行時間趨近于一致。

圖8 算法對不同數(shù)量的任務(wù)性能Fig.8 Algorithms’ performance for different numbers of tasks

圖9 算法對不同數(shù)量的任務(wù)性能Fig.9 Algorithms’ performance for different numbers of tasks

總的來說，對于不同的數(shù)據(jù)集，HEABC算法雖然在尋優(yōu)的步驟上增加了聚類操作，但由于是并行操作，并未增加過多的時間成本，所以對于求得的最終解，執(zhí)行時間與EABC相差無幾。而在解質(zhì)量上，HEABC算法略優(yōu)于EABC和TBA算法，這是因為通過聚類以及對相似服務(wù)的選擇，增加了蜜蜂群體間信息共享的能力，從而在尋優(yōu)時能保留更好的解。

5 結(jié) 論

為了高效地完成服務(wù)選擇和匹配，本文改進了傳統(tǒng)的人工蜂群算法，對算法蜜源初始化以及蜂群尋優(yōu)兩個方面做了改進。首先通過K-means算法對候選蜜源進行特征聚類，將蜜源分為不同類別的簇，每一部分對應(yīng)著當前類別下的相似解，代表著同一類原子服務(wù)。然后通過KNN算法對每次尋優(yōu)得到最新解進行類別判斷，找到與之對應(yīng)的簇，再次更新解的參數(shù)時，只在其對應(yīng)類別閾值范圍內(nèi)浮動，從而保證了所有解都在離散空間內(nèi)。最終的仿真實驗表明，本文所提的算法在求解質(zhì)量和求解時間上均有所提高，應(yīng)用前景十分廣闊。