王雯雯

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

基于遺傳算法考慮服務(wù)質(zhì)量的服務(wù)組合方式的研究

王雯雯

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

隨著云計(jì)算的發(fā)展，服務(wù)越來越多地出現(xiàn)在我們的生活中，服務(wù)的粒度也根據(jù)企業(yè)的具體工作流程或側(cè)重點(diǎn)發(fā)生了變化。單一的服務(wù)往往關(guān)注的是一個(gè)功能單元，而不足以支撐用戶的工作流程，其多樣性及廣泛性使得服務(wù)組合的概念應(yīng)運(yùn)而生。在這里我們結(jié)合軟件質(zhì)量的知識(shí)以及遺傳算法的使用，來介紹考慮服務(wù)質(zhì)量的服務(wù)組合。

服務(wù)組合；遺傳算法；服務(wù)質(zhì)量

1 服務(wù)組合問題引入

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

1.1 服務(wù)組合方法研究現(xiàn)狀

對(duì)于服務(wù)組合這個(gè)問題，許多學(xué)者都進(jìn)行了大量的研究，提出了相應(yīng)的技術(shù)或系統(tǒng)，其分類方式也具有不同的標(biāo)準(zhǔn)，可根據(jù)服務(wù)組合的實(shí)現(xiàn)方式劃分為：編制和編排兩種，其區(qū)別主要是是否依賴于總控協(xié)調(diào)；根據(jù)服務(wù)組合的動(dòng)態(tài)程度劃分為：動(dòng)態(tài)和靜態(tài)服務(wù)組合；還有依據(jù)自動(dòng)化程度進(jìn)行劃分等等。其中討論最多的是依據(jù)方法論的角度進(jìn)行劃分：工作流程、軟件開發(fā)過程、軟件質(zhì)量。在此論文中，主要討論以軟件質(zhì)量為出發(fā)點(diǎn)，考慮服務(wù)質(zhì)量的服務(wù)組合方式。

1.2 考慮服務(wù)質(zhì)量的服務(wù)組合的過程

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

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

對(duì)于考慮服務(wù)質(zhì)量的服務(wù)組合來說，速度是十分重要的，特別是對(duì)于互操作系統(tǒng)，客戶一般不能接受較長時(shí)間的拖延，例如：一個(gè)訂票系統(tǒng)，用戶不會(huì)希望為了要從候選的服務(wù)中選擇提供最低價(jià)的預(yù)訂系統(tǒng)而等待較長的時(shí)間。在一個(gè)快速的組合中，也要求在執(zhí)行過程中重新服務(wù)組合，從服務(wù)質(zhì)量的角度來看，在運(yùn)行過程中，因?yàn)閃eb服務(wù)環(huán)境是動(dòng)態(tài)的，這就會(huì)導(dǎo)致服務(wù)的組合在執(zhí)行期間發(fā)生變化，例如：在后期的某一具體服務(wù)選擇時(shí)，會(huì)對(duì)前期所選擇的服務(wù)有一定的牽制作用，所以除了速度外還有一個(gè)重要的要求：這一方案是可行的且遵循SLA。

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

2 基于遺傳算法考慮服務(wù)質(zhì)量的服務(wù)組合方法陳述

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

（1）滿足服務(wù)水平協(xié)議中的服務(wù)質(zhì)量約束。

（2）對(duì)其它的服務(wù)質(zhì)量參數(shù)有一定的優(yōu)化作用。

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

在描述使用遺傳算法解決、優(yōu)化問題之前，我們需要描述如何計(jì)算組合服務(wù)的服務(wù)質(zhì)量。

2.1 組合服務(wù)的服務(wù)質(zhì)量計(jì)算

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

表1 各結(jié)構(gòu)對(duì)應(yīng)質(zhì)量屬性的聚集函數(shù)

上表中給出了不同的結(jié)構(gòu)針對(duì)不同的軟件質(zhì)量屬性所對(duì)應(yīng)的聚集函數(shù)，亦可以由此得出基于遺傳算法進(jìn)行服務(wù)組合的優(yōu)勢(shì)：這些聚集函數(shù)不可能要求其全部為線性的，尤其是由用戶指定的聚集函數(shù)。

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

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

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

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

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

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

適應(yīng)度：個(gè)體所對(duì)應(yīng)解的好壞，通常由某個(gè)適應(yīng)度函數(shù)表示。

