QoS感知物流Web服務(wù)組合的改進(jìn)遺傳算法

沈記全,羅常委,侯占偉,劉志中

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

1 相關(guān)研究

在經(jīng)濟(jì)全球化浪潮中,第四方物流的發(fā)展在推動(dòng)經(jīng)濟(jì)貿(mào)易增長(zhǎng)方面有著不可替代的作用,是新的國(guó)民經(jīng)濟(jì)增長(zhǎng)點(diǎn),為加速發(fā)展物流行業(yè)開(kāi)創(chuàng)了新的道路[1].然而由于Web服務(wù)運(yùn)行環(huán)境的開(kāi)放性,用戶反饋需求的隨意性,還有Web服務(wù)數(shù)據(jù)真實(shí)性等各種不穩(wěn)定的因素,導(dǎo)致了互聯(lián)網(wǎng)上功能性相同、非功能性不同的物流Web服務(wù)數(shù)量日益增加[2].如何從數(shù)量眾多的物流Web服務(wù)中挑選一組資源服務(wù),并且構(gòu)建出具有最優(yōu)QoS的Web服務(wù)組合是服務(wù)應(yīng)用領(lǐng)域亟待解決的重點(diǎn)問(wèn)題.

文獻(xiàn)[3]針對(duì)Petri網(wǎng)理論,提出了Web服務(wù)組合的Petri網(wǎng)自動(dòng)生成方法,從Web服務(wù)執(zhí)行的角度,給出了Petri網(wǎng)的服務(wù)組合定義,并進(jìn)一步討論了原子服務(wù)的Petri網(wǎng)的PNML+OWL描述方法.文獻(xiàn)[4]提出了一種基于動(dòng)態(tài)Web服務(wù)選擇的離散粒子群算法,為了避免粒子群陷入局部最優(yōu),設(shè)計(jì)了粒子無(wú)希望與重希望準(zhǔn)則來(lái)保證粒子群的多樣性.文獻(xiàn)[5]提出了一種免疫遺傳算法,基于生物免疫機(jī)制中的抗原識(shí)別、抗原記憶和抗體的抑制、促進(jìn)原理,應(yīng)用于貨郎擔(dān)(TSP)優(yōu)化問(wèn)題的求解,該算法具有較好的全局搜索能力.文獻(xiàn)[6]基于參數(shù)自適應(yīng)思想,提出了全局自適應(yīng)優(yōu)化蟻群算法GAO,改進(jìn)了狀態(tài)轉(zhuǎn)移概率和蟻群信息素更新規(guī)則,該方法具有很好的全局收斂能力.文獻(xiàn)[7]針對(duì)Web服務(wù)的動(dòng)態(tài)性、不穩(wěn)定性以及多種QoS屬性約束的問(wèn)題,提出一種多信息素動(dòng)態(tài)更新的蟻群算法MPDACO.

上文中所建立的數(shù)學(xué)模型容易忽略物流Web服務(wù)QoS屬性內(nèi)在的信譽(yù)度和可靠性.而且以粒子群算法(PSO)、遺傳算法(GA)、蟻群算法(ACO)為代表的群體智能進(jìn)化算法存在一定的缺陷:求解結(jié)果不穩(wěn)定,容易陷入局部最優(yōu)等.

針對(duì)物流服務(wù)的不確定性,利用數(shù)學(xué)特征對(duì)QoS信息建模,引入了服務(wù)可靠性、可用性和信譽(yù)度對(duì)組合服務(wù)進(jìn)行綜合評(píng)價(jià).同時(shí)為了提高遺傳算法的搜索效率,進(jìn)一步優(yōu)化了遺傳算法的不足之處.最后通過(guò)對(duì)比實(shí)驗(yàn)證明了該方法的可行性和有效性.

2 物流Web服務(wù)組合問(wèn)題

通過(guò)復(fù)合多種物流Web服務(wù)的手段,也就是按照一定的業(yè)務(wù)邏輯構(gòu)造多個(gè)Web服務(wù)以及Web服務(wù)之間的集成模式,即是物流Web服務(wù)組合.

