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

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

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

0 引言

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

1 Web服務算法設計

1.1 算法框架

從圖1中可以看到遺傳算法的具體框架結構,如圖1所示。

圖1 算法框架

先利用遺傳算法個體構建得到社會種群空間；再通過更新函數實現信仰空間知識的更新；利用接收函數接收來自社會群體空間的個體并在信仰空間內轉換為知識；通過生成函數生成種群；影響函數可以利用信仰空間的知識對社會群體空間進化方向產生影響；利用評價函數對種群適應度進行分析；利用函數從遺傳操作中選出交叉個體。

1.2 編碼

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

圖2 染色體編碼

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

1.3 遺傳算子

1) 算子的選擇。

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

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

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

③ 計算得到累計概率。

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

2) 變異算子。

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

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

1.4 算法流程

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

第一步：創建社會種群P，通過適應度函數f對種群個體適應度進行評價。

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

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

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

第五步：評價前代社會種群空間的個體，通過接收函數把較優個體傳輸至信仰空間，實現信仰空間知識的更新。

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

2 實驗

2.1 實驗平臺

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

2.2 結果分析

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

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

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

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

2) 執行時間分析。

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

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

3 總結

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

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

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