主客觀權(quán)重遺傳算法在服務(wù)選擇中的研究

吳明禮，魏瑞珍

(北方工業(yè)大學(xué) 信息學(xué)院，北京 100144)

0 引 言

目前，網(wǎng)絡(luò)上的Web服務(wù)越來越多，但是功能都比較單一，已經(jīng)無法滿足復(fù)雜應(yīng)用的需求，需要通過一定的技術(shù)將這些Web服務(wù)組合起來，形成功能強(qiáng)大的服務(wù)[1]。Web服務(wù)組合的前提是服務(wù)選擇，隨著Web服務(wù)數(shù)量的不斷增多，服務(wù)選擇問題變得越來越復(fù)雜，如何從海量的候選服務(wù)中，選出開發(fā)人員滿意的服務(wù)，成了Web服務(wù)選擇領(lǐng)域的研究熱點(diǎn)[2]。

Web服務(wù)的選擇重點(diǎn)是找到既滿足功能需求又滿足非功能需求(服務(wù)質(zhì)量)的服務(wù)[2]。而在基于服務(wù)質(zhì)量的Web服務(wù)選擇研究方面，選擇結(jié)果的滿意度和算法的求解受到廣泛關(guān)注。但是，在滿意度方面，以往都將開發(fā)人員的需求直接轉(zhuǎn)化為權(quán)重，而忽略了服務(wù)的客觀性能；在算法的求解方面，以往使用的智能算法如粒子群算法[3]、多目標(biāo)蟻群算法[4]、人工蜂群算法[5]等雖然取得了一定的效果，但是，在面對大規(guī)模的Web服務(wù)選擇問題時(shí)，仍然存在收斂性方面的不足，遺傳算法[6,7]在研究中被認(rèn)為更適合[8]。本文中，結(jié)合Web服務(wù)選擇和遺傳算法的特點(diǎn)，對遺傳算法中的編碼，適用度函數(shù)中的權(quán)重，交叉和變異都做了一定的改進(jìn)，使改進(jìn)后的遺傳算法在結(jié)果滿意度方面和算法收斂性方面都有一定的提升。

1 基于QoS的Web服務(wù)選擇的研究現(xiàn)狀

基于服務(wù)質(zhì)量的Web服務(wù)選擇問題，屬于組合優(yōu)化問題。是NP難問題。很多學(xué)者針對這個(gè)問題提出了各種解決方法。在對基于服務(wù)質(zhì)量的Web服務(wù)選擇求解時(shí)，傳統(tǒng)的方法有窮舉法和貪婪算法。但是這種算法都只適用于候選服務(wù)個(gè)數(shù)少的情況。目前，Web服務(wù)的數(shù)量不斷增長，這些算法難以達(dá)到較好的求解速度，因此，學(xué)者們提出了各種啟發(fā)式的智能算法，來應(yīng)對目前的形勢。

在使用遺傳算法求解時(shí)，收斂速度慢，易陷入局部最優(yōu)解。針對這些問題，魯城華等[9]采用多屬性多決策方法，對多個(gè)QoS屬性同時(shí)處理，將問題轉(zhuǎn)化為多目標(biāo)優(yōu)化問題，為了提高計(jì)算效率，提出基于ε支配的多目標(biāo)遺傳算法。徐甜等[8]針對使用遺傳算法求解Web服務(wù)優(yōu)化組合的問題，提出將多尺度交叉算子和信息共享因子引入遺傳算法，提高了問題的求解速度。吳青林等[10]提出在求解動(dòng)態(tài)Web服務(wù)組合時(shí)，將罰函數(shù)的概念引入遺傳算法，并且動(dòng)態(tài)調(diào)整變權(quán)因子，交叉因子和變異因子，實(shí)現(xiàn)了在較短時(shí)間內(nèi)找到符合用戶需求的服務(wù)。譚文安等[11]針對Web服務(wù)組合中的服務(wù)質(zhì)量感知問題，提出了一種基于混沌遺傳算法的Web服務(wù)組合方法。通過對每次進(jìn)化后的子代群體附加混沌小擾動(dòng)有效克服了遺傳算法早熟和收斂速度慢的問題。葉恒舟等[12]在提出的遺傳算法中，先使用Top-k選擇方法，從每個(gè)抽象服務(wù)組中篩選出若干候選服務(wù)，有效減少了解空間，然后再使用遺傳算法進(jìn)行求解。

