基于Pareto解集的Web服務組合推優(yōu)方案

萬里 丁沖沖

南京財經(jīng)大學信息工程學院 江蘇 210046

0 引言

本文提出一種基于Pareto解集的多目標粒子群算法來解決多目標的Web服務組合全局優(yōu)化問題，利用粒子群算法的尋優(yōu)策略，對問題進行建模優(yōu)化，并對已有算法本身存在的一些不足地方，進行分析和改進，最終產(chǎn)生滿足用戶需求的一組Pareto非劣解集，供用戶來進行選擇。

1 Web服務組合選擇的多目標優(yōu)化模型

1.1 Web服務組合的基本模型

一個 Web服務組合通常由提供不同的簡單功能的多個Web服務構成，這些不同功能的子服務通常相互之間彼此獨立。常用的Web服務組合的結構有四種，分別是順序結構，并行結構，選擇結構和循環(huán)結構。

在實際的應用中，提供功能相同或相似的Web服務數(shù)量較多，它們在功能上可以相互替代，但它們具有不同的非功能屬性，例如服務的執(zhí)行時間，執(zhí)行價格，可信度以及可用性等。在Web服務進行組合的時候，需要按照指定的任務完成相應的功能，對于每個不同的任務，只包含相應的描述信息和接口信息，不指向具體的服務，我們稱之為抽象服務。這樣對復雜功能的Web服務，都有一定數(shù)量的抽象服務組合而成，在真正執(zhí)行的時候，這些抽象服務將從候選服務里選出具體的服務來實現(xiàn)，通常抽象服務的候選服務有一個或者多個。以順序結構為例，如圖1中所示，S代表Web服務執(zhí)行的起點，T代表終點，Wi為第i個抽象服務，Wi，j代表第i個抽象服務的第j個候選服務，其中(1≤i≤n，1≤j≤m)。

圖1 Web服務組合選擇

1.2 Web服務組合的多目標優(yōu)化問題

考慮到Web服務的非功能屬性通常具有多個評價參數(shù)。因此，很難找到一個全方位的最優(yōu)解，使得組合的效果在各個屬性方向上同時達到最優(yōu)解，而且一些屬性本身就具有互相偏離性，比如說時間短的服務與價格低的服務關系，或者價格低的服務與可信度高的服務的關系，通常這些服務的屬性很難達到一致最優(yōu)。所以只能對各個目標折中求解，使得各個目標盡可能符合用戶需要。以往的處理方法往往是對各個目標進行線性加權，利用一個評價函數(shù)尋求多個目標的平衡，但這種方法會帶來諸多問題。

本文采用的是利用多目標求解方法，將多個目標函數(shù)作為一個目標向量考慮，該目標向量的維數(shù)由屬性的個數(shù)確定。求得目標向量通常會不止一個，所求得的這些向量之間，不存在一向量在任何一個目標上比另一個向量好，但同時其他目標也不差的更好解。這些解構成的集合稱為Pareto最優(yōu)解集，單個解稱為Pareto最優(yōu)解或者非劣解。多目標優(yōu)化的幾個基本概念如下：

定義1

(1) Pareto支配：解x0支配x1(x0? x1)當且僅當

(2) Pareto最優(yōu):如果解x0是Pareto最優(yōu)的當且僅當┐?x1：x1? x0。

(3) Pareto最優(yōu)集：所有Pareto最優(yōu)解的集合Ps={ x0|┐?x1? x0}

(4) Pareto最優(yōu)前端或均衡面或Pareto前端：所有Pareto最優(yōu)解對應的目標函數(shù)值所形成的區(qū)域PF：

以兩目標為例，圖2描述了受支配解和非受支配解在目標空間的分布。

圖2 受支配解與非受支配解的關系

2 基于粒子群算法的Web服務組合描述

2.1 標準粒子群算法

粒子群算法和其他進化算法類似，也是根據(jù)對環(huán)境的適應度將種群中的個體移動到好的區(qū)域，與其他進化算法不同，它不對個體使用進化算子，而將每個個體看成是搜索空間中的一個沒有體積沒有質(zhì)量的粒子，在搜索空間中以一定的速度飛行，并根據(jù)個體和集體飛行的經(jīng)驗的綜合分析來動態(tài)調(diào)整這個速度。

標準PSO中，粒子在搜索空間的速度和位置根據(jù)如下的公式確定：

式中，w為慣性權重；r1、r2為加速常數(shù)；rand()為區(qū)間[0,1]上均勻分布的隨機數(shù)；Pt和Gt分別為t時刻粒子的自身最好位置pbest和全局最好位置gbest。pbest為粒子自身飛過的最好位置，而 gbest為粒子所對應的全局最好位置，它是整個群體所經(jīng)歷的最好位置。xt=(xt1,xt2,…,xm)與 vt=(vt1,vt2,…,vm)為時刻t的位置與速度。

