基于遺傳算法考慮服務質量的服務組合方式的研究

王雯雯

（中國石油大學勝利學院，山東 東營 257000）

基于遺傳算法考慮服務質量的服務組合方式的研究

王雯雯

（中國石油大學勝利學院，山東 東營 257000）

隨著云計算的發展，服務越來越多地出現在我們的生活中，服務的粒度也根據企業的具體工作流程或側重點發生了變化。單一的服務往往關注的是一個功能單元，而不足以支撐用戶的工作流程，其多樣性及廣泛性使得服務組合的概念應運而生。在這里我們結合軟件質量的知識以及遺傳算法的使用，來介紹考慮服務質量的服務組合。

服務組合；遺傳算法；服務質量

1 服務組合問題引入

云計算近幾年來愈來愈多地出現在個人或企業資源使用的優化名單上，而越來越多的企業也樂于將自己的業務功能或者工作流程打包成符合云計算相關標準的Web服務在云上進行發布，這樣無疑可以拓寬客戶群體，實現業務增值。那么對用戶來說就面臨這樣一個問題：單一服務不足以支撐使用需求時，如何選擇、組合已達到最優利用。

1.1 服務組合方法研究現狀

對于服務組合這個問題，許多學者都進行了大量的研究，提出了相應的技術或系統，其分類方式也具有不同的標準，可根據服務組合的實現方式劃分為：編制和編排兩種，其區別主要是是否依賴于總控協調；根據服務組合的動態程度劃分為：動態和靜態服務組合；還有依據自動化程度進行劃分等等。其中討論最多的是依據方法論的角度進行劃分：工作流程、軟件開發過程、軟件質量。在此論文中，主要討論以軟件質量為出發點，考慮服務質量的服務組合方式。

1.2 考慮服務質量的服務組合的過程

云計算的流行使軟件開發過程發生了重大改變。面向服務的軟件工程描述了一種對基于組件的軟件工程的自然解決方法，基于組件的軟件工程中，一個組件綜合者尋找可復用的軟件，并利用一些粘合代碼，將它們組合成一個新的系統。而在云中，無須通過開發應用程序整合服務，服務接口都是公開的，可分為服務發現和服務調用兩部分。而作為面向服務系統的最大的承諾即后期綁定技術的應用，在一個工作流程中給定的功能需求在這里我們稱為抽象服務，其可能由一系列的服務來實現，在這里我們稱這一系列的服務為具體服務。

對應著同一個抽象服務的所有的具體服務都是在功能上等價的即其可以互相替代，而對于組合來說我們就是要對這些等價的具體服務根據一些非功能的屬性進行選擇，這些非功能的屬性即為服務質量屬性。例如，我們可以選擇最便宜的屬性、最快的屬性或者兩者兼顧。服務質量被定義為一組屬性包括：價格、響應時間、有效性、名聲等等，它還可以擁有一些領域特定的服務質量屬性。當然，在選擇過程中，用戶可以指定某一屬性值的限制約束，如價格不可以高于某一指定值，這也有可能影響最終的選擇。而服務的提供商也可以評估Qos屬性值的范圍作為與潛在的用戶建立合同的一部分。

對于考慮服務質量的服務組合來說，速度是十分重要的，特別是對于互操作系統，客戶一般不能接受較長時間的拖延，例如：一個訂票系統，用戶不會希望為了要從候選的服務中選擇提供最低價的預訂系統而等待較長的時間。在一個快速的組合中，也要求在執行過程中重新服務組合，從服務質量的角度來看，在運行過程中，因為Web服務環境是動態的，這就會導致服務的組合在執行期間發生變化，例如：在后期的某一具體服務選擇時，會對前期所選擇的服務有一定的牽制作用，所以除了速度外還有一個重要的要求：這一方案是可行的且遵循SLA。

對于上述的服務組合需要解決的問題，利用整數規劃無疑是可以解決的，但是在這里我們不得不假設約束和目標函數都是線性的。在整數規劃方法中對服務質量的考慮主要集中在花費、響應時間、有效性、可靠性等，而且這一類的模型聲稱可以對一些更加一般的約束屬性做出處理，如服務依存關系、用戶的喜好等等，但是這些優化的方法沒有給出；在這里建議使用遺傳算法，遺傳算法比整數規劃方法慢，但是其描述了更多可改變的選擇，更加適合操作一般的服務質量屬性。當然我們可以采用非線性的規劃方法，但是其可用工具的成熟度不高，而且無法驗證其結果的準確性。還有一種基于人工智能的約束處理方法叫做約束邏輯編程，這種方法有一個優勢就是它具有豐富的建模能力，其特點是約束傳播，即用約束來定義變量的允許子域，并且遞歸地運用此方法，顯然這一方法可以得到一個有效的組合，但是其價格昂貴。在下文將陳述基于遺傳算法考慮服務質量的服務組合的具體方法、這種方法的優勢及不足。

