基于知識的人工蜂群服務組合優化算法

王 野,周井泉,常瑞云

(南京郵電大學 電子科學與工程學院，江蘇 南京 210003)

基于知識的人工蜂群服務組合優化算法

王 野,周井泉,常瑞云

(南京郵電大學 電子科學與工程學院，江蘇 南京 210003)

近年來，Web服務組合問題一直是研究熱點，是典型的NP難題。隨著Web服務技術的發展，用戶更加注重服務質量。目前，將人工蜂群算法應用于連續性優化問題的研究比較多，然而將其用于解決Web服務組合這一離散化問題卻不多見。為了提高在大量Web服務中快速有效找到針對特定問題的最優Web服務組合的效率，以滿足用戶對服務質量日益提高的需求，文中提出一種基于服務順序知識的人工蜂群算法(KABC)來解決這一NP問題。首先，建立了單個服務的QoS評估模型，并提出了應用于Web服務組合優化問題的QoS數學模型。其次，算法運用當前較優解的服務順序知識來指導后續解的更新，加快了算法的收斂速度，提高了精度。實驗結果表明，與原始的ABC、PSO算法相比較，KABC具有更快、更優的搜索能力以及更好的求解質量。

Web服務組合；NP；人工蜂群算法；知識

0 引 言

在面向服務的計算模式下，網絡中已存的Web服務能夠無縫地組合起來，進而形成新的功能更強的增值服務來滿足用戶日益提高的需求。尤其是在開放動態的Web環境中，如Ad-Hoc，WSN等，需要從海量的候選服務中選擇最優的服務。然而，具有相同功能的服務數量隨著網絡技術的發展而急劇增加，在選擇服務時既要考慮服務功能的方面，還要考慮到服務質量(Quality of Service，QoS)[1]這些非功能性的指標，如服務響應時間、可用性、代價等。候選的Web服務集合之間進行的“爆炸”組合，是一個典型的NP難題[2]。如何從具有不同QoS屬性的高度動態化的服務中，高效率地選擇滿足用戶QoS需求的服務，已成為服務組合中所面臨的一個關鍵難題,具有重要的理論意義和實用價值。

Web服務組合起源于軟件重用，其基本思想是通過已有的Web服務，按照一定的組合邏輯，產生新的或質量更高的服務來滿足用戶需求，實現服務的增值。文獻[3]分析了Web服務組合的概念和實現框架。根據研究側重點及其依賴的技術基礎，將WSC方法歸為兩大類別—基于工作流、狀態演算和進程代數模型描述的過程驅動的組合方法和基于語義描述的自動服務組合方法。

為了解決服務組合這一NP難題，研究者做了大量研究。文獻[4]提出了一種基于OWL-S和HTN的Web服務組合架構，并在此基礎上提出了基于改進的K-means的服務集合算法。該算法依據不同服務之間的關聯，用K-means方法將眾多服務劃分成一些集群，減少了服務的匹配時間，提高了算法的效率。粒子群算法(PSO)具有控制參數少、收斂速度快的優點，但容易受到當前最優解的引導陷入局部收斂。文獻[5]改進了PSO算法，并應用于Web服務組合之中。該算法使用基于粒子圓周軌道和零慣性權重，基于三角函數的動態學習因子，控制粒子群的行為，使粒子的局部認知和全局搜索能力達到較好的平衡。文獻[6]改進了PSO算法并用來解決Web服務選擇問題。該算法采用自適應權值調整和非統一變異策略獲得了較為滿意的結果。人工蜂群算法憑借其算法實現簡單、收斂精度高而得到廣泛的應用。文獻[7]改進了人工蜂群算法，通過引入混沌策略產生新的解來代替面臨丟棄的解，使得算法跳出局部最優解，同時引入禁忌搜索策略避免跟隨蜂的重復搜索，提高了算法的成功率以及搜索效率。

為了進一步提高服務組合問題的求解效果，文中提出一種基于知識的人工蜂群算法(Knowledge-basedArtificialBeeColony，KABC)。通過設計一種針對Web服務組合優化問題的服務順序知識，引導算法后續解的更新，加快算法的收斂速度，并提高精度。實驗結果表明，KABC求解質量優于原始的ABC和PSO算法。

