基于全局QoS約束分解與關(guān)聯(lián)感知的動(dòng)態(tài)服務(wù)組合

侯占偉，翟海霞，沈記全

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

0 引 言

隨著云計(jì)算、物聯(lián)網(wǎng)等信息技術(shù)的快速發(fā)展，越來(lái)越多的Web服務(wù)共享在網(wǎng)絡(luò)上，由于單個(gè)服務(wù)不能滿(mǎn)足用戶(hù)的復(fù)雜業(yè)務(wù)需求，將網(wǎng)絡(luò)上可用的服務(wù)聚合成功能強(qiáng)大的組合服務(wù)是實(shí)現(xiàn)服務(wù)增值的關(guān)鍵技術(shù)。如何高效地從大規(guī)模功能相同而QoS不同的候選服務(wù)中選出具有全局最優(yōu)服務(wù)質(zhì)量的服務(wù)是服務(wù)組合過(guò)程中需解決的關(guān)鍵技術(shù)問(wèn)題。

很多學(xué)者在基于QoS感知的Web服務(wù)組合方法上做了大量的研究，并取得一定的研究成果。基于QoS的服務(wù)組合是一個(gè)組合優(yōu)化方面的NP難題[1]，主要采用群體智能算法、進(jìn)化算法或數(shù)學(xué)規(guī)劃方法對(duì)該優(yōu)化問(wèn)題進(jìn)行求解，這些方法缺乏一定的靈活性，在候選服務(wù)規(guī)模增加時(shí)算法的時(shí)間復(fù)雜度也會(huì)明顯增加。為了提高服務(wù)組合的靈活性，將全局QoS約束自適應(yīng)地分解為局部約束，目前采用的方法有基于模糊邏輯的自適應(yīng)粒子群優(yōu)化算法[2]，考慮組件服務(wù)的效用、組合模式進(jìn)行約束分解方法[3-4]，以預(yù)測(cè)服務(wù)的QoS閾值進(jìn)行全局QoS分解方法[5]，采用改進(jìn)遺傳人工蜂群算法、文化遺傳算法等提高服務(wù)組合性能[6-7]，結(jié)合用戶(hù)特征和訪問(wèn)服務(wù)偏好進(jìn)行服務(wù)選擇[8]。但這些方法在全局QoS約束分解時(shí)沒(méi)有考慮QoS之間的關(guān)聯(lián)關(guān)系。在基于服務(wù)間關(guān)聯(lián)的服務(wù)組合方法有通過(guò)擴(kuò)展的服務(wù)建模來(lái)描述服務(wù)間的相關(guān)性[9]，構(gòu)建支持服務(wù)間質(zhì)量依賴(lài)關(guān)系及語(yǔ)義關(guān)聯(lián)服務(wù)選取的QoS模型[10-11]，通過(guò)支持任務(wù)間關(guān)聯(lián)關(guān)系的服務(wù)重選算法[12]、支持相關(guān)感知服務(wù)的剪枝算法[13]，基于遺傳算法的相關(guān)感知服務(wù)選擇[14]，結(jié)合服務(wù)間相關(guān)性，采用擴(kuò)展花授粉算法獲得最優(yōu)服務(wù)組合[15]。但在實(shí)際服務(wù)組合過(guò)程中，這些方法沒(méi)有考慮上下游組合服務(wù)之間的動(dòng)態(tài)關(guān)聯(lián)性。

本文通過(guò)分析上下游組合服務(wù)之間的關(guān)聯(lián)性，提出一種基于全局QoS約束分解與關(guān)聯(lián)感知的動(dòng)態(tài)優(yōu)化服務(wù)組合方法。采用改進(jìn)的人工蜂群算法進(jìn)行全局QoS約束分解，在服務(wù)組合過(guò)程中，動(dòng)態(tài)結(jié)合上下游服務(wù)之間的QoS關(guān)聯(lián)關(guān)系進(jìn)行服務(wù)選擇，保證了服務(wù)選擇的準(zhǔn)確性，解決了存在關(guān)聯(lián)關(guān)系的服務(wù)組合問(wèn)題。

1 Web服務(wù)動(dòng)態(tài)組合問(wèn)題描述

