持續(xù)自適應(yīng)的Web服務(wù)組合方法

付燕寧, 趙東范, 趙 健

(1. 吉林財(cái)經(jīng)大學(xué) 信息經(jīng)濟(jì)學(xué)院, 長(zhǎng)春 130122; 2. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130012)

Web環(huán)境的改變可以導(dǎo)致過(guò)去是有效的組合服務(wù)不再有效, 過(guò)去是優(yōu)化的組合服務(wù)不再優(yōu)化, 組合服務(wù)性能可能會(huì)退化甚至無(wú)法運(yùn)行. 文獻(xiàn)[1]根據(jù)將具體服務(wù)綁定到組合規(guī)范的時(shí)機(jī)把基于過(guò)程的服務(wù)組合分為三類(lèi)： 1) 在設(shè)計(jì)時(shí)確定具體的服務(wù)并將其綁定到組合規(guī)范； 2) 在組合服務(wù)執(zhí)行前將過(guò)程模型中的任務(wù)綁定為服務(wù), 然后引擎再執(zhí)行組合服務(wù)； 3) 按照過(guò)程模型中任務(wù)間的執(zhí)行邏輯, 逐步將過(guò)程模型中的任務(wù)綁定為服務(wù)并進(jìn)行調(diào)用. 后兩類(lèi)在一定程度上適應(yīng)了動(dòng)態(tài)的Web環(huán)境, 但當(dāng)用戶再次發(fā)出同樣的服務(wù)請(qǐng)求時(shí), 則會(huì)出現(xiàn)以下問(wèn)題： 第二類(lèi)(如文獻(xiàn)[2-3])將以往形成的服務(wù)組合當(dāng)成最終版本, 每當(dāng)用戶再次發(fā)出服務(wù)請(qǐng)求時(shí), 直接利用過(guò)去形成的組合服務(wù), 不再探索新的服務(wù)組合, 這種處理方式只有對(duì)以往組合方案的利用, 而沒(méi)有對(duì)環(huán)境的探索, 因此不能適應(yīng)動(dòng)態(tài)變化的Web環(huán)境； 第三類(lèi)(如文獻(xiàn)[4-5])將每次組合服務(wù)的執(zhí)行都作為一個(gè)全新的問(wèn)題, 重新探索新的環(huán)境形成新的組合服務(wù), 這種處理方式只有對(duì)新環(huán)境的探索而缺乏對(duì)以往服務(wù)組合的利用, 導(dǎo)致增加系統(tǒng)開(kāi)銷(xiāo). 這兩類(lèi)服務(wù)組合方式均缺乏對(duì)動(dòng)態(tài)Web環(huán)境的可持續(xù)適應(yīng)性, 因此, 將強(qiáng)化學(xué)習(xí)應(yīng)用于基于過(guò)程的服務(wù)組合, 可使組合流程無(wú)論在何時(shí)運(yùn)行, 均既可以利用以往獲得的Web服務(wù)性能數(shù)據(jù), 又能探索動(dòng)態(tài)的Web環(huán)境, 在利用的基礎(chǔ)上進(jìn)行探索并調(diào)整組合策略, 持續(xù)適應(yīng)不斷變化的Web環(huán)境. 雖然文獻(xiàn)[5-7]將學(xué)習(xí)機(jī)制用于動(dòng)態(tài)Web環(huán)境下的Web服務(wù)組合, 但文獻(xiàn)[5]僅考慮了組合服務(wù)每次執(zhí)行時(shí)對(duì)環(huán)境的探索, 未考慮對(duì)以往形成的Web服務(wù)性能數(shù)據(jù)的再利用, 對(duì)Web服務(wù)及其性能的探索缺乏可連續(xù)性； 而文獻(xiàn)[6-7]僅考慮了對(duì)以往數(shù)據(jù)的利用, 未考慮對(duì)環(huán)境的探索. 為解決對(duì)Web環(huán)境缺乏可持續(xù)適應(yīng)性的問(wèn)題, 本文根據(jù)解決該類(lèi)服務(wù)組合的特點(diǎn), 提出一種基于Markov決策模型的任務(wù)分配模型, 并為實(shí)現(xiàn)對(duì)動(dòng)態(tài)變化的Web環(huán)境的可持續(xù)探索和利用, 提出了持續(xù)自適應(yīng)服務(wù)組合方法.