1 Web服務組合問題描述

QoS代表著一個Web服務的非功能屬性。成本(C)、可靠性(R)、響應時間(T)是其中較為重要的三個屬性。一條完整的服務組合路徑主要包含以下三個部分：

子任務：服務組合的基本單元。每一個子任務從它的候選服務中選擇一個Web服務來完成對應的功能。所有子任務完成各自對應的部分功能后，按照用戶的需求組合形成最終的服務。

候選服務：每一個候選服務都有不同的非功能屬性QoS值，其中一些參數由服務提供者給出，另外則由服務使用者提供。同一個子任務下的候選服務具有相同的功能，即都能完成該子任務，但各自的QoS屬性值不同。

服務組合：組合服務由不同子任務選出的候選服務按照一定的邏輯或者拓撲組合而成。組合后的服務具有更強大的功能，滿足用戶更高的需求。組合服務的整體QoS值可由候選服務按照相互組合結構計算獲得。

Web服務有四種基本結構(見圖1)：順序結構(a)、循環結構(b)、并行結構(c)和選擇結構(d)。

在順序結構中，任務按照先后順序依次執行；在循環結構中，一個任務將被循環執行許多次；在并行結構中，所有的并行任務可以同時執行，但是只有所有的并行任務都執行完畢才可進行接下來的任務；在選擇結構中，每一個子任務都能完成需求的功能，并且只要有一個分支任務執行完成就可繼續向下執行后續任務。

圖1 Web服務組合四種基本結構

因為組合Web服務是由上述四種基本結構組成，因此一個結構確定的服務組合的QoS可以通過對應基本結構的QoS屬性計算獲得。四種結構的成本(C)、可靠性(R)、響應時間(T)計算公式如下：

(1)

(2)

(3)

其中：n是任務數目；k是循環次數；pi是選擇結構中分支的選擇概率。

這些QoS指標中有的是值越大越好，如可靠性，稱為效益型指標，屬于正指標。相反地，成本、響應時間則是成本型指標，屬于負指標。

為了能夠統一計算，需要對各個QoS指標值進行標準化處理。公式如下：

正指標(可靠性)：

(4)

負指標(成本、響應時間)：

(5)

其中：Q是原始QoS屬性值；Qstand是標準化后QoS屬性值。

標準化之后，將其他三種組合結構轉化為順序結構[8]，從而簡化計算。因此，基于QoS的Web服務組合計算模型定義如下：

(6)

其中，ω表示各個屬性的權值，且ω1+ω2+ω3=1。

2 算法描述

近年來，越來越多的研究者開始探索智能優化算法迭代過程中演化與學習之間的聯系。在求解Web服務組合問題時，可以利用優化過程中準最優解的相關知識，然后用獲得的知識來指導后續的優化過程。

基于上述理念，文中提出一種基于服務順序知識的人工蜂群算法來解決Web服務組合問題。

2.1 服務順序知識

文獻[9]提出了一種弧段順序知識(Arc Priority Knowledge，APK)，用以描述所需弧段之間順序的一種累積知識。在求解Web服務組合優化問題時，經常要考慮相鄰的兩條服務弧段之間的關聯。為了有效利用該關聯信息，文中以弧段順序知識為基礎，提出了服務順序知識。和弧段順序知識相比，其不同點在于：文中根據組合問題的子任務數以及每個子任務下候選服務的數目來限定記錄服務順序知識矩陣的行和列的大小。假設子任務數是n，每個子任務的候選服務數是m。僅考慮相鄰兩個子任務之間的服務順序知識，那么每個解(維度為n)都有n-1段服務順序，記錄一個服務順序所需要的矩陣大小為m×m，因此總的計數矩陣大小為(n-1)m×m。

服務順序知識的抽取：按照如下方式從已獲得的準最優解中抽取弧段順序知識。對于任意一個新生成的組合方案，將它插入到當前的種群中，然后將種群中所有的方案按照適應度值的大小由高到低排列。如果新生成的方案處于種群的前20%，則采用新方案來更新服務順序知識。例如，新生成的組合方案順序是2→4→1→3，那么新方案中出現了三個服務序列(2，4)，(4，1)和(1，3)。將服務序列(2，4)，(4，1)和(1，3)在計數矩陣出現的次數分別增加1次。