Web服務(wù)動(dòng)態(tài)優(yōu)化組合問(wèn)題是指在服務(wù)組合過(guò)程中，根據(jù)用戶(hù)功能需求及QoS約束，動(dòng)態(tài)地選擇最優(yōu)候選服務(wù)進(jìn)行組合，在滿(mǎn)足用戶(hù)的任務(wù)要求情況下使構(gòu)建的組合服務(wù)的QoS全局最優(yōu)。組合服務(wù)CWS={S1,S2,…Sn}由n個(gè)服務(wù)類(lèi)組成，服務(wù)類(lèi)Si包含多個(gè)功能相同但QoS不同的候選服務(wù)，其中Si={Si1,Si2,…,Sik}，表示服務(wù)類(lèi)Si有k個(gè)候選服務(wù)。動(dòng)態(tài)Web服務(wù)優(yōu)化組合是在大量的候選服務(wù)中選擇一組滿(mǎn)足用戶(hù)需求的最優(yōu)候選服務(wù)進(jìn)行組合。

1.1 組合服務(wù)的評(píng)價(jià)函數(shù)

設(shè)在一個(gè)順序結(jié)構(gòu)服務(wù)組合中，CS={S1,S2,…,Sn}表示該服務(wù)組合n個(gè)任務(wù)節(jié)點(diǎn)的候選服務(wù)集，候選服務(wù)sjt為服務(wù)類(lèi)Sj中的一個(gè)候選服務(wù)，SCl={s1,s2,…,sjt,…,sut}為一個(gè)服務(wù)組合方案；那么，單個(gè)服務(wù)sjt與組合服務(wù)SCl的QoS效用函數(shù)U(sjt)和U(SCl)可以通過(guò)(1)式和(2)式計(jì)算得到。

(1)

(2)

同時(shí)，

Qmin(j,k)=min?sj,i∈Sjqk(sji)

(3)

Qmax(j,k)=max?sj,i∈Sjqk(sji)

(4)

(5)

(6)

1.2 全局QoS約束分解模型

全局QoS約束分解是指在服務(wù)組合過(guò)程中，按照用戶(hù)的功能需求和QoS約束，將組合流程中服務(wù)類(lèi)的全局QoS約束分成若干個(gè)局部取值區(qū)間，為每類(lèi)服務(wù)找到滿(mǎn)足局部取值區(qū)間要求的最優(yōu)候選服務(wù)，使得滿(mǎn)足局部QoS約束要求的候選服務(wù)組合同樣滿(mǎn)足全局QoS約束。如果僅考慮滿(mǎn)足局部最優(yōu)約束分解的方法進(jìn)行服務(wù)選擇，可能出現(xiàn)組合失敗的情況；把全局約束分解為局部約束后，可以保證滿(mǎn)足局部約束的服務(wù)組合一定滿(mǎn)足全局約束，提高了服務(wù)組合的效率和成功率。

文獻(xiàn)[17]將上述的離散的局部QoS取值區(qū)間定義為質(zhì)量標(biāo)尺(quality level)，并提出了一種基于質(zhì)量標(biāo)尺的QoS分解方法，如圖1所示。

首先，初始化質(zhì)量標(biāo)尺，圖1中，Qjab(1≤a≤m,1≤b≤k)為候選服務(wù)Sja的第b個(gè)屬性的QoS，Ljxy(1≤x≤d,1≤y≤k)為第y個(gè)質(zhì)量標(biāo)尺的第x個(gè)離散數(shù)值。將每一個(gè)服務(wù)類(lèi)Sj中的k個(gè)QoS屬性分解為k個(gè)質(zhì)量標(biāo)尺，每個(gè)質(zhì)量標(biāo)尺的離散數(shù)值Ljdk滿(mǎn)足關(guān)系Qmin(j,k)≤Ljd1≤…≤Ljdk≤Qmax(j,k)。

其次，構(gòu)建最優(yōu)Web服務(wù)的質(zhì)量標(biāo)尺組合評(píng)價(jià)模型，不但要保證滿(mǎn)足要求的候選服務(wù)數(shù)量較多，同時(shí)還要保證滿(mǎn)足組合要求的候選服務(wù)的評(píng)價(jià)值較大。服務(wù)組合質(zhì)量標(biāo)尺評(píng)價(jià)公式為

(7)

2 基于改進(jìn)人工蜂群算法的全局QoS約束分解方法

2.1 改進(jìn)的人工蜂群算法