標準粒子群算法流程如下：

(1) 初始化粒子群，隨機產(chǎn)生所有粒子的位置和速度并確定粒子的pbest和gbest。

(2) 對每個粒子，將它的當前位置與它經(jīng)歷的最好位置pbest進行比較，如果當前位置更好，則將其作為當前的最好位置pbest，否則，pbest保持不變。

(3) 對每個粒子，將它的當前位置和群體中所有粒子所經(jīng)歷的最好位置 gbest作比價，如果這個粒子的位置更好，則將其設置為當前的gbest；否則gbest保持不變。

(4) 更新粒子的速度和位置。

(5) 如未達到結束條件(通常為預定的運算精度或迭代次數(shù))，返回步驟(2)。

(6) 開始下一輪迭代計算；否則，取當前gbest為最優(yōu)解。

2.2 離散粒子群算法

標準粒子群算法只要通過簡單的變換就能夠?qū)B續(xù)空間求最優(yōu)解取得很好的效果。但是在實際應用中，問題空間往往都在離散空間中，而標準粒子群算法往往較難處理。在標準粒子群基礎上，一些研究者提出了離散粒子群算法(DPSO)，此類方法的研究大致有兩個處理方向，一個是仍將離散空間中的組合優(yōu)化問題轉(zhuǎn)化成為連續(xù)空間中來處理，再按照標準粒子群的方法，對粒子的速度和位置進行更新和改變；而另一個方向是對粒子的速度、位置信息等進行重新的編碼，其更新的機理也會隨著具體問題的不同，而具有相對的靈活性和針對性。

基于連續(xù)空間的離散粒子群算法，以二進制編碼的粒子群算法(BPSO)為代表，該算法首先由Kennedy和Eberhart提出，作者定義了一個sigmoid模糊函數(shù)：

相應的將位置更新公式變?yōu)椋?/p>

其中rand為[0,1]之間均勻分布的隨機數(shù)，在標準粒子群算法中，當前速度對下一時刻的粒子飛行方向和位置產(chǎn)生影響，使得搜索在一定的空間范圍內(nèi)變動。但是在BPSO中，速度的定義已經(jīng)改變，通過sigmoid模糊函數(shù)，表示粒子位置取1的概率為S(vt),取0的概率為1-S(vt)。由于BPSO保留了標準粒子群算法中較多的更新方式，所以很多在處理連續(xù)空間上的方法都可以使用，但是由于BPSO二進制編碼的局限性，所以該算法的應用領域并不是很廣，對一些組合優(yōu)化問題并不是很好的解決方法。

目前針對離散空間的DPSO研究較少，Clerc教授最先提出一種基于離散點位置交換的改進粒子群算法并成功求解了旅行商問題。在此算法中，位置標示為一個離散值向量，而速度則表示粒子的運動趨勢，這樣位置在交換前和交換后均為離散值。此算法在保持標準粒子群公式的條件下，改變了運算符號的意義，其新的符號分別為：

1，位置減操作Θ：例如xΘy，表示一個速度，即粒子由x朝y方向飛行。

2，速度加操作⊕：表示兩個速度的疊加，先按照第一個速度移動，再按照第二個速度移動。

3，位置加速度操作⊕：位置加上某一個速度后，得到一個新的位置。

4，系數(shù)乘速度操作?：表示以這個系數(shù)為概率來按照這個速度移動位置。

基于離散空間的DPSO與標準粒子群算法的運動方式有很大不同，粒子不是通過在解空間內(nèi)連續(xù)的運動方式來向最優(yōu)解靠攏，而是采取跳動的方式來尋找，這種方式能夠減小上一代粒子對下一代粒子的影響，從而能夠更好的進行尋優(yōu)。

2.3 改進的粒子群算法

上文中，Clerc提出的算法是針對特定的旅行商問題，粒子的運動方式也僅僅適用于存在值序概念的組合優(yōu)化問題，而對Web服務組合問題并不好直接應用。通過分析發(fā)現(xiàn)，在Web服務組合問題上，可以對離散空間的DPSO算法做進一步的改進。由于Web服務的各個抽象服務之間具有相對的獨立性，并且各個抽象服務的候選服務之間相互的關聯(lián)度也很低，因此在此離散空間的尋優(yōu)問題上，粒子由當前位置跳到下一位置的過程中，速度并不像標準粒子群算法那樣有效的影響到尋優(yōu)結果和收斂速度，因此位置的更新機理就成為考慮的重點。