上述改進(jìn)的遺傳算法求解Web服務(wù)的選擇問題時(shí)，都只關(guān)注算法本身的收斂性和求解效率，而忽略了Web服務(wù)自身的一些特殊性質(zhì)。

(1)在使用遺傳算法編碼時(shí)，大多采用二進(jìn)制編碼方式，如譚文安等[11]在編碼時(shí)，選中Web服務(wù)設(shè)為1，未選中設(shè)為0，當(dāng)Web服務(wù)過多時(shí)，存在編碼長度過長的問題。

(2)在計(jì)算遺傳算法適應(yīng)度函數(shù)值時(shí)，由于Web服務(wù)的QoS屬性有多個(gè)，每個(gè)屬性權(quán)重的賦值都很重要，不同的權(quán)重會(huì)產(chǎn)生不同的結(jié)果，但是大部分的研究只是簡單考慮開發(fā)人員的偏好，如徐甜等[8]在使用遺傳算法求解時(shí)，直接將開發(fā)人員的偏好設(shè)置為權(quán)重，如果開發(fā)人員設(shè)置的權(quán)重不恰當(dāng)，就會(huì)給選擇帶來誤差，這種情況要求系統(tǒng)有一定的糾正能力。

針對這些問題，本文對Web服務(wù)的QoS屬性的權(quán)重進(jìn)行分析，提出了一種基于主客觀權(quán)重的遺傳算法，并且對遺傳算法的編碼，選擇，交叉，變異進(jìn)行了改進(jìn)，使算法更加適用于Web服務(wù)的選擇問題，有效提高了算法的收斂性。

2 基于改進(jìn)遺傳算法的QoS的Web服務(wù)選擇

2.1 標(biāo)準(zhǔn)遺傳算法的流程

遺傳算法(genetic algorithm)是一種全局的搜索算法，搜索過程不需要知道問題的內(nèi)在性質(zhì)。借鑒了生物界的適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)律。由美國J.Holland教授在1975年首次提出。遺傳算法首先要進(jìn)行基因編碼，從一個(gè)初始種群開始，經(jīng)過遺傳，交叉，變異，逐漸產(chǎn)生出滿足要求的個(gè)體。遺傳算法的工作流程如圖1所示。

圖1 標(biāo)準(zhǔn)遺傳算法流程

2.2 Web服務(wù)選擇模型的建立

2.2.1 Web服務(wù)的選擇模型

在Web服務(wù)的工作流模型中，主要的組合結(jié)構(gòu)有順序，循環(huán)，選擇和并行結(jié)構(gòu)[13]。組合結(jié)構(gòu)如圖2所示。

圖2 Web服務(wù)組合結(jié)構(gòu)

由于順序結(jié)構(gòu)的組合模型，是組合模型中最基礎(chǔ)也是最重要的模型，其它模型都可以轉(zhuǎn)化為順序模型，所以這篇文章中，只研究基于順序結(jié)構(gòu)的組合模型。

對于每個(gè)Web服務(wù)，都有若干個(gè)QoS屬性，我們先對Web服務(wù)的QoS屬性做一些介紹。本文中，Web服務(wù)的QoS屬性主要選取響應(yīng)時(shí)間，價(jià)格，可用性和信譽(yù)。響應(yīng)時(shí)間(t)：介于發(fā)送請求和收到響應(yīng)的時(shí)間間隔；可用性(v)：指服務(wù)成功執(zhí)行的次數(shù)與總執(zhí)行次數(shù)的比值；價(jià)格(p)：是調(diào)用一次服務(wù)的費(fèi)用；信譽(yù)(r)：主要取決于調(diào)用者使用服務(wù)的體驗(yàn)，可以被定義為用戶對服務(wù)的評價(jià)的得分。