1 任務(wù)分配模型

任務(wù)分配策略是將基于過(guò)程的任務(wù)分配視為隨機(jī)順序決策問(wèn)題, 將任務(wù)分配過(guò)程分為若干個(gè)連續(xù)階段, 利用強(qiáng)化學(xué)習(xí)技術(shù)在每個(gè)階段嘗試選擇滿足任務(wù)需求的Web服務(wù), 并從選擇的結(jié)果中進(jìn)行學(xué)習(xí), 在執(zhí)行過(guò)程中逐步逼近從初始階段到終止階段累計(jì)代價(jià)最小的任務(wù)分配.

1.1 過(guò)程模型

服務(wù)請(qǐng)求的過(guò)程模型可形式化表示為SR=(T,R,δ), 其中:T={t1≤t≤m}表示一組構(gòu)成服務(wù)請(qǐng)求的任務(wù)集合；R?T×T表示任務(wù)之間執(zhí)行的次序; (t→t+1)∈R表示只有當(dāng)t執(zhí)行成功,t+1才開(kāi)始執(zhí)行；δ：T→D表示每個(gè)任務(wù)到抽象任務(wù)描述的映射,D表示抽象任務(wù)功能描述的集合, 即D={d1≤d≤m}.

抽象任務(wù)描述與任務(wù)一一對(duì)應(yīng), Web服務(wù)發(fā)現(xiàn)算法利用過(guò)程模型給出的抽象任務(wù)描述查找相應(yīng)的服務(wù).

1.2 候選服務(wù)集合

如果將發(fā)現(xiàn)服務(wù)的過(guò)程表述為函數(shù)φ：D→CS, 則任務(wù)t所對(duì)應(yīng)的服務(wù)集合為CSt=φ(δ(t)), 該服務(wù)集合稱為候選服務(wù)集合. 服務(wù)集合由功能相同、 QoS屬性不同的一組服務(wù)組成.

如果將基于過(guò)程的任務(wù)分配分為若干階段, 則這種組合問(wèn)題具有如下特點(diǎn)： 每個(gè)任務(wù)分配對(duì)應(yīng)一個(gè)階段, 每個(gè)任務(wù)對(duì)應(yīng)一個(gè)侯選服務(wù)集合, 即CS, 因此, 一個(gè)階段即存在多種可能的任務(wù)分配, 需要在每個(gè)階段確定出執(zhí)行任務(wù)的Web服務(wù)； 在當(dāng)前階段確定了某個(gè)服務(wù)后, 則進(jìn)入到下一階段的某個(gè)狀態(tài)(狀態(tài)即一個(gè)階段開(kāi)始時(shí)算法所處的環(huán)境)并且Web服務(wù)的選擇只取決于當(dāng)前狀態(tài), 與過(guò)去各階段的狀態(tài)無(wú)關(guān)； 如果在每個(gè)階段都根據(jù)某種標(biāo)準(zhǔn)確定出優(yōu)化的Web服務(wù), 則由各個(gè)階段選擇出的Web服務(wù)所構(gòu)成的組合服務(wù)也是優(yōu)化的. 因此, 這種服務(wù)組合問(wèn)題實(shí)際上是隨機(jī)順序決策問(wèn)題, Markov決策模型適合為該問(wèn)題建模.

1.3 任務(wù)分配模型

基于Markov決策模型, 將任務(wù)分配問(wèn)題表示為T(mén)AM=(k,s,ξ,ρ).

1)k表示任務(wù)分配階段, 1≤k≤m. 若過(guò)程模型包含m個(gè)待分配的串型任務(wù), 則基于過(guò)程的Web服務(wù)組合過(guò)程可被劃分為m個(gè)連續(xù)階段.

2)s表示在每個(gè)階段開(kāi)始時(shí)算法所處的狀態(tài). 初始階段k=1, 只包括一個(gè)狀態(tài)(即初始狀態(tài), 記為s0)； 其余各階段k≠1, 所包含的狀態(tài)數(shù)取決于前一階段可供分配的Web服務(wù)數(shù)量； 特別當(dāng)k=m時(shí), 沒(méi)有可用于分配的Web服務(wù), 為了算法處理的需要, 需設(shè)定一個(gè)無(wú)代價(jià)的任務(wù)分配終止?fàn)顟B(tài), 記為sd.