人工蜂群算法(artificial bee colony algorithm，ABC)是由D.Karaboga在2009年提出的一種新穎的群集智能優(yōu)化算法[18]，并將其原理成功地應(yīng)用到函數(shù)的數(shù)值優(yōu)化問(wèn)題。算法模擬蜜蜂群體尋找優(yōu)質(zhì)蜜源的過(guò)程，把蜜蜂分為引領(lǐng)蜂、跟隨蜂和偵察蜂3種角色[19]，其中，引領(lǐng)蜂負(fù)責(zé)全局搜索，跟隨蜂負(fù)責(zé)局部搜索，偵察蜂則負(fù)責(zé)處理進(jìn)化停滯的個(gè)體，利用3種蜜蜂間的協(xié)作分工及信息交流共享，來(lái)實(shí)現(xiàn)對(duì)最優(yōu)蜜源的搜索，從而找到問(wèn)題的最優(yōu)解。

根據(jù)服務(wù)組合問(wèn)題中服務(wù)之間存在有關(guān)聯(lián)關(guān)系這一特性，本文提出一種改進(jìn)的人工蜂群(improved artificial bee colony， I-ABC)算法來(lái)解決服務(wù)組合全局QoS約束分解問(wèn)題。

1)改進(jìn)的初始食物源生成方法。生成初始解。設(shè)定食物源的規(guī)模為SN，根據(jù)服務(wù)組合執(zhí)行的歷史記錄，從每個(gè)候選服務(wù)的非功能性屬性中隨機(jī)選擇一個(gè)常用的屬性值；首先生成第一個(gè)解，產(chǎn)生其余解時(shí)需先查詢(xún)服務(wù)關(guān)聯(lián)數(shù)據(jù)集，然后從與已生成解存在有關(guān)聯(lián)關(guān)系的數(shù)據(jù)集中隨機(jī)選擇常用的屬性值，組成初始食物源S={S1,S2,…,Si,…,SN}，如圖2所示。

圖2 生成N個(gè)初始解Fig.2 Generate N initial solutions

2)改進(jìn)的雇傭蜂階段。進(jìn)行解的鄰域交叉變換，如圖3所示。首選隨機(jī)選擇一個(gè)解Si，在服務(wù)關(guān)聯(lián)數(shù)據(jù)集中查詢(xún)與Si存在有關(guān)聯(lián)的解并隨機(jī)選擇一個(gè)解Sj，0≤i,j≤n。然后將隨機(jī)選擇的Si，Sj2個(gè)解對(duì)應(yīng)列進(jìn)行交換后得到2個(gè)新解Si′和Sj′。計(jì)算并比較Si，Sj、Si′和Sj′ 4個(gè)解的評(píng)價(jià)值，保留評(píng)價(jià)值最優(yōu)的解。

圖3 解的交叉變換Fig.3 Cross transformation of the solution

圖4 解的變異Fig.4 Variation of the solution

4)最優(yōu)解保留操作。采用(3)式對(duì)當(dāng)前解的集合S={S1,S2,…,Si,…,SN}依次計(jì)算其評(píng)價(jià)值，然后進(jìn)行評(píng)價(jià)比較，將評(píng)價(jià)值最高的解保留在最優(yōu)解BS中。

2.2 基于I-ABC的最優(yōu)服務(wù)組合求解算法

在本文提出的改進(jìn)人工蜂群算法求解全局QoS約束分解的方法中，我們?cè)诔跏冀獾纳?、鄰域搜索變換等階段時(shí)考慮解組合服務(wù)之間的關(guān)聯(lián)關(guān)系，這樣更加符合服務(wù)組合的實(shí)際情況，有利于縮短最優(yōu)解的尋優(yōu)時(shí)間，提高最優(yōu)解的生成效率。同時(shí)，在復(fù)雜的網(wǎng)絡(luò)環(huán)境中進(jìn)行服務(wù)組合，動(dòng)態(tài)的根據(jù)環(huán)境的變化可將服務(wù)的全局約束分解按照實(shí)際的服務(wù)需求進(jìn)行全局優(yōu)化，實(shí)現(xiàn)動(dòng)態(tài)的服務(wù)組合。

下面給出基于I-ABC算法求服務(wù)組合最優(yōu)解的過(guò)程描述。

算法1基于I-ABC的最優(yōu)服務(wù)組合求解算法。