圖1 物流Web服務(wù)組合Fig.1 Logistics Web service composition

Web組合服務(wù)的原子結(jié)構(gòu)包括順序結(jié)構(gòu)(sequence)、選擇結(jié)構(gòu)(choice)、循環(huán)結(jié)構(gòu)(loop)和并行結(jié)構(gòu)(parallel)[8].這些組合模型可以通過(guò)采取文獻(xiàn)[9]中的技術(shù)轉(zhuǎn)化成順序原子結(jié)構(gòu).服務(wù)流程已經(jīng)確定的Web服務(wù)組合如圖1.設(shè)一個(gè)Web組合服務(wù)有n個(gè)物流服務(wù)類,每個(gè)服務(wù)類有m個(gè)候選Web服務(wù),每個(gè)候選Web服務(wù)有r個(gè)QoS屬性.這種物流Web服務(wù)組合為:CSS={S1,S2,…,Sn},S1,S2,…,Sn是組成物流Web服務(wù)組合流程的服務(wù)節(jié)點(diǎn).Web服務(wù)類CSj={CSj1,CSj2,…,CSjm}包含m個(gè)擁有一樣的功能但QoS不同的候選物流服務(wù)類.每個(gè)候選Web服務(wù)的QoS屬性值可用向量表示為:qk(CSji)={q1(CSji),q2(CSji),…,qr(CSji)}.

當(dāng)處理物流Web服務(wù)組合流程時(shí),可以根據(jù)以下兩種方法判定Web服務(wù)組合程序是否具備可行性:

1)在一個(gè)物流Web服務(wù)組合程序中,物流Web服務(wù)的運(yùn)能可否能夠達(dá)到用戶運(yùn)能的最低標(biāo)準(zhǔn),只有在所有物流Web服務(wù)的運(yùn)能都可以滿足用戶要求時(shí),該物流Web服務(wù)組合程序才是有效的.

2)對(duì)于一個(gè)完整的物流Web服務(wù)組合程序,要求其中所有Web服務(wù)的終止時(shí)間都要在緊接其后的Web服務(wù)的開(kāi)始時(shí)間之前,還需要按照調(diào)度Web服務(wù)的時(shí)間約束條件設(shè)置相應(yīng)的緩沖間隔.

3 數(shù)學(xué)模型

物流Web服務(wù)作為一種復(fù)雜的Web服務(wù)具有多種QoS屬性指標(biāo)[10],所有物流Web服務(wù)的QoS屬性大體上可以分成兩類,一類是考慮QoS屬性最大化的積極屬性,比如Web服務(wù)的可靠性、信譽(yù)度、可用性等;另一類是考慮QoS屬性最小化的消極屬性,比如Web服務(wù)的成本、響應(yīng)時(shí)間等.為了能夠客觀準(zhǔn)確地判斷物流Web服務(wù)的QoS優(yōu)劣,需要將不同數(shù)值類型、不同取值區(qū)間的QoS屬性值歸一化處理,轉(zhuǎn)化為相同的取值類型和范圍.

(1)

在滿足用戶QoS需求的前提下,物流Web服務(wù)的全局服務(wù)質(zhì)量屬性應(yīng)當(dāng)符合下列約束條件:

(2)

(3)

根據(jù)定性概念的數(shù)字特征,可以精確地判斷出QoS屬性的不確定程度,從而為獲得可靠的物流Web服務(wù)組合提供了保障.對(duì)于客戶而言,保留QoS較優(yōu)且波動(dòng)性小的物流Web服務(wù)比不穩(wěn)定的物流Web服務(wù)更為重要.

滿足全局QoS約束的最優(yōu)物流Web服務(wù)組合的目標(biāo)函數(shù)為:

(4)

4 改進(jìn)的遺傳優(yōu)化算法

