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

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

0 引言

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

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

1.1 算法框架

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

圖1 算法框架

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

1.2 編碼

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

圖2 染色體編碼

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

1.3 遺傳算子

1) 算子的選擇。

每次都從之前種群中選出2個染色體并對其實施交叉，以輪盤賭算法選出2條染色體。包括如下步驟：

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

② 計算出個體xi被選中以及進入下代遺傳的概率。

③ 計算得到累計概率。

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

2) 變異算子。

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

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

1.4 算法流程

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

第一步：創(chuàng)建社會種群P，通過適應(yīng)度函數(shù)f對種群個體適應(yīng)度進行評價。

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

第三步：對社會種群個體實施遺傳進化操作。

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

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

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

2 實驗

2.1 實驗平臺

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

2.2 結(jié)果分析

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

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

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

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

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

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

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

3 總結(jié)

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

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

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