輸入：組合服務(wù)類(lèi)的數(shù)量；QoS全局約束；候選服務(wù)QoS值；QoS質(zhì)量標(biāo)尺；最大迭代次數(shù)MCN；解的數(shù)量SN；用戶(hù)約束及偏好；控制參數(shù)limit。

輸出：最優(yōu)質(zhì)量標(biāo)尺組合。

步驟1確定候選服務(wù)集合。

IF(Si不屬于集合QRS)//在服務(wù)關(guān)聯(lián)數(shù)據(jù)集QRS中進(jìn)行解的搜索；

選擇候選服務(wù)Sj并判斷否屬于QRS；

Endif

步驟2初始化階段。

Set parameterslimit,MCN,SN,counteri//設(shè)置循環(huán)次數(shù)、迭代次數(shù)、解的數(shù)量、更新次數(shù)；

For i=1 toSN

產(chǎn)生SN個(gè)食物源(解)并保留最優(yōu)解；

Endfor

步驟3雇傭蜂操作過(guò)程。

For i=1 toSN//對(duì)每一個(gè)食物源

進(jìn)行解的鄰域搜索變換，并保留最優(yōu)解；

If(當(dāng)前的食物源質(zhì)量沒(méi)有改變)

counteri=counteri+1

Endif

Endfor

步驟4觀察蜂操作過(guò)程。

For i=1 toSN//對(duì)每一個(gè)食物源

Endfor

For i=1 toSN//對(duì)每一個(gè)食物源

利用輪盤(pán)賭方式選擇新解并進(jìn)行解的鄰域搜索變換，保留最優(yōu)解；

If(當(dāng)前的食物源質(zhì)量沒(méi)有改變)

counteri=counteri+1

Endif

Endfor

步驟5偵查蜂操作過(guò)程。

For i=1 toSN

If(limit大于給定值后，解未更新或者解的評(píng)價(jià)值降低)

進(jìn)行解的變異操作，評(píng)價(jià)保留最優(yōu)解。

Endif

Endfor

步驟6判斷算法是否結(jié)束。

If(達(dá)到最大迭代次數(shù)MCN)

輸出最優(yōu)解BS并停止計(jì)算；

Else //沒(méi)有到達(dá)結(jié)束的條件

迭代次數(shù)增加一次，返回步驟3。

改進(jìn)的人工蜂群算法的流程如圖5所示。

圖5 改進(jìn)的人工蜂群算法流程圖Fig.5 Improved ABC flow chart

3 基于QoS關(guān)聯(lián)感知的服務(wù)優(yōu)化選擇方法

3.1 候選服務(wù)QoS值的確定

在進(jìn)行服務(wù)選擇時(shí)，考慮上下游服務(wù)之間的QoS關(guān)聯(lián)性，首先通過(guò)對(duì)服務(wù)歷史數(shù)據(jù)的分析和挖掘來(lái)構(gòu)建服務(wù)關(guān)聯(lián)數(shù)據(jù)集。針對(duì)候選服務(wù)之間存在的關(guān)聯(lián)服務(wù)質(zhì)量變化情況，定義服務(wù)間的QoS相關(guān)性，若為負(fù)相關(guān)，相關(guān)服務(wù)的QoS值會(huì)因QoS相關(guān)性的存在而減??；若為正相關(guān)，相關(guān)服務(wù)的QoS值會(huì)因QoS相關(guān)性的存在而增大。將候選服務(wù)參與服務(wù)組合的實(shí)際QoS值與其服務(wù)本身的QoS值之間的比例關(guān)系定義為服務(wù)關(guān)聯(lián)系數(shù)，該系數(shù)能夠精確表達(dá)某一候選服務(wù)在服務(wù)組合中局部約束的QoS實(shí)際值，從而使全局QoS約束的分解能夠與服務(wù)的實(shí)際運(yùn)行情況保持一致，提高Web服務(wù)動(dòng)態(tài)優(yōu)化組合中服務(wù)選擇的準(zhǔn)確度和組合效率。

定義1服務(wù)關(guān)聯(lián)數(shù)據(jù)集(QoS related set, QRS)，在服務(wù)組合中

(8)

(8)式中：1≤i,j≤n，(si,sj,…)為服務(wù)關(guān)聯(lián)組合單元；(qsi,qsj，…)為對(duì)應(yīng)該服務(wù)關(guān)聯(lián)組合單元的QoS屬性聚合值；n為組合服務(wù)節(jié)點(diǎn)個(gè)數(shù)；QRS稱(chēng)為服務(wù)關(guān)聯(lián)數(shù)據(jù)集。