如果階段k存在n個(gè)可供選擇的Web服務(wù), 表明階段k的某個(gè)狀態(tài)有n種可能的任務(wù)分配, 這種可能的任務(wù)分配完成后, 算法可能到達(dá)的狀態(tài)稱為可達(dá)狀態(tài). 如果階段k的可達(dá)狀態(tài)為n, 則階段k+1存在n個(gè)狀態(tài).

盡管每個(gè)階段可能有多種狀態(tài), 但在算法執(zhí)行過(guò)程中只能處于某個(gè)階段的某一種狀態(tài), 即在算法執(zhí)行過(guò)程中, 狀態(tài)和階段是相對(duì)應(yīng)的, 因此, 如果將某階段k的某個(gè)狀態(tài)記為s(k), 則s(k)也可以記為s； 同理,CS(k)也可記為CS(s).

3)ξ:πs(w)→w是Web服務(wù)選擇函數(shù), 表示在狀態(tài)s(k)根據(jù)概率分布πs(w)為該狀態(tài)所對(duì)應(yīng)的任務(wù)選擇Web服務(wù).πs(w)是在狀態(tài)s上關(guān)于Web服務(wù)的概率分布(簡(jiǎn)稱為狀態(tài)s的概率分布). 如果狀態(tài)s的候選服務(wù)集為CS(s)={w1,w2,w3}, 則其概率分布πs(w)是πs(w1),πs(w2),πs(w3). 概率分布實(shí)質(zhì)是關(guān)于代價(jià)rk(w)的多項(xiàng)式函數(shù),rk(w)是關(guān)于Web服務(wù)某種性能的實(shí)際觀察值函數(shù).

4)ρ: (s(k),ξ)→s(k+1)是狀態(tài)轉(zhuǎn)移函數(shù), 表示在當(dāng)前狀態(tài)s(k), 由函數(shù)ξ(πs(w))做出了某種任務(wù)分配, 下一個(gè)階段的某個(gè)狀態(tài)s(k+1)也就完全確定了, 即表示在狀態(tài)s(k)完成任務(wù)分配后轉(zhuǎn)換到下一個(gè)狀態(tài)s(k+1).

因此, 任務(wù)分配模型具有如下特點(diǎn)： 一旦在某個(gè)狀態(tài)選定了一個(gè)服務(wù), 則下一個(gè)階段的某個(gè)狀態(tài)也就確定了, 即s′=ρ(s,w); 并且不同的服務(wù)選擇可導(dǎo)致不同的狀態(tài), 即ρ(s,w1)≠ρ(s,w2).

1.4 策略Π

策略Π由各階段(或狀態(tài))上的服務(wù)選擇函數(shù)ξ組成, 即Π={ξkk=1,2,…,m}. 由于ξ由各階段上的概率分布決定, 因此, 策略Π也可定義為是由各階段上的概率分布組成的, 即Π={πs(w)s=1,2,…,m}.m個(gè)階段的任務(wù)分配過(guò)程包括m個(gè)狀態(tài)轉(zhuǎn)換, 與任務(wù)分配模型相對(duì)應(yīng)的任務(wù)分配狀態(tài)轉(zhuǎn)移如圖1所示, 表示了各階段的狀態(tài)及狀態(tài)轉(zhuǎn)移.

圖1 任務(wù)分配狀態(tài)轉(zhuǎn)移Fig.1 Task allocation transition

假設(shè)服務(wù)請(qǐng)求模型包括4個(gè)任務(wù), 存在13個(gè)可供分配的Web服務(wù), 其中,CS(1),CS(2),CS(3),CS(4)分別為4,4,3,2, 階段1～階段5的狀態(tài)數(shù)分別為1,4,4,3,2. 圖1中節(jié)點(diǎn)表示任務(wù)分配狀態(tài), 邊表示狀態(tài)轉(zhuǎn)移； 實(shí)線邊表示實(shí)際轉(zhuǎn)移, 虛線邊表示可能的狀態(tài)轉(zhuǎn)移； 實(shí)心節(jié)點(diǎn)表示實(shí)際到達(dá)的狀態(tài), 空心節(jié)點(diǎn)表示可能達(dá)到的狀態(tài).