服務順序知識的應用：為了防止更新后的準最優解在算法后續的更新過程中遭到破壞，使用服務順序知識指導后續的解更新。若某服務序列在已獲得準最優解中出現的次數非常多，那么在下一輪的迭代過程中則以較小的概率選擇該服務進行更新；反之，則以較大概率破壞該服務序列。

假設服務順序知識如表1所示。當前的個體為2→4→1→3，則服務序列為(2，4)，(4，1)，(1，3)，在準最優解中出現的次數分別為11，16和8，在服務序列(2，4)，(4，1)，(1，3)之間選擇更新的概率分別為37.50%、6.25%和56.25%。計算方法為：將三條服務順序出現的次數11、16和8取相反數得-11、-16和-8，然后加上一個最小正整數17使得相反數變為正數6、1和9，最后除以三個數之和16得到服務順序更新概率分別為37.50%、6.25%和56.25%。

表1 服務順序知識

2.2 人工蜂群算法

人工蜂群算法[10]是Karaboga于2005年提出的一種模擬蜂群覓食行為的群體智能優化算法。對比其他智能算法，該算法控制參數少、易于實現，受到眾多學者的關注。

在ABC算法中，有三種分工不同的蜜蜂，分別是引領蜂、跟隨蜂和偵察蜂。引領蜂是負責探索優質蜜源并進行初步鄰域搜索的蜜蜂，數量和蜜源數量相等；跟隨蜂根據引領蜂傳遞蜜源信息，有選擇地對蜜源進行鄰域搜索，跟隨蜂數量與引領蜂數量相等；偵察蜂則是進行全局隨機搜索，防止漏掉質量更高的其他蜜源。每只蜜蜂都對應一個解，引領蜂代表當前種群的現有解；跟隨蜂代表潛在的鄰域搜索解；偵察蜂則代表全局隨機搜索解。

一個蜜源的位置代表優化問題一個可能的解，解的適應度用花蜜的質量表示。首先，ABC算法隨機生成含有SN個解的初始種群。每個解xi(i=1,2,…,SN)是一個D維的向量。然后，引領蜂先對對應的食物源(解)進行一次鄰域搜索，并選擇花蜜數量多也就是適應度較高的食物源(解)。跟隨蜂按照概率選擇食物源。花蜜越多的食物源，被選擇的概率越大。跟隨蜂會對被選中的蜜源進行一次鄰域搜索，并選擇較優的解。跟隨蜂按照概率值pi選擇食物源，計算表達式如下：

(7)

其中，fitnessi是第i個解的適應度。

引領蜂和跟隨蜂按照式(8)進行鄰域搜索[11]：

vij=xij+rand(xij-xkj)

(8)

其中：k∈{1,2,…,D},j∈{1,2,…,D}，k和j都是隨機選取的，但是k不能等于i；rand是-1和1之間的隨機數。

如果某個解經過limit次循環之后仍然沒有得到改善，那么這個解就要被舍棄掉。假定丟掉的解是xi，那么就由偵察蜂按照式(9)產生一個新的解來代替xi。

(9)

2.3 基于知識的人工蜂群算法解決Web服務組合

應用KABC算法求解Web服務組合優化問題，首先要解決的是蜂群的初始化。假設服務組合共包含n個子任務，每個子任務待選的Web服務個數都是10，那么每個待選子服務可用WSij(C,R,T)表示。其中，i為子任務的編號，j為完成該子任務的候選服務的編號。設定蜂群的每個成員(解)代表一條服務組合路徑，用向量X=[x1,x2,…,xn]表示[12]，解的維度與服務組合問題的子任務數一致。舉例來說，服務組合路徑WS15→WS26→WS39→WS40→…→WSn7可以用X=[5,6,9,0,…,7]來表示。

