萬里 丁沖沖

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

0 引言

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

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

1.1 Web服務(wù)組合的基本模型

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

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

圖1 Web服務(wù)組合選擇

1.2 Web服務(wù)組合的多目標(biāo)優(yōu)化問題

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

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

定義1

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

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

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

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

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

圖2 受支配解與非受支配解的關(guān)系

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

2.1 標(biāo)準(zhǔn)粒子群算法

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

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

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

標(biāo)準(zhǔn)粒子群算法流程如下：

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

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

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

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

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

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

2.2 離散粒子群算法

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

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

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

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

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

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

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

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

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

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

2.3 改進(jìn)的粒子群算法

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

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

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

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

2.4 利用改進(jìn)的粒子群算法進(jìn)行問題求解

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

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

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

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

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

2.5 算法主要流程

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

圖3 算法的主要流程

3 實驗結(jié)果分析

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

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

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

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

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

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

圖6 兩種方法對比

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

4 結(jié)束語

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

[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án)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社.

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

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

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

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