2 基于遺傳算法考慮服務質量的服務組合方法陳述

如上文所述，本文旨在提出一種基于遺傳算法的、可以快速地為一組抽象服務決定其具體的服務集合。此服務集合必須符合以下規則：

（1）滿足服務水平協議中的服務質量約束。

（2）對其它的服務質量參數有一定的優化作用。

在這里我們要考慮的是一個由n個抽象服務組成的組合服務S，S={s1,s2,……sn}。而其具體的結構由一些工作流的描述語言給出，每一個成員Si又與m個具體服務相對應CSi.1，……CSi.m，其中這m個具體服務在功能上是等價的。

在描述使用遺傳算法解決、優化問題之前，我們需要描述如何計算組合服務的服務質量。

2.1 組合服務的服務質量計算

首先，在這里我們所考慮的是基于工作流程的組合服務的服務質量，那么我們就要對工作流程中的不同情況進行不同的考慮：switch結構（選擇），每一個case選擇語句都標注著其被選擇的可能性（概率），例如，一個包含著switch的工作流，其中switch結構中有兩個選擇，其花費分別為C1，C2，其概率分別為P及1-P，則全部的成本可由下式計算：PC1+(1-P)C2。顯然，概率的初始化是由工作流的設計者完成的，其更新取決于工作流在執行過程中監測所得的信息。Loop結構（循環）由其循環次數k標注，如果循環的代價是C，那么此循環的預測成本為：kC；這樣定義循環結構的優勢在于：它允許在不展開循環的前提下，對工作流的質量進行快速計算；對循環結構的服務質量的評估與對其循環次數的評估相關聯。Fork結構（分叉）中除時間屬性的聚合函數為并行任務中的最大耗時外，其它屬性的聚集函數與順序結構一致。不同結構的不同服務質量聚集函數可由表1給出：

表1 各結構對應質量屬性的聚集函數

上表中給出了不同的結構針對不同的軟件質量屬性所對應的聚集函數，亦可以由此得出基于遺傳算法進行服務組合的優勢：這些聚集函數不可能要求其全部為線性的，尤其是由用戶指定的聚集函數。

2.2 基于遺傳算法的解決方案

遺傳算法并不強制其服務質量的屬性成分必須是線性的（目標函數和約束），這就使得我們可以對所有的可能的服務質量屬性（包括自定義的屬性）使用此方法，而無須將其線性化。

要使用遺傳算法首先要確定基本的組成元素：

基因：組成染色體的單元。

染色體或者個體：表示待求解問題的一個可能解。

群體：由一定量的染色體組成是遺傳算法的搜索空間。

適應度：個體所對應解的好壞，通常由某個適應度函數表示。

根據遺傳算法的知識，要想使用遺傳算法來解決我們的問題，首先要將這個問題編制為一個適當的基因組也就是染色體。在我們的例子中，基因組被描述為一個整數序列，其中數組的項數等于組成這一組合服務的完全分開的抽象服務的個數。每一項都有一個索引，這一索引對應著一個數列，此數列表示的是該抽象服務對應的具體服務組，其結構如圖1所示：

圖1 基因組結構

遺傳算法的基本運算包括選擇、交換和突變，起初隨機選擇服務組合方式，也就是隨機選擇一些個體，充分體現“適者生存，優勝劣汰”的進化原則，所謂優劣通過適應度函數來進行計算，服務組合適應度函數的建模將在下文中給出，根據適應度排序并產生下一代，這個過程通過選擇和繁殖（交換和突變）完成，在這里就涉及到交叉算子和變異算子的概念，結合服務組合問題給出兩種算子的含義：交叉算子是標準的二點交叉，而變異算子是隨機選擇一個抽象服務（即基因組中的位置）并用另一個有效的具體服務隨機替換與此抽象服務對應的具體服務。顯然，在遺傳算法的執行過程中，一個抽象服務只與一個具體服務對應。周而復始，直到滿足終止條件。常見的終止條件有進化的次數、資源限制、適應度飽和等等，在本文中依據服務組合這個具體問題的實際需求，給出的終止條件與約束條件有關。