定義2服務(wù)關(guān)聯(lián)關(guān)系(QoS relationship, QR)，在服務(wù)組合中

(9)

(9)式中：si,sj為服務(wù)關(guān)聯(lián)數(shù)據(jù)集中的候選服務(wù)；QR(si,sj)稱(chēng)為服務(wù)關(guān)聯(lián)關(guān)系。當(dāng)QR(si,sj)的值為1時(shí)，稱(chēng)服務(wù)(si,sj)正相關(guān)，當(dāng)QR(si,sj)的值為0時(shí)，稱(chēng)服務(wù)(si,sj)不相關(guān)，當(dāng)QR(si,sj)的值為-1時(shí)，稱(chēng)服務(wù)(si,sj)負(fù)相關(guān)。

定義3服務(wù)關(guān)聯(lián)系數(shù)(QoS related coefficient,QRC)，在服務(wù)組合中

(10)

(10)式中：Qsi為服務(wù)si的QoS屬性值；qsi為在服務(wù)關(guān)聯(lián)數(shù)據(jù)集中服務(wù)si的QoS實(shí)際值；QRC(si)稱(chēng)為候選服務(wù)si對(duì)應(yīng)的服務(wù)關(guān)聯(lián)系數(shù)，用于計(jì)算服務(wù)組合中具體服務(wù)的QoS實(shí)際值。

在執(zhí)行過(guò)程中，判斷已選服務(wù)si和當(dāng)前候選服務(wù)sj之間的關(guān)聯(lián)關(guān)系，若為負(fù)相關(guān)，則丟棄當(dāng)前候選服務(wù)，若為正相關(guān)，當(dāng)前候選服務(wù)QoS的值為Qsj·QRC(sj)。

在實(shí)際的商業(yè)運(yùn)行中，不同領(lǐng)域的服務(wù)之間具有一定的關(guān)聯(lián)關(guān)系，比如協(xié)約關(guān)聯(lián)關(guān)系、統(tǒng)計(jì)關(guān)聯(lián)關(guān)系等，服務(wù)之間這種關(guān)聯(lián)關(guān)系是客觀存在的。導(dǎo)致具有關(guān)聯(lián)關(guān)系的服務(wù)在運(yùn)行時(shí)，表現(xiàn)出不同的QoS值。因此，在進(jìn)行服務(wù)選擇時(shí)，需要考慮上下游之間的服務(wù)是否存在關(guān)聯(lián)關(guān)系。支持服務(wù)關(guān)聯(lián)關(guān)系的QoS評(píng)價(jià)模型能夠更加客觀的評(píng)價(jià)服務(wù)在不同情況下所表現(xiàn)出的服務(wù)質(zhì)量有助于選出更加合適的服務(wù)，進(jìn)而提高服務(wù)動(dòng)態(tài)組合的質(zhì)量。

3.2 基于關(guān)聯(lián)的服務(wù)選擇過(guò)程

在Web服務(wù)選擇時(shí)，利用質(zhì)量標(biāo)尺將Web服務(wù)組合的全局QoS約束分解為局部QoS約束，局部約束給出了候選服務(wù)的服務(wù)質(zhì)量上限或下限。考慮上下游服務(wù)之間的關(guān)聯(lián)性，在動(dòng)態(tài)的選擇候選服務(wù)時(shí)，首先查找關(guān)聯(lián)數(shù)據(jù)集中是否和已選服務(wù)存在關(guān)聯(lián)關(guān)系，選擇過(guò)程如圖6所示。

圖6 考慮QoS關(guān)聯(lián)的服務(wù)選擇過(guò)程示意圖Fig.6 QoS-related service selection process

基于QoS關(guān)聯(lián)的Web服務(wù)動(dòng)態(tài)組合服務(wù)過(guò)程如下。

步驟1選擇第一個(gè)候選服務(wù)。從候選服務(wù)集S1={S11,S12,…S1l}中隨機(jī)選擇滿(mǎn)足局部約束CS1的候選服務(wù)(CSk為對(duì)應(yīng)任務(wù)Ti的局部QoS約束，1≤k≤m，m為服務(wù)組合任務(wù)總數(shù))。

