基于參數自適應差分進化算法的Web服務組合

李 強，周井泉，張嚴凱

(南京郵電大學 電子科學與工程學院，江蘇 南京 210003)

0 引 言

近年來，隨著Web服務相關標準的持續完善，越來越多的Web服務在網上共享，然而單個Web服務功能有限，很難滿足實際需求，因此需要將共享的Web服務組合起來，增強Web服務的能力。因此，關于Web服務組合的研究被提出，并吸引了工商界和學術界的廣泛關注[1]。

目前評價服務質量多采用QoS(quality of service)，但QoS只能從性能層面反映Web服務的質量，不能反映用戶的滿意程度。為了更加精確地反映用戶對Web服務的滿意程度，體驗質量(quality of experience，QoE)便應運而生。目前解決Web服務組合問題的主流算法為智能優化算法[2-3]，文中應用的是參數自適應DE算法。DE算法具有高可靠性、強魯棒性以及良好的優化性能，但同時也有早熟收斂和搜索停滯等缺點，于是在標準DE算法的基礎上，引入混沌初始化[4-5]和參數自適應機制，不僅避免了DE算法本身的缺點，還能提高其性能和穩定性。

1 問題描述

1.1 Web服務組合

一般情況下，Web服務框架由Web服務提供者、中介和Web服務需求者三部分構成，其中Web服務需求者把自己的需求信息發送給中介，中介會根據Web服務需求者的需求從Web服務提供者提供的服務中選擇一個最優的發送給需求者，Web服務提供者主要的任務是提供各種Web服務。

1.2 基于QoE的Web服務組合模型

QoE的Web服務組合模型框架如圖1所示。文中選取響應時間、可用性、可靠性三個參數作為QoS的評價指標，并在Web服務組合模型中引入模糊理論與專家系統，通過隸屬函數和推理規則確定QoE的值(見表1和表2)。一般情況下，模糊集可分為三角形模糊集和梯形模糊集，文中選取梯形模糊集。

圖1 QoE評估系統

指標低中高響應時間TT≤0.20.2≤T≤0.6T>0.6可靠性RR≤0.250.25≤R≤0.8R>0.8可用性AA≤0.30.30.8

表2 滿意程度

注：0表示非常不滿意，1表示不滿意，2表示較差，3表示一般，4表示良好，5表示滿意，6表示非常滿意。

文中選取的是串聯Web服務模型，如圖2所示。適應度函數如式(1)所示：

(1)

圖2 串聯的Web服務實例

2 算法描述

2.1 標準差分進化算法

差分進化算法(DE算法)是在解的可行域范圍內產生一個隨機種群，然后對該隨機種群進行變異、交叉、選擇操作，產生新一代種群[6]。DE算法基于實數編碼，它首先在所要解決問題的可行解空間生成隨機種群：xi=(xi,1,xi,2,…,xi,D),i=1,2,…,NP。其中,D為問題維數;NP為種群規模。

2.1.1 差分變異

在DE算法中，變異操作是把種群中的個體進行差分操作，把得到的差分向量乘以縮放因子后再加上種群中另一個體得到一個新的變異個體。根據不同的變異操作形成了不同的變異策略。其中一種最常見的變異策略DE/rand/1的方程為：

vi,g=xr1,g+F·(xr2,g-xr3,g)

(2)

其中,r1≠r2≠r3≠i;F為縮放因子。

2.1.2 交 叉

交叉操作生成實驗向量，DE算法有兩種交叉方式，即二項式交叉和指數交叉(文中只介紹二項式交叉)。二項式交叉操作的方程為：

(3)

其中，j=1,2,…,D;jrand為[1,D]隨機產生的整數；CR∈(0,1)為交叉率。

2.1.3 選 擇

DE算法是利用“貪婪”策略[7]，根據適應值函數f(·)在目標向量xi,g和試驗向量ui,g中進行篩選，選擇優秀個體，淘汰劣質個體。對于最小化問題，選擇操作的方程為：

(4)

其中，xi,g+1為下一代目標向量。

DE算法經過差分變異、交叉、選擇操作產生下一代種群，如此完成種群的進化，最終找到最優個體。

標準差分進化算法的基本步驟如下：

Step1:初始化種群參數，包括種群規模NP，縮放因子F，變異因子CR，進化代數t=0；

Step3：個體評價。計算每個個體的適應度值；

2.2 DE算法的改進

DE算法具有高可靠性、強魯棒性以及良好的優化性能，因此成為進化計算領域的熱點課題，但DE算法也存在早熟收斂和搜索停止的問題，除此之外DE算法還有以下缺點：標準DE算法的搜索性能對參數具有一定的依賴性[8]；算法在有限的情況下很難保證獲得全局最優解，搜索能力需要進一步提高[9]。

為了克服上述DE算法的缺點，提出混沌初始化和參數自適應機制對標準DE算法進行改進。

2.2.1 混沌模型

由于混沌具有隨機性、遍歷行和規律性等特點[10]，利用混沌遍歷性的特點有助于避免智能算法在搜索過程中陷入局部最優[11]。典型的混沌模型有Logistic混沌模型、Tent混沌模型，文中使用Logistic混沌模型。Logistic模型遞推方程如下：