下面我們就可以對適應度函數及一些約束進行建模，適應度函數需要使某一些服務質量屬性（如：可靠性）增至最大，而使某一些減至最小（如：代價），當使用到我們上文所提到的特定領域的服務質量屬性時，其具體的適應度函數由工作流的設計者給出。

此外，適應函數必須分別對那些違反約束但是可以推動得出符合約束的演變的情況作出懲罰，我們假設一個組合服務服務質量有如下一系列的約束：其中，g為一個基因組即一個個體，也就是一個服務組合；此服務組合中共有n個服務；cl表示每種服務的約束函數，當此個體在某一服務約束函數大于0時則說明其違反了約束也就是針對每一個服務的y取值會為1，這樣也就是所謂的懲罰；D函數計算一個個體（服務組合）服務約束距離之和。

我們定義約束滿足的距離為：

那么其適應度函數可定義為：

在此公式中，服務質量因子的大小控制在[0,1]之間，w1,w2,w3,w4,w5是不同的適應度函數中真實確定的權重，w1,w2,w3,w4暗示了特定的服務質量因子對適應性函數的貢獻，其中Cost()為花費、Response Time()為響應時間、Availability()為可用性、Reliability()為可靠性，這些都是常用的軟件質量評價屬性，w5代表了懲罰因子的權重。

最后，我們定義此遺傳算法的結束標準，一種可行的方法是固定最大的遺傳代數(maxgenconstr)，除此之外以下兩種方法也可以：

（1）執行，直到約束全部滿足D(g)=0；如果在最大代數里沒有遇到這種情況，則說明這一問題無解；

（2）一旦D(g)=0，記錄此時遺傳代數為maxgenfitness這可能是maxgenconstr的一個百分數，這一代可作為選擇，繼續執行遺傳算法，直到個體的適應度函數不隨遺傳代數的增加而改變。

2.3 動態的適應函數

在上文中的適應函數包含了對個體違反約束的靜態處理，也就是說在每一代中的懲罰都是一樣的，若懲罰因子的權重w5很高就會存在這樣的風險：在此解決方案中可能違反了某一個約束但其已十分接近完美的解決方案，它有可能會被舍棄。其解決方法就是采用動態的懲罰：

其中gen是指現在所處的代數，maxgen是遺傳算法中規定的最大代數。

2.4 基于遺傳算法的優缺點

在解決考慮質量的服務組合問題時，使用最多的方法是整數規劃，其與遺傳算法相比有如下的優缺點：在整數規劃中，其服務質量屬性的聚合函數必須是線性的，對于一些標準的屬性我們可以對其聚合函數使用線性化，但有些特殊的屬性其線性化就很困難（例如：分叉結構中其響應時間聚合函數的線性化），而用戶自定義的質量屬性其聚合函數線性化無法把握。當然，我們可以選擇使用非線性整數規劃，但其可預測性很差。

換句話說，線性規劃的方法要比遺傳算法方法速度快，當工作流程數目和具體服務數目有限且無須使用非線性聚合函數時，整數規劃方法更加合適。當對于每一個抽象服務都有大量的具體服務可供選擇時，應選用遺傳算法。

3 結論

在這里我們詳述了一種解決考慮服務質量的服務組合的方法，此方法是基于遺傳算法的。即尋找一組滿足約束且對于每一個服務質量因子最優化的具體服務，這些具體服務和與其對應的抽象服務綁定。與整數規劃這一常用方法相比，遺傳算法中其服務質量屬性的聚合函數可為非線性的，且當具體服務數目增加時，遺傳算法的性能可保持。

[1]鄧水光，吳朝暉．Web服務組合方法綜述[J]．中國科技論文在線，2008，3(02)：79-84．

[2]許廣宇．Web服務組合研究與實現[D]．北京：北京郵電大學，2009．

[3]曹洪江．基于用戶需求的Web服務組合系統研究[D]．武漢：武漢理工大學，2010．

Research on Service Composition Based on GeneticAlgorithm in Consideration of Service Quality

Wang Wenwen
(Shengli College,China University of Petroleum,Dongying 257000,Shandong)

With the development of cloud computing,more and more services appear in our life,the service granularity also changes according to the specific procedures or the emphasis in enterprises.Single service tends to pay attention to a functional unit,which is not enough to support the user's work flow,so the concept of service composition arise according to the diversity and universality of service.This paper combines the knowledge of software quality and the usage of genetic algorithms,and introduces service composition considering service quality.

service composition;genetic algorithm;service quality

TP393.09

A

1008-6609(2017)08-0048-03

作者介紹：王雯雯（1986-），女，山東東營人，碩士，助教，研究方向為軟件工程。