在順序結(jié)構(gòu)的組合模型中，一個(gè)工作流可以被描述為：工作流中有n個(gè)抽象的服務(wù)，每個(gè)抽象服務(wù)表示為Fi， 有i到j(luò)個(gè)功能相似的服務(wù)可提供給用戶，表示為Fij， 每個(gè)服務(wù)有k個(gè)QoS屬性，表示為qk， 每組抽象服務(wù)中有且僅有1個(gè)服務(wù)被選中，最終的組合服務(wù)表示為WS， 求最優(yōu)的組合方式。如圖3所示。

圖3 服務(wù)組合 注：上圖是一個(gè)順序結(jié)構(gòu)的工作流模型下的服務(wù)組合 示意圖，方框表示抽象服務(wù)，方框內(nèi)的圖案 表示功能相同，非功能屬性不同的服務(wù)。

該模型可用數(shù)學(xué)公式描述為

(1)

其中， minFi=min{F11,F12,F13…F1m}， 同時(shí)

(2)

這是一個(gè)多目標(biāo)組合優(yōu)化問題，本文采用線性加權(quán)的方式將它轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，轉(zhuǎn)化后為

(3)

在Web服務(wù)選擇中，Web服務(wù)屬性的權(quán)重非常關(guān)鍵，影響著最終的選擇結(jié)果。需要對權(quán)重進(jìn)行詳細(xì)的分析，使得結(jié)果更加準(zhǔn)確和滿意。

2.2.2 Web服務(wù)選擇中主客觀權(quán)重分析

開發(fā)人員在選擇服務(wù)時(shí)，往往需要按照自己的需求去選擇，但是如果只按照開發(fā)人員需求選擇時(shí)，往往會(huì)忽略服務(wù)潛在的性能。馬友等[14]提出了一種自適應(yīng)主客觀權(quán)重的度量算法，很好解決了這個(gè)問題，本文把這一概念引用到Web服務(wù)選擇中。

開發(fā)人員在選擇Web服務(wù)時(shí)，針對應(yīng)用領(lǐng)域的不同，對QoS屬性的側(cè)重可能有不同的要求，有的希望響應(yīng)時(shí)間盡量短，有的希望服務(wù)的價(jià)格盡量低，不同的需求就會(huì)有不同的權(quán)重，這類按照開發(fā)人員的需求轉(zhuǎn)化而來的權(quán)重，稱為Web服務(wù)選擇中的主觀權(quán)重。

主觀權(quán)重可以由用戶直接指定，也可以通過自適應(yīng)法，專家評分法，層次分析法等來確定。這里設(shè)主觀權(quán)重為ws， 以供后文使用。

但是，當(dāng)開發(fā)人員在給定主觀權(quán)重時(shí)，往往會(huì)因?yàn)椴涣私馇闆r而給出不恰當(dāng)?shù)闹?，如開發(fā)人員需要盡量便宜，但是便宜的那個(gè)服務(wù)其它性能都非常差，這種情況下，主觀權(quán)重就需要系統(tǒng)進(jìn)行糾正，以此來調(diào)整選出的結(jié)果。例如：對于服務(wù)A、B，當(dāng)屬性q1、q2的權(quán)重分別為0.6、0.4(情況a)時(shí)，A服務(wù)比B服務(wù)好，當(dāng)權(quán)重調(diào)整為0.3、0.7(情況b)時(shí)，B服務(wù)比A服務(wù)好。比較結(jié)果見表1。

表1 權(quán)重對服務(wù)選擇結(jié)果的影響比較

這里把系統(tǒng)給屬性賦予的權(quán)重定義為客觀權(quán)重?？陀^權(quán)重反應(yīng)了服務(wù)的潛在性能和規(guī)律，對于一組服務(wù)，如果其中某一屬性的值相差不大，那么這個(gè)屬性的參考價(jià)值就不大，客觀權(quán)重就小?？陀^權(quán)重是對服務(wù)的區(qū)分能力的體現(xiàn)。

客觀權(quán)重的計(jì)算公式定義為

(4)

dis(qi)=|qi|/|S|

(5)