算法從初始狀態(tài)出發(fā)直到終止?fàn)顟B(tài)通過(guò)學(xué)習(xí)機(jī)制逐步逼近一條累計(jì)代價(jià)的優(yōu)化路徑. 在初始狀態(tài), 有4個(gè)可供分配的Web服務(wù), 算法根據(jù)函數(shù)ξ為任務(wù)1選擇某個(gè)Web服務(wù)后, 到達(dá)下一個(gè)狀態(tài)2(圖1中實(shí)心節(jié)點(diǎn)所示)； 通過(guò)服務(wù)的執(zhí)行獲得其實(shí)際執(zhí)行代價(jià), 計(jì)算該狀態(tài)的概率分布πs(w), 對(duì)于其他狀態(tài)算法重復(fù)上述過(guò)程, 直至終止?fàn)顟B(tài). 通過(guò)學(xué)習(xí)算法不斷地執(zhí)行, 不斷更新服務(wù)組合策略, 逐步逼近從初始狀態(tài)到終止?fàn)顟B(tài)的優(yōu)化任務(wù)分配策略.

2 主要方法

2.1 選擇Web服務(wù)的依據(jù)

當(dāng)將QoS作為選擇服務(wù)的依據(jù)時(shí), 要注意服務(wù)提供者所給出的性能發(fā)布值是否能準(zhǔn)確反映Web服務(wù)的實(shí)際性能, 否則會(huì)將不是真實(shí)性能的Web服務(wù)加入到組合中而影響組合服務(wù)的性能, 因此在選擇Web服務(wù)時(shí)要根據(jù)Web服務(wù)執(zhí)行的實(shí)際性能, 而不是根據(jù)服務(wù)提供者所發(fā)布的性能. 文獻(xiàn)[8-10]使用“信任”從一組執(zhí)行同樣任務(wù)的服務(wù)中選擇優(yōu)化的Web服務(wù), 利用Web服務(wù)使用者給出的評(píng)價(jià)計(jì)算信譽(yù). 這種計(jì)算信譽(yù)度的弊端是采用了使用者的主觀評(píng)價(jià), 而不同使用者的評(píng)價(jià)標(biāo)準(zhǔn)不同, 因此, 人為的評(píng)價(jià)不一定能反映Web服務(wù)的真實(shí)性能. 本文選擇某種QoS性能參數(shù)的信譽(yù)度作為選擇Web服務(wù)的依據(jù), 通過(guò)比較所觀察到的Web服務(wù)實(shí)際性能和Web服務(wù)提供者所發(fā)布的性能計(jì)算信譽(yù)度.

對(duì)于服務(wù), 其參數(shù)k的信譽(yù)度函數(shù)為

(1)

2.2 選擇Web服務(wù)的技術(shù)

根據(jù)任務(wù)分配模型可知, 該結(jié)構(gòu)恰好對(duì)應(yīng)確定性最短路徑, 可考慮采用動(dòng)態(tài)規(guī)劃或強(qiáng)化學(xué)習(xí)解決這種優(yōu)化問(wèn)題. 由于將Web服務(wù)的實(shí)際性能參數(shù)作為選擇Web服務(wù)的依據(jù), 因此, 在Web服務(wù)執(zhí)行前, 算法并不能獲得Web服務(wù)的實(shí)際性能, 這樣每個(gè)狀態(tài)的概率分布事先并不可知. 如果在概率分布未知的情況下, 優(yōu)化問(wèn)題則轉(zhuǎn)化為強(qiáng)化學(xué)習(xí)問(wèn)題, 通過(guò)值迭代或策略迭代的方式逼近MDP中的最優(yōu)策略. 根據(jù)Bellman最優(yōu)定理, 對(duì)于狀態(tài)空間有限的單鏈MPD問(wèn)題, 必然存在一個(gè)最優(yōu)策略[11]； 同理, 對(duì)于服務(wù)選擇問(wèn)題也必然存在一個(gè)最優(yōu)的任務(wù)分配策略Π={πs(w)s=1,2,…,m}.

因此, 采用如下在線概率分布模型[12]:

(2)

(3)

綜上可知, 概率分布取決于服務(wù)執(zhí)行的實(shí)際代價(jià), 同時(shí)也受θs(即熵)的制約, 可通過(guò)事先指定各狀態(tài)的熵值, 確定各狀態(tài)的探索級(jí)別.

2.3 控制隨機(jī)選擇