然后是適應度值fitness(X)的計算問題。根據解X=[5,6,9,0,…,7]各個維度的編號讀取每個已選服務的成本、可靠性和響應時間三維QoS屬性值。按組合問題的組合結構(順序、循環、并行和選擇)，結合式(1)、(2)、(3)和(6)計算求得該解對應的適應度值。同時，無論引領蜂、跟隨蜂還是偵察蜂對應的解都是一個整型向量X，并且只有解的適應度值得到了提高，算法才會對現有的解進行更新，所以必須對解的更新機制進行整形化。具體公式如下：

vij=xij+[rand(xij-xkj)+0.5]

(10)

其中，[]是取整符號。

KABC算法應用于Web服務組合問題具體步驟描述如下：

步驟1：設置相關參數。引領蜂個數=跟隨蜂個數=SN，最大迭代次數為MCN，控制參數為limit。

步驟2：初始化蜂群。隨機產生SN個蜜源X，并計算適應度值fitness(X)。

步驟3：引領蜂按式(10)進行鄰域搜索，并根據新舊蜜源的適應度值采取“貪婪原則”進行選擇。

步驟4：若當前迭代次數小于MCN*20%，則轉向步驟5，否則運用已獲得的弧段順序知識選擇引領蜂合適的弧段進行更新。

步驟5：根據式(7)計算各蜜源被選擇的概率，跟隨蜂采用“輪盤賭”原則進行選擇，并按式(10)進行鄰域搜索。

步驟6：若當前迭代次數小于MCN*20%，則轉向步驟7，否則運用已獲得的弧段順序知識選擇引領蜂合適的弧段進行更新。

步驟7：若某蜜源經過limit次迭代適應度值仍未得到改善，則與之對應的引領蜂轉為偵察蜂，即重新生成蜜源。

步驟8：從已獲得的準最優解中抽取弧段順序知識，記錄在矩陣中。

步驟9：記錄目前最優蜜源，若當前迭代次數小于最大迭代次數MCN，轉向步驟3進行下一次迭代，否則輸出最優解作為優選結果。

3 實驗分析

鑒于目前還沒有統一的實驗平臺以及相關數據集[13]，本實驗所采用的是隨機生成各個Web服務QoS的三維屬性值，每一維對應的權重都是1/3。實驗中服務組合的子任務數是20，每個子任務的候選服務數是100。由上文可知，服務順序知識矩陣的規模應是1 900×100。實驗環境為聯想G490，Intel(R)Core(TM)i5-3230MCPU@ 2.60GHz,4GBRAM,Windows8,VC6.0。

為了驗證KABC算法的有效性，選取原始的ABC、PSO算法作為比較對象[14]。設置最大迭代次數MCN=100，種群規模NP=200，limit=100。考慮到智能算法的隨機性，每次實驗運行100次，記錄算法求解的最大值、最小值、平均值和中間值。

圖2為原始ABC、PSO以及KABC算法求得的解的平均適應度值隨迭代次數增加而變化的過程。

圖2 算法平均適應度值演變趨勢

由圖可知，從第20次迭代開始引入服務順序知識以后，KABC算法可以迅速將解的適應度值提高到一個更高的數值，增強了算法的精搜能力。在求解過程中，KABC的平均適應度值始終優于其他兩種算法，這說明基于知識的ABC算法更加適合解決復雜的服務組合問題，與理論預期相符。

圖3為三種算法運行100次，所得解的適應度的最大值、最小值、平均值和中間值的對比情況。

圖3 算法運行100次數據統計

對比柱狀圖，在運行次數同為100、最大迭代次數同為100的情況下，KABC算法在適應度最大值、最小值、平均值、中間值都大于其他算法，并且4個值之間的差距很小，說明該算法的穩定性更好。

4 結束語

文中給出了Web服務的QoS屬性的評估模型以及數學計算模型。通過引入服務順序知識，改進了ABC算法并用來解決Web服務組合優化問題。實驗結果證明了KABC算法的有效性和可行性。然而，基于知識的ABC算法的尋優能力以及適應大規模服務組合問題的能力也有待加強。這些將是后續研究工作的重點。

[1]ZengL,BenatallahB,NguAH,etal.Qos-awaremiddlewareforwebservicescomposition[J].IEEETransactionsonSoftwareEngineering,2004,30(5):311-327.