其中，qi表示第i個(gè)屬性，dis(qi) 表示屬性對服務(wù)的區(qū)分能力， |S| 表示服務(wù)的個(gè)數(shù)， |qi| 表示屬性qi劃分服務(wù)的個(gè)數(shù)。如某一抽象服務(wù)的價(jià)格屬性值為2,3,4,5,5，則 |S|=5， |qi|=4。

在計(jì)算Web服務(wù)屬性的權(quán)重時(shí)，首先確定開發(fā)人員的主觀權(quán)重，然后再使用可以保證服務(wù)潛在性能的客觀權(quán)重計(jì)算方法，求出客觀權(quán)重，最后使用效用函數(shù)計(jì)算最終權(quán)值。最終權(quán)重的計(jì)算公式為

w=αws+(1-α)wo

(6)

2.3 基于改進(jìn)遺傳算法的Web服務(wù)選擇模型求解

在分析完基于QoS的Web服務(wù)選擇模型和Web服務(wù)選擇中的權(quán)重后，就需要對模型進(jìn)行求解。這里采用基于主客觀權(quán)重的遺傳算法，即在Web服務(wù)選擇的適用度函數(shù)的計(jì)算中，權(quán)重的計(jì)算采用主客觀相結(jié)合的方式。

2.3.1 數(shù)據(jù)預(yù)處理

在度量Web服務(wù)的QoS屬性時(shí)，首先需要將不同單位不同方向的QoS屬性化為[0,1]區(qū)間中的值。越大越好的QoS屬性，稱為正屬性，如信譽(yù)度。越小越好的QoS屬性，稱為負(fù)屬性，如價(jià)格。在使用遺傳算法進(jìn)行求解時(shí)，首先要進(jìn)行數(shù)據(jù)的歸一化處理，本文采用下面的常用公式進(jìn)行歸一化的處理,處理完成后，所有屬性都是越大越好

(7)

(8)

2.3.2 編碼

在Web服務(wù)選擇中，功能相同的服務(wù)被認(rèn)為是一類抽象服務(wù)，即每類抽象服務(wù)由個(gè)數(shù)不等的功能相同而服務(wù)質(zhì)量不同的具體服務(wù)組成。以往的二進(jìn)制編碼方式很難準(zhǔn)確的描述，而且如果功能相同的服務(wù)個(gè)數(shù)很多，二進(jìn)制編碼串會(huì)很長，不能很好反應(yīng)Web服務(wù)選擇的特定環(huán)境。所以，這里采用鍵值對整數(shù)編碼方式，即Key-Value 編碼，先對抽象服務(wù)的編號為Key，抽象服務(wù)中的具體服務(wù)的編號為Value。這種編碼方式，邏輯清晰，可以很容易對應(yīng)到服務(wù)選擇的模型中，且易于代碼實(shí)現(xiàn)；簡化了后面計(jì)算適應(yīng)度函數(shù)時(shí)個(gè)體的解碼過程。編碼如圖4所示。

圖4 編碼

其中，k1到kn表示抽象服務(wù)編碼，v1到vn為具體服務(wù)編號，v1到vn的最小值可取0，最大值為所屬抽象服務(wù)所包含的具體服務(wù)的個(gè)數(shù)減1，以此類推。

2.3.3 初始化種群

隨機(jī)的生成初始化種群，在生成初始化種群時(shí)，對于不符合約束條件的個(gè)體直接進(jìn)行淘汰。保證最終種群的個(gè)體都是有效的個(gè)體。

2.3.4 群體的適應(yīng)度函數(shù)

因?yàn)樵谝酝?jì)算群體的適應(yīng)度函數(shù)時(shí)，只是簡單的使用權(quán)重與綜合值相乘再相加的模式，這種模式只注重了開發(fā)人員的主觀權(quán)重，而忽略了服務(wù)的客觀權(quán)重，造成服務(wù)選擇的片面性，這里采用綜合考慮主客觀權(quán)重的方式，既考慮開發(fā)人員的需求問題，同時(shí)又注重服務(wù)的客觀性，使最后的選擇結(jié)果更具有全面性。適用度函數(shù)的公式如下

(9)

