基于遺傳算法考慮QoS信息的Web服務(wù)分析

張志偉， 胡同普， 張高峰， 侯天威

(國(guó)網(wǎng)菏澤供電公司， 菏澤 274000)

0 引言

目前，各類(lèi)新的Web服務(wù)技術(shù)被不斷開(kāi)發(fā)并獲得廣泛應(yīng)用，這對(duì)軟件系統(tǒng)架構(gòu)的服務(wù)模式升級(jí)也發(fā)揮了明顯的促進(jìn)作用，使其從傳統(tǒng)面向組件的形式逐漸轉(zhuǎn)變成面向服務(wù)的過(guò)程。同時(shí)，Web服務(wù)還可以實(shí)現(xiàn)良好可擴(kuò)展性以及高效整合異構(gòu)資源的能力，使不同企業(yè)間可以完成無(wú)縫業(yè)務(wù)集成。許多具備同樣功能的開(kāi)放Web服務(wù)得到充分匯聚，此時(shí)服務(wù)合成的重點(diǎn)內(nèi)容不只是尋找所需的服務(wù)，而是如何從大量的Web服務(wù)數(shù)據(jù)中高效選擇符合用戶(hù)需求并具備高可信度以及高質(zhì)量的Web服務(wù)，這也因此成為了當(dāng)前服務(wù)組合方面的一個(gè)新課題[1]。遺傳算法是根據(jù)生物進(jìn)化原理，通過(guò)選擇、變異、交叉等方式完成個(gè)體的遺傳操作，同時(shí)利用適應(yīng)度函數(shù)來(lái)完成種群個(gè)體的“優(yōu)勝劣汰”分析，以這種持續(xù)迭代的方式獲得具有高終適應(yīng)的個(gè)體。考慮到遺傳算法可以實(shí)現(xiàn)可擴(kuò)展性以及很強(qiáng)的全域搜索能力，非常適合將其應(yīng)用在處理服務(wù)組合之類(lèi)的NP難題[2]。不過(guò)也需注意，遺傳算法選擇隨機(jī)進(jìn)化策略，在迭代階段缺少有效的知識(shí)引導(dǎo)，從而使算法搜索方向表現(xiàn)出明顯的盲目性特征。由于文化算法是一類(lèi)建立在知識(shí)基礎(chǔ)上的雙層進(jìn)化系統(tǒng)，可以從進(jìn)化種群內(nèi)抽取與問(wèn)題相關(guān)的知識(shí)，再根據(jù)這些知識(shí)為搜索過(guò)程提供指導(dǎo)，使算法實(shí)現(xiàn)更快速度的收斂，避免算法發(fā)生“早熟”的情況。目前已有許多學(xué)者通過(guò)綜合運(yùn)用遺傳算法與文化算法的方式對(duì)組合優(yōu)化問(wèn)題進(jìn)行有效處理，根據(jù)不同的工作流組合形式，可將其視為一種靜態(tài)綁定機(jī)制：確定流程模板之后，再?gòu)墓?jié)點(diǎn)功能角度分析，為各流程節(jié)點(diǎn)綁定能夠達(dá)到功能要求的各項(xiàng)服務(wù)，不必對(duì)服務(wù)的全局QoS信息進(jìn)行分析；即使包含QoS信息，也基本都是屬于局部服務(wù)。利用QoS語(yǔ)義實(shí)現(xiàn)的服務(wù)組合，通常是按照服務(wù)的QoS語(yǔ)義信息，從候選服務(wù)集內(nèi)尋找跟用戶(hù)功能要求良好匹配的服務(wù)，從本質(zhì)層面上分析這依然屬于一類(lèi)基于功能的服務(wù)組合，雖然可以支持對(duì)服務(wù)質(zhì)量的單獨(dú)選擇，卻無(wú)法從用戶(hù)的服務(wù)需求出發(fā)對(duì)全局QoS約束服務(wù)組合過(guò)程進(jìn)行處理。本文綜合分析了文化算法與遺傳算法，通過(guò)遺傳算法來(lái)完成文化算法的社會(huì)種群空間進(jìn)化，再利用從信仰空間中提取出的知識(shí)為社會(huì)種群空間進(jìn)化提供指引，從而實(shí)現(xiàn)算法的更快收斂并提高服務(wù)組合效率。