探索是嘗試解決新問(wèn)題的方法, 而利用是重用曾經(jīng)成熟的解決方案. 因此, 既要使算法保持一定程度上的探索, 還要使其利用以往獲得的Web服務(wù)性能數(shù)據(jù). 探索和利用間的平衡問(wèn)題是學(xué)習(xí)算法要解決的問(wèn)題之一, 強(qiáng)化學(xué)習(xí)是以集成方式確切地處理探索和利用之間的平衡問(wèn)題及概率分布的在線估計(jì)問(wèn)題[12], 為了量化探索, 利用候選服務(wù)集概率分布的熵定義各狀態(tài)的探索度.

3 算法與分析

3.1 學(xué)習(xí)算法

該算法的主要步驟是從初始狀態(tài)s0出發(fā), 在每個(gè)狀態(tài)s根據(jù)概率分布πs(w)選擇一個(gè)服務(wù)w并執(zhí)行該服務(wù), 根據(jù)服務(wù)執(zhí)行產(chǎn)生的實(shí)際代價(jià), 更新c(s,w),πs(w)和U(s), 然后轉(zhuǎn)移到新的狀態(tài)s′. 重復(fù)這個(gè)過(guò)程直至終止?fàn)顟B(tài). 由于sd是終止?fàn)顟B(tài), 因此sd的代價(jià)為0. 其中,c(s,w),πs(w),U(s)需要預(yù)先給定初始值, 一般情況下, 令πs(w),U(s)的初始值為1/ns和0, 當(dāng)πs(w)=1/ns時(shí),c(s,w)的初始值已經(jīng)不再重要. 算法步驟如下:

WSCompositionPolicy(entropyπ)

1) begin

2)t← identifyTask(SR)

3)CSt=φ(δ(t))

4) if (s≠sd)

5)w←ξ(πs(w))

6) execution(w)

7)c(s,w)=rk(w)

8)θs← computeTeta(πs(w))

10) goto 2)

11) endif

12) end

該算法在不同狀態(tài)與不同的環(huán)境交互, 通過(guò)步驟3)感知Web環(huán)境中服務(wù)的變化. 在步驟5)和步驟6)嘗試選擇執(zhí)行任務(wù)的Web服務(wù), 如何嘗試取決于該狀態(tài)的概率分布. 步驟7)表明算法根據(jù)Web服務(wù)的執(zhí)行而觀察到該服務(wù)實(shí)際執(zhí)行性能(在動(dòng)態(tài)環(huán)境下隨時(shí)間的改變而改變), 并由此計(jì)算出rk(w). 步驟9)更新該狀態(tài)的概率分布, 之后學(xué)習(xí)算法進(jìn)入下一個(gè)任務(wù)分配狀態(tài)s+1, 直至終止?fàn)顟B(tài)sd. 注意算法第一次執(zhí)行時(shí), 根據(jù)初始概率分布選擇執(zhí)行任務(wù)的Web服務(wù).

該算法每次執(zhí)行都是自學(xué)習(xí)、 自適應(yīng)過(guò)程, 通過(guò)算法的不斷執(zhí)行, 算法不斷地獲得所選中Web服務(wù)的執(zhí)行代價(jià), 根據(jù)該代價(jià)不斷更新各狀態(tài)的概率分布, 逐漸逼近一個(gè)優(yōu)化的任務(wù)分配策略, 即Π={πs(w)s=1,2,…,m}.

3.2 算法分析

當(dāng)θs=0時(shí), 概率分布退化為πs(w)=1/ns, 熵值Es=logns, 所有狀態(tài)的探索度達(dá)到最大值, 此時(shí)算法總是處于隨機(jī)探索狀態(tài), 不計(jì)代價(jià)隨機(jī)地選取一個(gè)Web服務(wù)進(jìn)行任務(wù)分配, 不再利用以往學(xué)習(xí)到的策略. 因此, 當(dāng)0

通過(guò)上述分析可知, 合理地給定熵值Es, 該算法即可逐步逼近一個(gè)優(yōu)化的服務(wù)選擇策略. 每當(dāng)Web環(huán)境發(fā)生變化時(shí), 該算法都能動(dòng)態(tài)地調(diào)整服務(wù)組合策略； 如果Web環(huán)境未發(fā)生變化, 則可利用由Web服務(wù)以往性能參數(shù)所學(xué)習(xí)到的組合策略.

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法對(duì)環(huán)境變化的適應(yīng)性, 本文通過(guò)給定不同的探索率, 考察算法在靜態(tài)和動(dòng)態(tài)兩種環(huán)境下對(duì)環(huán)境的探索程度. 每次模擬實(shí)驗(yàn)開(kāi)始, 令U(s)和πs(w)的初始值為0和1/ns, 且每個(gè)狀態(tài)的探索率都相同；根據(jù)方程(3)和(4)在每一步更新平均代價(jià)和轉(zhuǎn)換概率.