遺傳算法GA是由美國(guó)Holland教授于1975年提出的一種基于隨機(jī)搜索的智能優(yōu)化算法,其宗旨是將問(wèn)題的隱含解表示為個(gè)體,并利用適應(yīng)度函數(shù)計(jì)算個(gè)體的評(píng)價(jià)值.

4.1 遺傳編碼與初始種群

為了讓GA找到物流Web服務(wù)組合的有效解,首先需要對(duì)染色體進(jìn)行編碼.染色體由一些候選物流Web服務(wù)構(gòu)成,其中的一個(gè)基因代表一個(gè)候選Web服務(wù),包含了r條QoS屬性及其數(shù)值.為了簡(jiǎn)化染色體的編碼方式,文中利用雙層位置編碼模式,使得染色體上不同的基因都有對(duì)應(yīng)的Web服務(wù),QoS屬性由相應(yīng)的基因決定.

目前許多的啟發(fā)式進(jìn)化算法都采用簡(jiǎn)單的均勻取種法或者隨機(jī)取種法來(lái)構(gòu)造初始種群,這兩種方法的隨機(jī)性比較強(qiáng),可能會(huì)引起種群適應(yīng)度普遍偏低,很難提高算法的收斂能力[11].

對(duì)于確定的物流Web服務(wù)組合流程,候選Web服務(wù)CSji的QoS適應(yīng)度函數(shù)如下:

(5)

CSji被選中的概率為:

(6)

4.2 交叉操作

大多數(shù)遺傳算法的交叉操作往往只要求隨機(jī)選擇兩條染色體作為交叉算子,容易導(dǎo)致算法搜索結(jié)果不穩(wěn)定.本文在交叉算子的基礎(chǔ)上引入?yún)f(xié)作學(xué)習(xí)的概念,加快了算法的搜索效率.對(duì)于所有的物流Web服務(wù)組合方案,其中的每個(gè)具體服務(wù)都是基因片段.將這些候選服務(wù)路徑分成相等的子路徑,再使它們分別與剩余的服務(wù)路徑間進(jìn)行模仿選擇,交叉的節(jié)點(diǎn)個(gè)數(shù)為C.自適應(yīng)交叉概率如下:

(7)

4.3 變異操作

(8)

自適應(yīng)變異概率如下:

(9)

4.4 遺傳算法步驟

基于QoS感知的物流Web服務(wù)組合與優(yōu)化算法中,其基本理念是:根據(jù)用戶對(duì)服務(wù)質(zhì)量的約束及偏愛(ài),挑選出滿足用戶需要的候選物流Web服務(wù),提高Web服務(wù)組合的搜索效率.再通過(guò)使用改進(jìn)后的遺傳優(yōu)化算法,得到具有最優(yōu)QoS的物流Web服務(wù)組合方案.詳細(xì)步驟如下:

Step1.初始化候選物流Web服務(wù)集合與服務(wù)質(zhì)量屬性,根據(jù)公式(2)、公式(3)初步選擇候選物流Web服務(wù),設(shè)定最大進(jìn)化代數(shù)Nmax,確定種群規(guī)模.

Step2.對(duì)物流Web服務(wù)進(jìn)行編碼,按照公式(5)計(jì)算物流Web服務(wù)適應(yīng)度,

Step3.根據(jù)適應(yīng)度大小選擇物流Web服務(wù),產(chǎn)生初始種群NGA.

Step4.根據(jù)選擇概率公式可以計(jì)算出所有候選物流Web服務(wù)的選擇概率,根據(jù)輪盤(pán)賭方法可以得到物流Web服務(wù)組合.

Step5.根據(jù)交叉概率Pc計(jì)算Web服務(wù)的交叉概率,判斷是否需要進(jìn)行交叉操作.

Step6.按照變異概率Pm計(jì)算Web服務(wù)的變異概率,然后根據(jù)公式(8)進(jìn)行領(lǐng)域搜索,產(chǎn)生新的Web服務(wù)組合.

