基于知識的人工蜂群服務(wù)組合優(yōu)化算法

王 野,周井泉,常瑞云

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

基于知識的人工蜂群服務(wù)組合優(yōu)化算法

王 野,周井泉,常瑞云

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

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

Web服務(wù)組合；NP；人工蜂群算法；知識

0 引 言

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

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

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

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

1 Web服務(wù)組合問題描述

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

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

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

服務(wù)組合：組合服務(wù)由不同子任務(wù)選出的候選服務(wù)按照一定的邏輯或者拓?fù)浣M合而成。組合后的服務(wù)具有更強大的功能，滿足用戶更高的需求。組合服務(wù)的整體QoS值可由候選服務(wù)按照相互組合結(jié)構(gòu)計算獲得。

Web服務(wù)有四種基本結(jié)構(gòu)(見圖1)：順序結(jié)構(gòu)(a)、循環(huán)結(jié)構(gòu)(b)、并行結(jié)構(gòu)(c)和選擇結(jié)構(gòu)(d)。

在順序結(jié)構(gòu)中，任務(wù)按照先后順序依次執(zhí)行；在循環(huán)結(jié)構(gòu)中，一個任務(wù)將被循環(huán)執(zhí)行許多次；在并行結(jié)構(gòu)中，所有的并行任務(wù)可以同時執(zhí)行，但是只有所有的并行任務(wù)都執(zhí)行完畢才可進(jìn)行接下來的任務(wù)；在選擇結(jié)構(gòu)中，每一個子任務(wù)都能完成需求的功能，并且只要有一個分支任務(wù)執(zhí)行完成就可繼續(xù)向下執(zhí)行后續(xù)任務(wù)。

圖1 Web服務(wù)組合四種基本結(jié)構(gòu)

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

(1)

(2)

(3)

其中：n是任務(wù)數(shù)目；k是循環(huán)次數(shù)；pi是選擇結(jié)構(gòu)中分支的選擇概率。

這些QoS指標(biāo)中有的是值越大越好，如可靠性，稱為效益型指標(biāo)，屬于正指標(biāo)。相反地，成本、響應(yīng)時間則是成本型指標(biāo)，屬于負(fù)指標(biāo)。

為了能夠統(tǒng)一計算，需要對各個QoS指標(biāo)值進(jìn)行標(biāo)準(zhǔn)化處理。公式如下：

正指標(biāo)(可靠性)：

(4)

負(fù)指標(biāo)(成本、響應(yīng)時間)：

(5)

其中：Q是原始QoS屬性值；Qstand是標(biāo)準(zhǔn)化后QoS屬性值。

標(biāo)準(zhǔn)化之后，將其他三種組合結(jié)構(gòu)轉(zhuǎn)化為順序結(jié)構(gòu)[8]，從而簡化計算。因此，基于QoS的Web服務(wù)組合計算模型定義如下：

(6)

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

2 算法描述

近年來，越來越多的研究者開始探索智能優(yōu)化算法迭代過程中演化與學(xué)習(xí)之間的聯(lián)系。在求解Web服務(wù)組合問題時，可以利用優(yōu)化過程中準(zhǔn)最優(yōu)解的相關(guān)知識，然后用獲得的知識來指導(dǎo)后續(xù)的優(yōu)化過程。

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

2.1 服務(wù)順序知識

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

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

服務(wù)順序知識的應(yīng)用：為了防止更新后的準(zhǔn)最優(yōu)解在算法后續(xù)的更新過程中遭到破壞，使用服務(wù)順序知識指導(dǎo)后續(xù)的解更新。若某服務(wù)序列在已獲得準(zhǔn)最優(yōu)解中出現(xiàn)的次數(shù)非常多，那么在下一輪的迭代過程中則以較小的概率選擇該服務(wù)進(jìn)行更新；反之，則以較大概率破壞該服務(wù)序列。

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

表1 服務(wù)順序知識

2.2 人工蜂群算法

人工蜂群算法[10]是Karaboga于2005年提出的一種模擬蜂群覓食行為的群體智能優(yōu)化算法。對比其他智能算法，該算法控制參數(shù)少、易于實現(xiàn)，受到眾多學(xué)者的關(guān)注。

在ABC算法中，有三種分工不同的蜜蜂，分別是引領(lǐng)蜂、跟隨蜂和偵察蜂。引領(lǐng)蜂是負(fù)責(zé)探索優(yōu)質(zhì)蜜源并進(jìn)行初步鄰域搜索的蜜蜂，數(shù)量和蜜源數(shù)量相等；跟隨蜂根據(jù)引領(lǐng)蜂傳遞蜜源信息，有選擇地對蜜源進(jìn)行鄰域搜索，跟隨蜂數(shù)量與引領(lǐng)蜂數(shù)量相等；偵察蜂則是進(jìn)行全局隨機搜索，防止漏掉質(zhì)量更高的其他蜜源。每只蜜蜂都對應(yīng)一個解，引領(lǐng)蜂代表當(dāng)前種群的現(xiàn)有解；跟隨蜂代表潛在的鄰域搜索解；偵察蜂則代表全局隨機搜索解。

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

(7)

其中，fitnessi是第i個解的適應(yīng)度。

引領(lǐng)蜂和跟隨蜂按照式(8)進(jìn)行鄰域搜索[11]：

vij=xij+rand(xij-xkj)

(8)

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

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

(9)

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

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

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

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

(10)

其中，[]是取整符號。

KABC算法應(yīng)用于Web服務(wù)組合問題具體步驟描述如下：

步驟1：設(shè)置相關(guān)參數(shù)。引領(lǐng)蜂個數(shù)=跟隨蜂個數(shù)=SN，最大迭代次數(shù)為MCN，控制參數(shù)為limit。

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

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

步驟4：若當(dāng)前迭代次數(shù)小于MCN*20%，則轉(zhuǎn)向步驟5，否則運用已獲得的弧段順序知識選擇引領(lǐng)蜂合適的弧段進(jìn)行更新。

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

步驟6：若當(dāng)前迭代次數(shù)小于MCN*20%，則轉(zhuǎn)向步驟7，否則運用已獲得的弧段順序知識選擇引領(lǐng)蜂合適的弧段進(jìn)行更新。

步驟7：若某蜜源經(jīng)過limit次迭代適應(yīng)度值仍未得到改善，則與之對應(yīng)的引領(lǐng)蜂轉(zhuǎn)為偵察蜂，即重新生成蜜源。

步驟8：從已獲得的準(zhǔn)最優(yōu)解中抽取弧段順序知識，記錄在矩陣中。

步驟9：記錄目前最優(yōu)蜜源，若當(dāng)前迭代次數(shù)小于最大迭代次數(shù)MCN，轉(zhuǎn)向步驟3進(jìn)行下一次迭代，否則輸出最優(yōu)解作為優(yōu)選結(jié)果。

3 實驗分析

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

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

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

圖2 算法平均適應(yīng)度值演變趨勢

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

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

圖3 算法運行100次數(shù)據(jù)統(tǒng)計

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

4 結(jié)束語

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

[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服務(wù)組合方法綜述[J].計算機工程,2008,34(4):79-81.

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

[5] 溫 濤,盛國軍,郭 權(quán),等.基于改進(jìn)粒子群算法的Web服務(wù)組合[J].計算機學(xué)報,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優(yōu)化問題的知識型遺傳算法[J].系統(tǒng)工程理論與實踐,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

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

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

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