4.1 靜態(tài)環(huán)境

當(dāng)探索率分別為0,30%,60%和90%時(shí), 通過(guò)算法探索的路徑, 考察算法對(duì)探索率的變化規(guī)律. 路徑[1,2,6,10,13]上邊的代價(jià)初始值為1, [1,5,9,12,14]上邊的代價(jià)為2, 而其他邊的代價(jià)初始值為3, 由于15是終止?fàn)顟B(tài), 因此[13,15], [14,15]的代價(jià)始終為0. 圖2給出了算法運(yùn)行10 000次(一次運(yùn)行表示一次完整的任務(wù)分配)探索的路徑. 圖2中粗線邊表示高訪問(wèn)率, 細(xì)線邊表示較高訪問(wèn)率, 長(zhǎng)虛線表示中訪問(wèn)率, 短虛線表示低訪問(wèn)率.

圖2 算法在4種不同探索率下的探索路徑Fig.2 Paths from source to destination for four exploration rates

當(dāng)探索率為0時(shí), 一旦找到從節(jié)點(diǎn)1到節(jié)點(diǎn)15的最短路徑, 即[1,2,6,10,13,15](圖2粗線邊所示路徑), 則算法不再進(jìn)行探索, [1,2,6,10,13,15]是唯一的遍歷路徑； 當(dāng)探索率為30%時(shí), 盡管探索到了其他邊, 但最短路徑仍然是[1,2,6,10,13,15], 表明對(duì)原有組合的利用大于探索； 當(dāng)探索率為60%時(shí), 算法探索了更多的邊, 但仍然采用[1,2,6,10,13,15]作為最短路徑, 雖然增加了探索, 但探索仍然低于利用； 當(dāng)探索率為90%時(shí), 不再利用原來(lái)的最短路徑, 探索明顯大于利用. 因此, 隨著探索率的提高, 算法的探索程度逐漸加大.

4.2 動(dòng)態(tài)環(huán)境

當(dāng)探索率分別為0,30%,60%和90%時(shí), 通過(guò)執(zhí)行代價(jià)變化趨勢(shì), 考察算法在不同探索率下對(duì)環(huán)境變化的適應(yīng)性. 圖3給出了隨著算法運(yùn)行次數(shù)的增加, 算法執(zhí)行代價(jià)的變化規(guī)律.

圖3 4種探索率的算法執(zhí)行代價(jià)Fig.3 Cost trends for four exploration rates

初始時(shí), 路徑[1,2,6,10,13]上邊的代價(jià)為3, [1,5,9,12,14,]上邊的代價(jià)為4, 其他邊的代價(jià)為6, 邊[13,15],[14,15]的代價(jià)仍然為0. 此時(shí)最短路徑為[1,2,6,10,13,15], 該路徑的總代價(jià)是12. 對(duì)不同探索率算法分別執(zhí)行13 000次, 當(dāng)算法執(zhí)行到7 501次時(shí), 將所有內(nèi)部邊的代價(jià)置為1, 此時(shí)觀察算法對(duì)不同探索率的變化規(guī)律. 由圖3可見(jiàn), 雖然內(nèi)部邊的代價(jià)發(fā)生了變化, 在整個(gè)模擬實(shí)驗(yàn)過(guò)程中算法執(zhí)行代價(jià)始終為12, 原因是在探索率為0時(shí), 盡管某些邊代價(jià)發(fā)生了改變, 產(chǎn)生了新的最短路徑, 但算法不再進(jìn)行探索； 當(dāng)探索率不為0時(shí), 算法可以在環(huán)境發(fā)生變化的情況下找到新的優(yōu)化路徑(所有經(jīng)過(guò)內(nèi)部節(jié)點(diǎn)3,4,7,8,11經(jīng)過(guò)13到達(dá)15的路徑是最短路徑), 代價(jià)由12變?yōu)?且探索率越高, 找到新優(yōu)化路徑的速度越快, 其原因是當(dāng)探索率不為0時(shí), 算法可對(duì)環(huán)境進(jìn)行探索發(fā)現(xiàn)性能更好的Web服務(wù), 對(duì)原來(lái)形成的組合策略進(jìn)行調(diào)整.