根據(jù)遺傳算法的知識(shí)，要想使用遺傳算法來解決我們的問題，首先要將這個(gè)問題編制為一個(gè)適當(dāng)?shù)幕蚪M也就是染色體。在我們的例子中，基因組被描述為一個(gè)整數(shù)序列，其中數(shù)組的項(xiàng)數(shù)等于組成這一組合服務(wù)的完全分開的抽象服務(wù)的個(gè)數(shù)。每一項(xiàng)都有一個(gè)索引，這一索引對(duì)應(yīng)著一個(gè)數(shù)列，此數(shù)列表示的是該抽象服務(wù)對(duì)應(yīng)的具體服務(wù)組，其結(jié)構(gòu)如圖1所示：

圖1 基因組結(jié)構(gòu)

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

下面我們就可以對(duì)適應(yīng)度函數(shù)及一些約束進(jìn)行建模，適應(yīng)度函數(shù)需要使某一些服務(wù)質(zhì)量屬性（如：可靠性）增至最大，而使某一些減至最?。ㄈ纾捍鷥r(jià)），當(dāng)使用到我們上文所提到的特定領(lǐng)域的服務(wù)質(zhì)量屬性時(shí)，其具體的適應(yīng)度函數(shù)由工作流的設(shè)計(jì)者給出。

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

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

那么其適應(yīng)度函數(shù)可定義為：

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

最后，我們定義此遺傳算法的結(jié)束標(biāo)準(zhǔn)，一種可行的方法是固定最大的遺傳代數(shù)(maxgenconstr)，除此之外以下兩種方法也可以：

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

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

2.3 動(dòng)態(tài)的適應(yīng)函數(shù)

在上文中的適應(yīng)函數(shù)包含了對(duì)個(gè)體違反約束的靜態(tài)處理，也就是說在每一代中的懲罰都是一樣的，若懲罰因子的權(quán)重w5很高就會(huì)存在這樣的風(fēng)險(xiǎn)：在此解決方案中可能違反了某一個(gè)約束但其已十分接近完美的解決方案，它有可能會(huì)被舍棄。其解決方法就是采用動(dòng)態(tài)的懲罰：

其中g(shù)en是指現(xiàn)在所處的代數(shù)，maxgen是遺傳算法中規(guī)定的最大代數(shù)。

2.4 基于遺傳算法的優(yōu)缺點(diǎn)

在解決考慮質(zhì)量的服務(wù)組合問題時(shí)，使用最多的方法是整數(shù)規(guī)劃，其與遺傳算法相比有如下的優(yōu)缺點(diǎn)：在整數(shù)規(guī)劃中，其服務(wù)質(zhì)量屬性的聚合函數(shù)必須是線性的，對(duì)于一些標(biāo)準(zhǔn)的屬性我們可以對(duì)其聚合函數(shù)使用線性化，但有些特殊的屬性其線性化就很困難（例如：分叉結(jié)構(gòu)中其響應(yīng)時(shí)間聚合函數(shù)的線性化），而用戶自定義的質(zhì)量屬性其聚合函數(shù)線性化無法把握。當(dāng)然，我們可以選擇使用非線性整數(shù)規(guī)劃，但其可預(yù)測(cè)性很差。

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

3 結(jié)論

在這里我們?cè)斒隽艘环N解決考慮服務(wù)質(zhì)量的服務(wù)組合的方法，此方法是基于遺傳算法的。即尋找一組滿足約束且對(duì)于每一個(gè)服務(wù)質(zhì)量因子最優(yōu)化的具體服務(wù)，這些具體服務(wù)和與其對(duì)應(yīng)的抽象服務(wù)綁定。與整數(shù)規(guī)劃這一常用方法相比，遺傳算法中其服務(wù)質(zhì)量屬性的聚合函數(shù)可為非線性的，且當(dāng)具體服務(wù)數(shù)目增加時(shí)，遺傳算法的性能可保持。

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

[2]許廣宇．Web服務(wù)組合研究與實(shí)現(xiàn)[D]．北京：北京郵電大學(xué)，2009．

[3]曹洪江．基于用戶需求的Web服務(wù)組合系統(tǒng)研究[D]．武漢：武漢理工大學(xué)，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-），女，山東東營人，碩士，助教，研究方向?yàn)檐浖こ獭?/p>