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

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

0 引 言

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

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

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

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

1 服務選擇問題描述

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

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

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

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

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

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

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

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

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

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

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

2 ABC算法

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

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

vij=xij+r(xij-xkj)

(1)

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

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

(2)

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

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

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

3 HEABC算法

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

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

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

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

(3)

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

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

(4)

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

(5)

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

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

策略2.當GD

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

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

IsSat(DS)

(6)

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

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

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

輸出：最優(yōu)解

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

Begin

初始化蜂群中所有蜜蜂的參數

Limit=0

eb=ob=SN/2

sb=SN

均勻地初始化eb

計算適應度值

foriter=0→Z-1

fori=1→eb

利用策略1或者2產生一個新的解

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

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

ifF(X’i)

then

Xi=X’i

else

++Limit[i]

end

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

end

forj=1→ob

根據prob[]選擇一個解

利用策略1或者2產生一個新的解

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

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

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)，候選服務集聚類，類別判斷，重新生成候選集，新舊解距離計算，適應度計算，偵查蜂初始化。初始化成本為O(SN×N)，其中SN是種群大小，N是抽象軟件服務數。雇傭蜂與跟隨蜂搜索成本復雜度為O(Z×SN×N×D)，其中Z是迭代次數，D是維度。候選服務集聚類的復雜度為N×O(K)，其中K為聚類的類別數，且K=SN。類別的判斷消耗成本為N×O(SN)。重新生成候選集消耗的成本為N×O(SN×H)，H為生成相識度最高候選軟件服務的個數。適合度計算時間復雜度為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)的個人電腦上進行的。我們設計了仿真實驗以驗證算法的有效性，并與文[12]中的TBA算法和文[13]中的EABC算法進行對比。程序是使用JAVA語言實現的，代碼是在文[12]的基礎上做的優(yōu)化。在初始化解時，首先進行了特征聚類，保證算法執(zhí)行過程中得到的解均在離散空間內。在執(zhí)行選擇和替換操作時，對候選服務集提前分類，將候選解分為不同類別的簇，使用KNN算法從對應的簇中對解進行隨機替換，保證解的相似性。

4.1 參數設置

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

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

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

表1 實驗參數設置Tab.1 Experimental parameter settings

4.2 實驗結果

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

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

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

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

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

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

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

5 結 論

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