[1] Stephan Leutenmayr. Selected Languages for Web Services Composition: Survey, Challenges, Outlook [D]: [Ph D Thesis]. Munich: University of Munich, 2007.

[2] CHEN Yan-ping, LI Zeng-zhi, TANG Ya-zhe, et al. A Method Satisfying Markov Process of Web Service Composition under Incomplete Constrains [J]. Chinese Journal of Computers, 2006, 29(7): 1076-1083. (陳彥萍, 李增智, 唐亞哲, 等. 一種滿足馬爾可夫性質(zhì)的不完全信息下的Web服務(wù)組合方法 [J]. 計(jì)算機(jī)學(xué)報(bào), 2006, 29(7): 1076-1083.)

[3] LIU Shu-lei, LIU Yun-xiang, ZHANG Fan, et al. A Dynamic Web Services Selection Algorithm with QoS Global Optimal in Web Services Composition [J]. Journal of Software, 2007, 18(3): 646-656. (劉書(shū)雷, 劉云翔, 張帆, 等. 一種服務(wù)聚合中QoS全局最優(yōu)服務(wù)動(dòng)態(tài)選擇算法 [J]. 軟件學(xué)報(bào), 2007, 18(3): 646-656.)

[4] ZENG Liang-zhao, Benatallah B, Dumas M, et al. Quality Driven Web Service Composition [C]//Proceedings of the 12th International Conference on World Wide Web. New York: ACM, 2003: 411-421.

[5] FAN Xiao-qin, JIANG Chang-jun, WANG Jun-li, et al. Random-QoS-Aware Reliable Web Service Composition [J]. Journal of Software, 2009, 20(3): 546-556. (范小芹, 蔣昌俊, 王俊麗, 等. 隨機(jī)QoS感知的可靠Web服務(wù)組合 [J]. 軟件學(xué)報(bào), 2009, 20(3): 546-556.)

[6] Abdallah S, Lesser V. Modeling Task Allocation Using a Decision Theoretic Model [C]//Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent System. New York: ACM, 2005: 719-726.

[7] Hannah H, Mouaddib A I. Task Selection Problem under Uncertainty as Decision-Making [C]//Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent System. New York: ACM, 2002: 1303-1308.

[8] Maximilien E M, Singh M P. Multiagent System for Dynamic Web Services Selection [C]//Proceedings of 1st Workshop on Service-Oriented Computing and Agent-Based Engineering. Netherlands: [s.n.], 2005: 25-29.

[9] ZHAI Hong-yi. Management Tool Design for IP QoS Policy [J]. Journal of Jilin University: Information Science Edition, 2011, 29(3): 225-230. (翟紅藝. IP網(wǎng)絡(luò)QoS策略管理工具設(shè)計(jì) [J]. 吉林大學(xué)學(xué)報(bào): 信息科學(xué)版, 2011, 29(3): 225-230.)

[10] ZHU Mei-ling, ZHAO Xiao-hui, GU Hai-jun, et al. Adaptive Resource Allocation Algorithm for Multiuser OFDM System Based on QoS [J]. Journal of Jilin University: Engineering and Technology Edition, 2009, 39(5): 1347-1352. (朱美玲, 趙曉暉, 顧海軍, 等. 基于QoS的多用戶OFDM系統(tǒng)自適應(yīng)資源分配算法 [J]. 吉林大學(xué)學(xué)報(bào): 工學(xué)版, 2009, 39(5): 1347-1352.)

[11] GAO Yang, ZHOU Ru-yi, WANG Hao, et al. Study on an Average Reward Reinforcement Learning Algorithm [J]. Chinese Journal of Computers, 2007, 30(8): 1372-1378. (高陽(yáng), 周如益, 王皓, 等. 平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)算法研究 [J]. 計(jì)算機(jī)學(xué)報(bào), 2007, 30(8): 1372-1378.)

[12] Achbany Y, Fouss F, Yen L, et al. Optimal Tuning of Continual Online Exploration in Reinforcement Learning [C]//Proceedings of the International Conferrence on Artificial Neural Networks. Berlin: Springer, 2007: 790-800.