步驟2選擇的關(guān)聯(lián)候選服務(wù)。對(duì)于候選服務(wù)Si(2≤i≤m)，首先動(dòng)態(tài)查找服務(wù)關(guān)聯(lián)數(shù)據(jù)集QRS，判斷與已選定的候選服務(wù)Si-1是否存在有關(guān)聯(lián)關(guān)系；若存在有關(guān)聯(lián)，且關(guān)聯(lián)關(guān)系QR(Si,Si-1)值為1，則選擇當(dāng)前服務(wù)質(zhì)量滿(mǎn)足約束條件為QRC(si-1)·CSi-1的候選服務(wù)。

步驟3選擇最優(yōu)Web服務(wù)組合。重復(fù)步驟2的過(guò)程，利用評(píng)價(jià)公式計(jì)算所選服務(wù)組合的評(píng)價(jià)值并進(jìn)行比較，選擇評(píng)價(jià)值最高的一組服務(wù)組合即為最優(yōu)Web服務(wù)組合。

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

本實(shí)驗(yàn)采用Java編程語(yǔ)言實(shí)現(xiàn)基于I-ABC的全局QoS約束優(yōu)化分解算法以及考慮QoS關(guān)聯(lián)關(guān)系的服務(wù)優(yōu)化選擇方法。其中，質(zhì)量標(biāo)尺數(shù)量設(shè)置為d=25；改進(jìn)人工蜂群算法中的交叉率設(shè)為0.85，變異率設(shè)為0.05。算法運(yùn)行環(huán)境為個(gè)人計(jì)算機(jī)，CPU為Intel 酷睿i5 7 500，內(nèi)存為4 GByte，操作系統(tǒng)為Windows 7。

為驗(yàn)證本文方法的有效性，實(shí)驗(yàn)過(guò)程設(shè)計(jì)如下：服務(wù)組合由10個(gè)服務(wù)節(jié)點(diǎn)組成，每個(gè)服務(wù)類(lèi)有n個(gè)候選服務(wù)(200≤n≤800)；設(shè)用戶(hù)提出了4個(gè)全局QoS約束：①價(jià)格<120元(人民幣)，②響應(yīng)時(shí)間<150 s，③成功率>0.5，④信譽(yù)度>0.6。每個(gè)服務(wù)類(lèi)的QoS屬性質(zhì)量標(biāo)尺數(shù)為d，假定4個(gè)QoS屬性偏好分別為0.3，0.4，0.2和0.1；10個(gè)任務(wù)節(jié)點(diǎn)所對(duì)應(yīng)組合服務(wù)類(lèi)的QoS取值如表1所示。

表1 QoS屬性的取值區(qū)間

每個(gè)候選服務(wù)的QoS屬性在相應(yīng)的區(qū)間內(nèi)隨機(jī)生成。這里通過(guò)隨機(jī)的方法確定具有QoS關(guān)聯(lián)關(guān)系的服務(wù)，具有QoS關(guān)聯(lián)關(guān)系的服務(wù)之間的關(guān)聯(lián)QoS值的取值方式為：成功率與信譽(yù)度是上下游服務(wù)這2個(gè)QoS屬性聚合值的1.2倍，價(jià)格與響應(yīng)時(shí)間是上下游服務(wù)這2個(gè)QoS屬性聚合值的2/3。

首先，利用本文所提出的改進(jìn)人工蜂群算法將用戶(hù)的全局QoS約束分解為滿(mǎn)足要求的局部QoS約束；然后，在服務(wù)優(yōu)化組合時(shí)，最優(yōu)服務(wù)的選擇是在考慮候選服務(wù)上下游之間的關(guān)聯(lián)關(guān)系對(duì)組合Web服務(wù)QoS的影響的情況下，基于所構(gòu)建的服務(wù)關(guān)聯(lián)數(shù)據(jù)集完成的。

4.2 算法性能比較與分析