1 Web服務(wù)算法設(shè)計(jì)

1.1 算法框架

從圖1中可以看到遺傳算法的具體框架結(jié)構(gòu),如圖1所示。

圖1 算法框架

先利用遺傳算法個(gè)體構(gòu)建得到社會(huì)種群空間；再通過(guò)更新函數(shù)實(shí)現(xiàn)信仰空間知識(shí)的更新；利用接收函數(shù)接收來(lái)自社會(huì)群體空間的個(gè)體并在信仰空間內(nèi)轉(zhuǎn)換為知識(shí)；通過(guò)生成函數(shù)生成種群；影響函數(shù)可以利用信仰空間的知識(shí)對(duì)社會(huì)群體空間進(jìn)化方向產(chǎn)生影響；利用評(píng)價(jià)函數(shù)對(duì)種群適應(yīng)度進(jìn)行分析；利用函數(shù)從遺傳操作中選出交叉?zhèn)€體。

1.2 編碼

根據(jù)服務(wù)組合的操作方式，將染色體結(jié)構(gòu)表示為矩陣編碼的形式。矩陣各列分別代表同類(lèi)抽象服務(wù)，各行對(duì)應(yīng)一個(gè)組合路徑，在各組合路徑中都含有許多不同的服務(wù)，各服務(wù)又與QoS屬性記錄相對(duì)應(yīng),如圖2所示。

圖2 染色體編碼

從圖2中可以看到染色體編碼的具體結(jié)構(gòu)。N代表組合路徑的各服務(wù)數(shù)，各服務(wù)QoS信息包含四個(gè)屬性，分別為響應(yīng)時(shí)間(time)、價(jià)格(cost)、可用性(availability)、信譽(yù)度(reputation)；wij、lij、hij、sij依次對(duì)應(yīng)一類(lèi)特定的抽象服務(wù)(i,j=1,2,…,n)。

1.3 遺傳算子

1) 算子的選擇。

每次都從之前種群中選出2個(gè)染色體并對(duì)其實(shí)施交叉，以輪盤(pán)賭算法選出2條染色體。包括如下步驟：

①f=(f1,f2,f3,…,fN)，代表之前種群的個(gè)體適應(yīng)度，N表示種群數(shù)量。

② 計(jì)算出個(gè)體xi被選中以及進(jìn)入下代遺傳的概率。

③ 計(jì)算得到累計(jì)概率。

④ 每次都生成1個(gè)隨機(jī)數(shù)r，當(dāng)r處于[q(xi),q(xi+1))范圍內(nèi)時(shí)，則選中個(gè)體i。

2) 變異算子。

通過(guò)隨機(jī)變異策略完成變異操作。其中，r1=Rand(1,N)，選出變異染色體，N代表種群的數(shù)量；r2=Rand(1,l)，l代表抽象服務(wù)類(lèi)別。

得到隨機(jī)數(shù)r(0.01≤r≤1.00)，以此作為染色體變異概率，對(duì)應(yīng)種群的變異概率為pmu，其值介于0.01～1.00。當(dāng)rpmu時(shí)，不實(shí)施變異操作。

1.4 算法流程

選擇改進(jìn)后的遺傳算法來(lái)求解服務(wù)組合問(wèn)題，基體步驟為：

第一步：創(chuàng)建社會(huì)種群P，通過(guò)適應(yīng)度函數(shù)f對(duì)種群個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)。

第二步：對(duì)個(gè)體適應(yīng)度實(shí)施排序，通過(guò)接收函數(shù)從原先種群內(nèi)選擇具有較高適應(yīng)度的個(gè)體，生成信仰空間并完成初始化過(guò)程。

第三步：對(duì)社會(huì)種群個(gè)體實(shí)施遺傳進(jìn)化操作。

第四步：利用影響函數(shù)在各進(jìn)化周期K內(nèi)引導(dǎo)社會(huì)種群空間個(gè)體的變異、交叉過(guò)程，使種群進(jìn)化出更高的適應(yīng)度，同時(shí)得到一定數(shù)量的下一代個(gè)體。

第五步：評(píng)價(jià)前代社會(huì)種群空間的個(gè)體，通過(guò)接收函數(shù)把較優(yōu)個(gè)體傳輸至信仰空間，實(shí)現(xiàn)信仰空間知識(shí)的更新。