式中：ti表示W(wǎng)eb服務(wù)的響應(yīng)時(shí)間，pi表示W(wǎng)eb服務(wù)的價(jià)格，vi表示W(wǎng)eb服務(wù)的可用性，ri表示W(wǎng)eb服務(wù)的信譽(yù)度。權(quán)重wt,wp,wv,wr使用式(6)進(jìn)行計(jì)算。

2.3.5 選擇

遺傳算法有很多選擇策略，如輪盤賭選擇，隨機(jī)遍歷抽樣法等。在Web服務(wù)的選擇中，對輪盤賭的方式進(jìn)行改進(jìn)，以此來加快算法的收斂速度。

首先，利用公式

(10)

計(jì)算出個(gè)體的賭盤概率，同時(shí)得到個(gè)體的平均適用度值。然后，根據(jù)個(gè)體的賭盤概率和平均適應(yīng)度，選擇個(gè)體。最終選擇的個(gè)體適應(yīng)度都是在平均適應(yīng)度之上的個(gè)體。

2.3.6 交叉

在Web服務(wù)選擇中，編碼方式采用了鍵值對編碼方式，在交叉操作時(shí)，實(shí)質(zhì)上我們僅對兩個(gè)父類的value值進(jìn)行交叉，如圖5所示。

圖5 個(gè)體交叉

同時(shí)，在對個(gè)體進(jìn)行交叉時(shí)，考慮到對于兩個(gè)相似度高的個(gè)體交叉時(shí)，產(chǎn)生的父代和子代的差異不大，交叉沒有意義。所以這里引用小生境思想，讓個(gè)體在一定的環(huán)境下進(jìn)化。這里對交叉算子進(jìn)行改進(jìn)。具體做法是：首先，計(jì)算交叉?zhèn)€體Fi和Fj的距離Sij(即兩個(gè)個(gè)體適應(yīng)度函數(shù)值的差)，如果Sij小于特定的數(shù)，那么就不進(jìn)行交叉，否則交叉。交叉概率的公式為

pc=pc0(1-t/T)-pcmint/T

(11)

其中，pc0為初始交叉概率，pcmin為最小交叉概率，t表示當(dāng)前迭代次數(shù)，T為最終終止次數(shù)。當(dāng)Sij較大時(shí)，父代個(gè)體的差異較大，進(jìn)行交叉操作，迭代剛開始時(shí)，交叉概率較大，可使群體產(chǎn)生更多新的個(gè)體。隨著迭代的進(jìn)行，交叉概率慢慢減小，結(jié)果逐漸接近最優(yōu)解，同時(shí)較小的交叉概率也可以一定程度上保護(hù)優(yōu)良的個(gè)體，加快算法的收斂速度。

2.3.7 變異

在進(jìn)化快結(jié)束時(shí)，種群的個(gè)體與最優(yōu)解相差越來越小。個(gè)體的適應(yīng)度和種群的平均適應(yīng)度很接近，這時(shí)就要注意種群陷入局部最優(yōu)，需要一個(gè)較大的變異概率來變異，這里的變異概率結(jié)合集中因子來考慮。如果種群最優(yōu)值與平均值相差越小，集中因子越小，變異概率越大。

變異概率為

pm=pm0-mt/T

(12)

其中，pm0為初始變異概率，m為集中因子，計(jì)算公式為m=(Fmax-Favg)/Fmax。

2.3.8 終止

終止條件為最大迭代次數(shù)或選擇出的服務(wù)滿足用戶需求時(shí)終止。

3 仿真實(shí)驗(yàn)

實(shí)驗(yàn)使用Java語言編程，JDK為jdk1.7.0_67；使用開發(fā)工具Eclipse，操作系統(tǒng)為win7，實(shí)驗(yàn)中的Web服務(wù)組合模型采用順序結(jié)構(gòu)的組合模型，數(shù)據(jù)采用QWS數(shù)據(jù)集，該數(shù)據(jù)集包含了全世界2507個(gè)Web服務(wù)的信息及調(diào)用情況，由于數(shù)據(jù)集中沒有提供價(jià)格和信譽(yù)度屬性，所以實(shí)驗(yàn)中的價(jià)格和信譽(yù)度在[0,1]區(qū)間內(nèi)隨機(jī)生成。將數(shù)據(jù)集中的數(shù)據(jù)隨機(jī)分為8個(gè)抽象服務(wù)做組合(經(jīng)計(jì)算，當(dāng)為8組時(shí)，組合規(guī)模已經(jīng)相當(dāng)大，符合實(shí)驗(yàn)需求)，每個(gè)抽象服務(wù)下有n到m個(gè)具體服務(wù)。實(shí)驗(yàn)中選擇響應(yīng)時(shí)間，價(jià)格，信譽(yù)度和可用性作為Web服務(wù)QoS的評價(jià)指標(biāo)，實(shí)驗(yàn)結(jié)果中的數(shù)據(jù)為歸一化后的值。