xn+1=λ(1-xn)xn

(5)

其中，0≤xn≤1,n=0,1,2…；λ在0～4中取值，當λ=4時，式(5)所表示的系統處于混沌狀態。

式(5)中λx代表種群數的平均增長率，而-λx2體現環境資源對種群繁衍的制約作用。通過設定初始值x0并研究數值序列x1,x2,…,xn,…的變化規律，就能得到種群繁衍的規律。

2.2.2 參數自適應DE算法

由于DE算法的控制參數對整個算法的性能影響較大，所以對于控制參數值的選取至關重要[12]。文中提出一種自適應機制動態選取F和CR的值[13]。初始種群的縮放因子F和交叉率CR是隨機數產生的，范圍是0～1。子代種群中的F和CR通過下式得到。

(6)

(7)

利用式(6)、式(7)可以讓每個子代種群中每個個體擁有各自的縮放因子F和交叉率CR，這樣便可完成參數的自適應。

參數自適應DE算法的步驟如下：

Step1：初始化種群參數；

Step2：利用Logistic模型產生初始種群；

Step3：計算每個個體的適應度值；

Step4：對種群進行變異操作；

Step5:對種群進行交叉操作；

Step6：進行選擇操作，選出下一代種群個體；

Step7：根據式(6)、(7)計算出下一代種群個體的縮放因子F和交叉率CR；

Step8：對算法進行終止檢驗，如果達到最大進化代數或滿足誤差要求，則停止進化并輸出最優個體，否則轉Step3。

3 實驗分析

為了驗證參數自適應DE算法的性能，選取了串聯Web服務模型，如圖2所示，其中設定m=10、n=10。參數設置：初始種群的縮放因子F和交叉率CR分別由Rand(0.1,1.0)和Rand(0.0,1.0)產生，種群規模NP=200，算法最大迭代次數G=100，實驗次數為200。鑒于目前沒有統一的實驗平臺和相關數據集，QoS的屬性值均由隨機函數產生，取值范圍為0～1。表3中顯示的數據是經過200次實驗后所取的平均值。算法比較結果如圖3所示。

表3 算法的對比結果

圖3 算法平均適應度值

從圖3和表3中可以看出，自適應DE算法的平均值、最劣解、最優解都大于其他算法，方差和運行時間較小，具有較好的收斂速度和穩定性。因此參數自適應DE算法具有良好的性能。

4 結束語

建立了QoE的模糊專家系統的評估模型，并將其轉化為Web服務組合優化問題。在標準DE算法的基礎上，引入混沌初始化和參數自適應機制對其進行改進，并應用于Web服務組合優化問題[14]。實驗結果表明，改進DE算法具有很好的穩定性和可靠性。然而，由于QoE的Web服務模型還不夠成熟，有待進一步研究。同時，DE算法中各種參數的具體取值并不能給出統一的標準，仍然需要研究，這也是以后研究的重點。

[1] 夏亞梅，程 渤，陳俊亮，等.基于改進蟻群算法的服務組合優化[J].計算機學報,2012,35(2):270-281.

[2] 梁艷春，吳春國，時小虎，等.智能優化算法理論及應用[M].北京：科學出版社，2009.

[3] 汪定偉.智能優化方法[M].北京：高等教育出版社，2007.

[4] LU Y,ZHOU J,QIN H,et al.Chaotic differential evolution methods for dynamic economic dispatch with valve-point effects[J].Engineering Applications of Artificial Intelligence,2011,24(2):378-387.

[5] GU P,XIU C,CHENG Y,et al.Adaptive ant colony optimization algorithm[C]//International conference on mechatronics and control.[s.l.]:IEEE,2014:95-98.

[6] 王 凌，錢 斌.混合差分進化與調度算法[M].北京：清華大學出版社，2012.

[7] 何 兵，車林仙，劉初升.一種蛙跳和差分進化混合算法[J].計算機工程與應用,2011,47(18):4-8.

[8] WEBER M,NERI F,TIRRONEN V.A study on scale factor in distributed differential evolution[J].Information Sciences,2011,181(12):2488-2511.

[9] NEKOVEE M.Epidemic algorithms for reliable and efficient information dissemination in vehicular[J].Intelligent Transport Systems,2009,3(2):104-110.

[10] ZHANG C,CHEN J,XIN B.Distributed memetic differential evolution with the synergy of Lamarckian and baldwinian learning[J].Applied Soft Computing,2013,13(5):2947-2959.

[11] MCGINLEY B,MAHER J,O’RIORDAN C,et al.Maintaining healthy population diversity using adaptive crossover,mutation and selection[J].IEEE Transactions on Evolutionary Computation,2011,15(5):692-714.

[12] CAPONIO A,NERI F,TIRRONERN V.Super-fit control adaption in memetic differential evolution frameworks[J].Soft Computing,2009,13(8):811-831.

[13] KAELO P,ALI M M.Differential evolution algorithms using hybrid mutation[J].Computational Optimization and Applications,2007,37(2):231-246.

[14] 劉榮輝.多階段自適應差分進化算法及應用研究[D].上海：東華大學，2012.