為此，提出一種針對Web服務組合特點的基于離散空間的位置采取跳動方式的改進粒子群算法。該算法結合蟻群算法的思想和遺傳算法的思想，并將三種算法結合起來，使得算法更加簡單有效。在蟻群算法中，螞蟻在尋找食物過程中選擇路線會傾向于信息濃度較高的一條作為前進方向，在整個群體共同發(fā)揮作用下，能夠一條發(fā)現(xiàn)最優(yōu)解的路徑。所以在粒子群算法中可以引進這種思想，使得粒子在更新過程中，也能夠受到一定的因素影響。但是粒子群算法在搜索過程中，單個粒子只會保留下其最優(yōu)信息，一旦多個粒子聚集在同一位置，將很難跳出此局部最優(yōu)位置，最終無法找到全局最優(yōu)解。針對粒子群算法收斂速度快但容易陷入局部最優(yōu)的特點，可以借助遺傳算法的變異策略，對部分粒子進行一定的擾動，從局部最優(yōu)解跳出，使得搜索空間覆蓋更廣。本文采取的是對每一個粒子以一定的概率進行變異，并在每一代粒子中都進行變異，這樣能有效防止局部最優(yōu)解被保留下來。

以上通過對問題以及三種算法的簡單分析，提出了一種新型的交換粒子群算法公式：

其中a1,a2均為0-1之間的數(shù)，Pkbest代表第k代粒子的最好位置，Pkgbest代表第k代所有粒子的最好位置，xk+1代表第k+1代粒子的位置。通過此公式進行更新時，第k+1代粒子將以概率a1取得第k代粒子的最好位置，以概率(1- a1)×a2取得第k代所有粒子的最好位置，以概率(1- a1)×(1-a2)來選取隨機的位置。通過改變a1和a2的值，使得粒子既能夠?qū)ψ陨淼男畔⒁欢ǔ潭壬系谋Ａ?，又能夠不斷更新自身的信息，同時還可以給粒子帶來類似遺傳算法中變異的效果，此公式還精簡了粒子群算法中的更新方式，從而使得該算法對整個問題的求解變得簡單而有效。

2.4 利用改進的粒子群算法進行問題求解

利用粒子群算法對Web服務組合模型進行編碼，其主要思想為：將一個Web服務組合方案看作是粒子群中一個飛行的粒子，粒子的維數(shù)代表一個Web服務組合的抽象服務的個數(shù)，而在每一維上的位置則代表了相應的候選服務。這樣，一旦每一個粒子的維數(shù)以及粒子每一維上的位置確定下來，該粒子就表示了一個確定的Web服務組合方案，而粒子在每一維上的位置的變化，則代表Web服務組合過程中用來實現(xiàn)抽象服務的候選服務的變化，每一個粒子通過改變在各維上的位置來更新自身的最優(yōu)解，而全局最優(yōu)解集通過各個粒子的最優(yōu)解的更新以及多次迭代來實現(xiàn)更新。

粒子的初始化。Web服務組合的維數(shù)為N，每一維上的候選服務為M個，先對每一維的Web抽象服務進行編號，在對這些抽象服務的候選服務進行編號，Wi，j代表第i個抽象服務的第 j個候選服務，其中(1≤i≤N，1≤j≤M)，再對每一個Web服務給定各個屬性的初值，將Web服務的編號，位置和屬性關聯(lián)起來，通過編號即可以獲得每一個Web服務相應的位置和屬性。每一個粒子只包含 Web服務的位置信息，例如粒子信息如下(7,9,3)，表示W(wǎng)eb服務組合中有3個抽象服務，第1個抽象服務選擇其候選服務中的第7個，第2個抽象服務選擇其候選服務中的第9個，第3個抽象服務選擇其候選服務中的第3個。粒子的初始位置可以作為粒子的初始最好位置。

適應度的計算。每一個粒子代表一個 Web服務組合方案，可以將粒子在各維上的數(shù)據(jù)取出，按照相應的Web服務組合模型方案進行計算，在本文中，Web服務組合QoS中的時間和價格按照簡單的疊加即可，而可信度和可用性按照疊乘即可，這樣適用度的優(yōu)劣，對于全局時間和價格越低越好，而全局的可信度和可用性則越高越好。

粒子群的初始化及更新，初始化一組粒子群，并將第一個粒子作為臨時參考最優(yōu)個體，對每一個粒子進行評價，如果有粒子可以支配臨時參考最優(yōu)個體，則用這個粒子替代臨時參考最優(yōu)個體，如果沒有粒子可以支配臨時參考最優(yōu)個體，則不必更新，最后再將不被這個臨時參考最優(yōu)解支配的其他解記錄下來。

