萬里 丁沖沖

南京財經大學信息工程學院 江蘇 210046

0 引言

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

1 Web服務組合選擇的多目標優化模型

1.1 Web服務組合的基本模型

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

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

圖1 Web服務組合選擇

1.2 Web服務組合的多目標優化問題

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

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

定義1

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

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

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

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

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

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

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

2.1 標準粒子群算法

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

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

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

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

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

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

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

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

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

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

2.2 離散粒子群算法

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

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

相應的將位置更新公式變為：

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

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

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

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

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

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

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

2.3 改進的粒子群算法

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

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

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

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

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

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

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

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

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

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

2.5 算法主要流程

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

圖3 算法的主要流程

3 實驗結果分析

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

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

圖4 不同迭代次數和不同規模候選下的運行時間

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

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

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

圖6 兩種方法對比

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

4 結束語

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

[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]雷德明,嚴新平.多目標智能優化算法及其應用[M].北京:科學出版社.

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

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

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

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