第六步：不具備停止條件時(shí)，重復(fù)實(shí)施步驟3與步驟5，直至完成大迭代數(shù)或算法終止。

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)平臺(tái)

本實(shí)驗(yàn)的仿真測(cè)試硬件配置為：CPU選擇PentiumP6000，2G內(nèi)存。測(cè)試時(shí)，需關(guān)注Web服務(wù)的4個(gè)QoS屬性，包括服務(wù)價(jià)格、響應(yīng)時(shí)間、信譽(yù)度以及可用性。對(duì)QWS2.0數(shù)據(jù)集進(jìn)行了測(cè)試，將各實(shí)驗(yàn)的交叉概率pc都設(shè)定在0.90，變異概率pm等于0.15。其中，服務(wù)價(jià)格等于0.2，響應(yīng)時(shí)間等于0.2，信譽(yù)度等于0.3，可用性等于0.3。各實(shí)驗(yàn)都進(jìn)行了20次測(cè)試再取平均值。

2.2 結(jié)果分析

1) 適應(yīng)度比較。本組實(shí)驗(yàn)總共包含4類(lèi)抽象服務(wù)，各類(lèi)抽象服務(wù)數(shù)量等于50，迭代數(shù)介于500～5 000范圍內(nèi)，對(duì)適應(yīng)度進(jìn)行比較所得的結(jié)果,如圖3與圖4所示。

根據(jù)圖3與圖4可知，對(duì)于不同的迭代數(shù)與服務(wù)數(shù)，本文ICGA的服務(wù)適應(yīng)度都高于TCGA與IGA，表明ICGA的搜索能力強(qiáng)于TCGA與IGA。對(duì)圖3進(jìn)行分析可以發(fā)現(xiàn)，本文采用的ICGA算法可以實(shí)現(xiàn)比TCGA與IGA算法更快的收斂速度。產(chǎn)生上述結(jié)果的原因是本文構(gòu)建的改進(jìn)遺傳算法在進(jìn)化期間選擇的是優(yōu)個(gè)體保留的策略以及相近染色體排斥的機(jī)制，一方面可以防止同源染色體的無(wú)效交叉，另一方面則可以通過(guò)信仰空間的知識(shí)使社會(huì)種群更加靠近優(yōu)解方向，使社會(huì)種群空間進(jìn)化具有明顯方向性。根據(jù)以上分析可知，相對(duì)于其它兩種方法，以本文ICGA方法得到的種群可以達(dá)到更高適應(yīng)度，并具備更好的收斂性。

1—TCGA；2—ICGA；3—IGA。

1—TCGA；2—ICGA；3—IGA。

2) 執(zhí)行時(shí)間分析。

從圖5中可以看到對(duì)各個(gè)服務(wù)數(shù)量下的3種算法對(duì)應(yīng)的執(zhí)行時(shí)間進(jìn)行比較所得的結(jié)果。本組實(shí)驗(yàn)總共包含了4類(lèi)抽象服務(wù)，各服務(wù)的數(shù)量范圍介于100～500，并且迭代數(shù)都等于500。根據(jù)圖5可知，ICGA具有比TCGA與IGA更長(zhǎng)的執(zhí)行時(shí)間。由于ICGA需要進(jìn)行染色體相似度計(jì)算并采取精英個(gè)體保留機(jī)制，因此需額外占用計(jì)算時(shí)間。

1—ICGA；2—TCGA；3—IGA。

3 總結(jié)

1) 先利用遺傳算法個(gè)體構(gòu)建得到社會(huì)種群空間，再通過(guò)更新函數(shù)實(shí)現(xiàn)信仰空間知識(shí)的更新，并給出了改進(jìn)后的遺傳算法流程。

2) 對(duì)于不同的迭代數(shù)與服務(wù)數(shù)，本文ICGA的服務(wù)適應(yīng)度都高于TCGA與IGA，且可以實(shí)現(xiàn)比TCGA與IGA算法更快的收斂速度。以本文ICGA方法得到的種群可以達(dá)到更高適應(yīng)度，并具備更好的收斂性。

3) ICGA具有比TCGA與IGA更長(zhǎng)的執(zhí)行時(shí)間。由于ICGA需要進(jìn)行染色體相似度計(jì)算并采取精英個(gè)體保留機(jī)制，因此需額外占用計(jì)算時(shí)間。