[2]WoegingerGJ.ExactalgorithmsforNP-hardproblems:asurvey[M]//JungerM.CombinatorialOptimization.Berlin:Springer,2003:185-207.

[3] 倪晚成,劉連臣,吳 澄.Web服務組合方法綜述[J].計算機工程,2008,34(4):79-81.

[4]TangX,TangF,BingL,etal.DynamicwebservicecompositionbasedonserviceintegrationandHTNplanning[C]//Procof2013seventhinternationalconferenceoninnovativemobileandinternetservicesinubiquitouscomputing.[s.l.]:[s.n.],2013:307-312.

[5] 溫 濤,盛國軍,郭 權,等.基于改進粒子群算法的Web服務組合[J].計算機學報,2013,36(5):1031-1046.

[6]HuCH,ChenXH,LiangXM.DynamicservicesselectionalgorithminWebservicescompositionsupportingcross-enterprisescollaboration[J].JournalofCentralSouthUniversityofTechnology,2009,16(2):269-274.

[7]HeJ,ChenL,WangX,etal.Webservicecompositionoptimizationbasedonimprovedartificialbeecolonyalgorithm[J].JournalofNetworks,2013,8(9):2143-2149.

[8]WangP.QoS-awarewebservicesselectionwithintuitionisticfuzzysetunderconsumer’svagueperception[J].ExpertSystemswithApplications,2009,36:4460-4466.

[9] 姚 鋒,邢立寧,李菊芳,等.求解雙層CARP優化問題的知識型遺傳算法[J].系統工程理論與實踐,2014,34(1):239-247.

[10]KarabogaD,BasturkB.Apowerfulandefficientalgorithmfornumericalfunctionoptimization:ArtificialBeeColony(ABC)algorithm[J].JournalofGlobalOptimization,2007,39(3):459-471.

[11]KarabogaD,GorkemliB,OzturkC,etal.Acomprehensivesurvey:ArtificialBeeColony(ABC)algorithmandapplications[J].ArtificialIntelligenceReview,2012,42(1):21-57.

[12]ZhaoX,SongB,HuangP,etal.AnimproveddiscreteimmuneoptimizationalgorithmbasedonPSOforQoS-drivenwebservicecomposition[J].AppliedSoftComputing,2012,12:2208-2216.

[13]Al-HelalH,GambleR.Introducingreplaceabilityintowebservicecomposition[J].IEEETransactionsonServicesComputing,2014,7(2):198-209.

[14]TaoF,LaiLiY,XuL,etal.FC-PACO-RM:aparallelmethodforservicecompositionoptimal-selectionincloudmanufacturingsystem[J].IEEETransactionsonIndustrialInformatics,2013,9(4):2023-2033.

Artificial Bee Colony Algorithm for Service Composition Based on Knowledge

WANG Ye，ZHOU Jing-quan，CHANG Rui-yun

(College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Web service composition,as a NP hard problem,has always been a hot research in recent years.With the development of Web service technology,users pay more attention to quality of service.Many researches on Artificial Bee Colony (ABC) are carried out to solve continuous optimization problems.It is rare for using ABC to tackle the Web Service Composition Problem (WSCP) of discrete optimization.In order to improve the efficiency of finding the best service composition,a Knowledge-based Artificial Bee Colony (KABC) algorithm is proposed and applied to WSCP.Firstly,the QoS model of a single Web service and mathematics model of a service composition are built.Secondly,the knowledge of service sequence of the high quality solutions is used to guide the updating of next generation solutions,so as to accelerate the convergence speed and improve the precision of solutions.Experiment shows that compared with original ABC and PSO,KABC has a better performance on WSCP.

Web service composition;NP;artificial bee colony;knowledge

2015-07-27

2015-11-05

時間：2016-05-05

國家自然科學基金資助項目(61401225)

王 野(1991-)，男，碩士研究生，研究方向為服務組合優化問題；周井泉，博士，教授，碩士生導師，研究方向為通信網絡的信息管理和控制。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0817.054.html

TP301.6

A

1673-629X(2016)05-0046-05

10.3969/j.issn.1673-629X.2016.05.010