最優(yōu)解的保留，將上一步進行多次的迭代，將每次記錄下來的解都放在一個外部的空間中，因為上一步中的臨時參考最優(yōu)解，具有很強的支配性，因此，不被它支配的解，也不容易被其他的解支配，而經(jīng)過多次迭代后，這些解最終只會在這個外部檔案中被支配，不會被外部檔案以外的解支配，再將最后一次迭代的臨時參考最優(yōu)解放入這個檔案中來。最后，對這個外部空間中的所有解，進行排劣操作，將被支配的解從這個空間中刪除掉，從而外部空間中的解之間不再具備支配關系，此時得到的解的集合便是Pareto最優(yōu)解集，從而得到Pareto最優(yōu)組合方案，其他所有的Web服務組合方案都不會在服務質(zhì)量上支配這些方案，從而可以將這些方案推薦給用戶，供用戶選擇。

2.5 算法主要流程

根據(jù)上面分析，針對本文所述Web服務組合問題的求解流程圖如圖3所示。

圖3 算法的主要流程

3 實驗結果分析

本文實驗的硬件環(huán)境為一臺pc機，主要配置如下：intel CORE i3處理器，主頻 2.4GHz，內(nèi)存 4G。軟件環(huán)境為windows7操作系統(tǒng)以及Myeclipse8.5，采用java實現(xiàn)。實驗中的Web服務的任務數(shù)為10個，屬性采用模擬方式實現(xiàn)，屬性包括時間，價格，可信度以及可靠性，取值范圍分別為：0

圖4為在考慮兩目標情況下，不同數(shù)量的候選服務，在不同的迭代次數(shù)下的程序運行時間的變化情況。通過圖4可以看出，當候選服務數(shù)量相同時，隨著迭代次數(shù)的增加，程序運行時間也隨著增加，基本是線性的變化。相同的迭代次數(shù)，候選服務數(shù)量越大，運行時間越長，候選服務數(shù)量差值相同時，運行時間的差值變化也不大，可以近似認為運行時間與候選服務規(guī)模呈線性關系。

圖4 不同迭代次數(shù)和不同規(guī)模候選下的運行時間

圖5為在不同候選服務數(shù)量下，考慮不同的屬性個數(shù)時，程序運行時間的變化情況。下圖反應的是，考慮相同屬性個數(shù)時，隨著候選服務的增加，程序運行時間呈線性的增加，而相同的候選服務數(shù)量時，隨著屬性個數(shù)的不同則對運行時間有較大影響，隨著屬性個數(shù)的增加，程序運行時間急劇的增長，說明Web服務屬相的個數(shù)對程序運行時間起主要作用。

圖5 不同候選服務和不同屬性個數(shù)的運行時間

圖6 分別為本文方法與文獻[4]中的方法，在考慮兩目標情況下，不同的候選服務數(shù)量下程序運行的時間對比，通過圖6可以看出，本文的方法程序運行時間與候選服務數(shù)量呈線性關系，且運行時間分布在一個不大的變化區(qū)間內(nèi)。而普通的MOPSO算法則隨著候選服務數(shù)量的增加，程序運行的時間快速的上升。在候選服務規(guī)模較小時，兩方法的程序運行時間相差不大，但在候選服務數(shù)量較大時，本文方法的程序運行時間要遠遠小于文獻[4]中提出的方法。

圖6 兩種方法對比

從以上的各個對比試驗及分析，可總結出以下結論：Web服務組合的多目標優(yōu)化問題，首要影響求解速度的因素是考慮問題屬性的個數(shù)，即目標數(shù)量，其次是候選服務的規(guī)模。目標數(shù)量對求解速度起到主要作用，候選規(guī)模的大小對求解起到次要作用。

4 結束語

本文針對Web服務組合多目標優(yōu)化問題的特點，簡化了已有的PSO中對此類問題沒有必要的步驟，改進了已有PSO算法，并結合了其他的進化算法的思想，使得提出的算法能夠很好地解決Web服務組合多目標優(yōu)化問題，尤其在規(guī)模較大問題上與已有的多目標粒子群求解 Web組合方法相比較具有明顯的高效性。今后將在如何協(xié)調(diào)效率以及問題難度和精確度上做進一步的研究。

[1]Wan Shuchao, Wei Jun, Song Jingyu, et al. Developing a selection model for interactive Web services [C] //Proc of IEEE ICWS 06. Piscataway,NJ:IEEE.2006.

[2]雷德明,嚴新平.多目標智能優(yōu)化算法及其應用[M].北京:科學出版社.

[3]夏虹,李增智.粒子群算法求解Web服務組合中基于QoS的服務選擇[J].北京郵電大學學報.2009.

[4]徐濤,王新環(huán).基于多目標粒子群優(yōu)化算法的Web服務組合[J].計算機工程與設計.2010.

[5]孫學勝,曹玖新,劉波.基于多目標粒子群優(yōu)化的服務選擇算法[J].東南大學學報.2009.

[6]范小芹,蔣昌俊.基于離散微粒群算法的動態(tài)Web服務選擇[J].計算機研究與發(fā)展.2010.