Step7.判斷算法是否達(dá)到終止進(jìn)化次數(shù)Nmax,如果達(dá)到就執(zhí)行下一步,否則跳回Step 4.

Step8.終止算法,得到最優(yōu)物流Web服務(wù)組合方案.

5 實(shí)驗(yàn)與分析

5.1 仿真實(shí)驗(yàn)

在仿真實(shí)驗(yàn)中,物流Web服務(wù)組合算法采用的運(yùn)行工具為VC++語(yǔ)言,算法的運(yùn)行環(huán)境為個(gè)人電腦,詳細(xì)配置為:Windows 7 SP1,RAM為2.00GB,CPU為Intel(R)Core(TM)2 E7500.

根據(jù)物流Web服務(wù)的特征,實(shí)驗(yàn)中的任務(wù)個(gè)數(shù)固定為9,候選物流Web服務(wù)的QoS屬性隨機(jī)生成.QoS屬性指標(biāo)分別為:運(yùn)行時(shí)間(time)、成本費(fèi)用(cost)、可靠性(reliability)、可用性(availability)和信譽(yù)度(reputation)五種QoS維度.它們各自的取值范圍分別為:(1h≤t≤30h)、(1$≤c≤100$)、(0.75≤rel≤1)、(0.75≤a≤1)、(0.5≤rep≤1).相應(yīng)的服務(wù)質(zhì)量屬性偏愛(ài)設(shè)置為{0.15,0.2,0.2,0.15,0.3}.

實(shí)驗(yàn)分為兩個(gè)方面:1)當(dāng)物流候選Web服務(wù)數(shù)量固定時(shí),比較不同算法的服務(wù)組合評(píng)價(jià)值;2)隨著候選Web服務(wù)數(shù)量的增加,不同算法運(yùn)行時(shí)間的變化趨勢(shì).

5.2 結(jié)果分析

圖2是算法在相同的實(shí)驗(yàn)環(huán)境下搜索到的物流Web服務(wù)組合評(píng)價(jià)值以及相應(yīng)的迭代次數(shù),其中候選Web服務(wù)數(shù)量

圖2 組合Web服務(wù)評(píng)價(jià)值的比較Fig.2 Comparison of composite Web service evaluation values

設(shè)為m=50.兩種算法在相同的迭代次數(shù)下搜索到的組合服務(wù)評(píng)價(jià)值有著很明顯的差距,改進(jìn)后的遺傳算法(EGA)的收斂速度與搜索解的性能明顯強(qiáng)于GA.

圖3記錄了候選物流Web服務(wù)數(shù)量增加時(shí),兩種不同的算法最終收斂時(shí)的運(yùn)行時(shí)間,其中算法的最大迭代次數(shù)設(shè)定成Nmax=50.顯然,隨著物流服務(wù)數(shù)量的增加,兩種算法搜索性能的差距變得越來(lái)越大.

圖3 算法運(yùn)行時(shí)間(s)的變化趨勢(shì)Fig.3 Trend of algorithm running time

從上述的仿真數(shù)據(jù)可以看出,改進(jìn)后的遺傳優(yōu)化算法更加適合用于求解物流Web服務(wù)組合與優(yōu)化問(wèn)題.

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

Web服務(wù)以其特有的性質(zhì)引起了商業(yè)界、學(xué)術(shù)界的廣泛關(guān)注,而基于QoS的服務(wù)組合技術(shù)更是占據(jù)了重要地位.目前遺傳算法在服務(wù)組合領(lǐng)域還不是十分成熟,文中提出了一種基于QoS感知的物流Web服務(wù)組合優(yōu)化方法,計(jì)算機(jī)仿真實(shí)驗(yàn)證明了該算法具有較高的收斂能力和搜索性能.下一步工作將研究如何將遺傳優(yōu)化算法應(yīng)用到實(shí)際的面向服務(wù)系統(tǒng)開(kāi)發(fā)中,并針對(duì)QoS動(dòng)態(tài)性、Web服務(wù)負(fù)載等方面進(jìn)行更深入的研究.