為了驗(yàn)證本文所提出的I-ABC算法在求解全局QoS約束分解問(wèn)題時(shí)的有效性，該實(shí)驗(yàn)分別采用遺傳算法(genetic algorithm, GA)、粒子群算法(particle swarm optimization, PSO)及I-ABC 3種方法對(duì)4.1節(jié)所設(shè)計(jì)的實(shí)驗(yàn)對(duì)象進(jìn)行求解，其中，3種算法的初始群體規(guī)模設(shè)置為50，遺傳算法的交叉概率設(shè)置為0.85，變異率設(shè)置為0.05；粒子群算法2個(gè)學(xué)習(xí)因子設(shè)置為2。實(shí)驗(yàn)結(jié)果如圖7所示。其中，橫坐標(biāo)表示3種算法的迭代次數(shù)；縱坐標(biāo)表示3種算法在求解全局QoS約束分解問(wèn)題時(shí)獲得解的評(píng)價(jià)值。從圖7可以看出，改進(jìn)的人工蜂群算法在求解全局QoS約束分解問(wèn)題時(shí)，具有較好的性能。

圖7 I-ABC算法全局QoS約束分解性能比較Fig.7 Performance comparison of I-ABC algorithm for global QoS constraint decomposition

在性能分析比較實(shí)驗(yàn)中設(shè)置了迭代次數(shù)為50，100，150，200，250，300，350，400情況下3種算法的性能比較，從實(shí)驗(yàn)結(jié)果可以看出，迭代次數(shù)越多，算法在求解全局QoS約束分解問(wèn)題時(shí)獲得解的評(píng)價(jià)值越高，算法執(zhí)行花費(fèi)的時(shí)間代價(jià)也越大。通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以看出，問(wèn)題的求解時(shí)間較短，能夠滿(mǎn)足服務(wù)動(dòng)態(tài)優(yōu)化組合對(duì)時(shí)效性的要求。

4.3 算法有效性驗(yàn)證

為進(jìn)一步驗(yàn)證本文提出的基于QoS全局約束分解與關(guān)聯(lián)感知的動(dòng)態(tài)服務(wù)組合算法(該方法記為GQDQCC)的有效性，該實(shí)驗(yàn)首先應(yīng)用本文所提出的方法對(duì)4.1節(jié)所設(shè)計(jì)的實(shí)驗(yàn)對(duì)象進(jìn)行了求解，采用離散型人工蜂群算法在保證全局最優(yōu)的情況下對(duì)同一個(gè)服務(wù)組合問(wèn)題求解(該方法記為ABCSC)。在該實(shí)驗(yàn)中，人工蜂群算法的初始食物源規(guī)模設(shè)為100，Limit值設(shè)置為15。實(shí)驗(yàn)結(jié)果如圖8所示，圖8中的橫坐標(biāo)表示服務(wù)組合算法的運(yùn)行時(shí)間(單位：s)，縱坐標(biāo)表示服務(wù)組合算法搜索最優(yōu)服務(wù)組合的評(píng)價(jià)值。

從圖8可以看出，本文所提出的算法在服務(wù)組合過(guò)程中，根據(jù)服務(wù)之間的關(guān)聯(lián)關(guān)系構(gòu)建了服務(wù)關(guān)聯(lián)關(guān)系數(shù)據(jù)庫(kù)，縮小了候選服務(wù)的搜索范圍，提高了搜索效率，能夠在較短的時(shí)間內(nèi)能夠找到較優(yōu)的服務(wù)組合。因此，本文所提出的基于全局QoS約束分解與QoS關(guān)聯(lián)感知的服務(wù)動(dòng)態(tài)優(yōu)化組合方法是有效的。

圖8 服務(wù)動(dòng)態(tài)優(yōu)化組合性能驗(yàn)證Fig.8 Dynamic optimization method for service performance verification

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

本文定義了一種支持服務(wù)關(guān)聯(lián)關(guān)系的QoS評(píng)價(jià)模型，運(yùn)用改進(jìn)的人工蜂群算法求解全局QoS約束分解為局部約束的服務(wù)優(yōu)化組合問(wèn)題，模擬實(shí)驗(yàn)結(jié)果表明該方法在優(yōu)化Web服務(wù)組合方面具有較高的求解效率。在后期的工作中，除了進(jìn)一步優(yōu)化組合服務(wù)關(guān)聯(lián)模型之外，還需考慮受網(wǎng)絡(luò)環(huán)境等因素的影響，候選服務(wù)質(zhì)量的不穩(wěn)定性、實(shí)時(shí)性和動(dòng)態(tài)性因素，提高服務(wù)質(zhì)量評(píng)價(jià)的準(zhǔn)確度，為高效率的Web服務(wù)組合提供參考依據(jù)。