3.1 實(shí)驗(yàn)1

實(shí)驗(yàn)使用改進(jìn)的遺傳算法IGA與文獻(xiàn)[11]中的CGA遺傳算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖6所示，實(shí)驗(yàn)結(jié)果表明經(jīng)過改進(jìn)的遺傳算法，提高了收斂速度，具有很好的適用性。

圖6 算法比較結(jié)果

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

該實(shí)驗(yàn)中，在對Web服務(wù)選擇進(jìn)行求解時(shí)，使用改進(jìn)的遺傳算法求解，不同之處是實(shí)驗(yàn)2.1的適應(yīng)度函數(shù)中的權(quán)重直接使用用戶的主觀權(quán)重，實(shí)驗(yàn)2.2的適應(yīng)度函數(shù)中的權(quán)重為綜合考慮主客觀權(quán)重。結(jié)果表明，實(shí)驗(yàn)2.2在符合開發(fā)人員的需求的同時(shí)，還綜合考慮了服務(wù)的潛在性能，把性能更好的服務(wù)提供給開發(fā)人員。

3.2.1 實(shí)驗(yàn)2.1

實(shí)驗(yàn)中主觀權(quán)重采用直接指定的方式：響應(yīng)時(shí)間0.35、價(jià)格0.27、信譽(yù)度0.15和可用性0.3，只考慮主觀權(quán)重時(shí)最終選出的組合服務(wù)見表2，表中抽象服務(wù)i使用符號Fi表示，最后求得的組合服務(wù)的綜合值為7.057。

表2 主觀權(quán)重計(jì)算結(jié)果

3.2.2 實(shí)驗(yàn)2.2

實(shí)驗(yàn)中綜合考慮主客觀權(quán)重，主觀權(quán)重與實(shí)驗(yàn)2.1相同，客觀權(quán)重使用式(4)、式(5)計(jì)算，綜合權(quán)重使用式(6)計(jì)算，最后得到綜合權(quán)重值：響應(yīng)時(shí)間0.3、價(jià)格0.2、信譽(yù)度0.17和可用性0.33。最終選出的組合服務(wù)見表3，表中抽象服務(wù)i同樣也使用符號Fi表示，最后求得的組合服務(wù)的綜合值為7.117。

表3 主客觀權(quán)重計(jì)算結(jié)果

通過比較可以得出：主要區(qū)別體現(xiàn)在F2， 綜合考慮主客觀權(quán)重選出的服務(wù)166號，雖然響應(yīng)時(shí)間沒有18號的服務(wù)性能好，但是信譽(yù)度和可用性都提升了，總體性能更好。

4 結(jié)束語

本文針對目前Web服務(wù)選擇中屬性權(quán)重和選擇算法收斂問題，設(shè)計(jì)了一種將主客觀權(quán)重和改進(jìn)的遺傳算法相結(jié)合的方法，對基于QoS的Web服務(wù)選擇問題進(jìn)行研究。采用了一種新的鍵值對編碼方式，給解碼工作帶來了一定的便利，更加適用于Web服務(wù)選擇的編程與后續(xù)操作，在計(jì)算個(gè)體的適應(yīng)度值時(shí)結(jié)合主客觀權(quán)重進(jìn)行計(jì)算，并引入小生境思想和集中因子，提高算法的收斂速度。最后，采用QWS數(shù)據(jù)集進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明改進(jìn)的遺傳算法在收斂方面和最終效果上都有良好的表現(xiàn)。