李 強(qiáng)，周井泉，張嚴(yán)凱

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

0 引 言

近年來(lái)，隨著Web服務(wù)相關(guān)標(biāo)準(zhǔn)的持續(xù)完善，越來(lái)越多的Web服務(wù)在網(wǎng)上共享，然而單個(gè)Web服務(wù)功能有限，很難滿足實(shí)際需求，因此需要將共享的Web服務(wù)組合起來(lái)，增強(qiáng)Web服務(wù)的能力。因此，關(guān)于Web服務(wù)組合的研究被提出，并吸引了工商界和學(xué)術(shù)界的廣泛關(guān)注[1]。

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

1 問(wèn)題描述

1.1 Web服務(wù)組合

一般情況下，Web服務(wù)框架由Web服務(wù)提供者、中介和Web服務(wù)需求者三部分構(gòu)成，其中Web服務(wù)需求者把自己的需求信息發(fā)送給中介，中介會(huì)根據(jù)Web服務(wù)需求者的需求從Web服務(wù)提供者提供的服務(wù)中選擇一個(gè)最優(yōu)的發(fā)送給需求者，Web服務(wù)提供者主要的任務(wù)是提供各種Web服務(wù)。

1.2 基于QoE的Web服務(wù)組合模型

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

圖1 QoE評(píng)估系統(tǒng)

指標(biāo)低中高響應(yīng)時(shí)間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表示非常滿意。

文中選取的是串聯(lián)Web服務(wù)模型，如圖2所示。適應(yīng)度函數(shù)如式(1)所示：

(1)

圖2 串聯(lián)的Web服務(wù)實(shí)例

2 算法描述

2.1 標(biāo)準(zhǔn)差分進(jìn)化算法

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

2.1.1 差分變異

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

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

(2)

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

2.1.2 交 叉

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

(3)

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

2.1.3 選 擇

DE算法是利用“貪婪”策略[7]，根據(jù)適應(yīng)值函數(shù)f(·)在目標(biāo)向量xi,g和試驗(yàn)向量ui,g中進(jìn)行篩選，選擇優(yōu)秀個(gè)體，淘汰劣質(zhì)個(gè)體。對(duì)于最小化問(wèn)題，選擇操作的方程為：

(4)

其中，xi,g+1為下一代目標(biāo)向量。

DE算法經(jīng)過(guò)差分變異、交叉、選擇操作產(chǎn)生下一代種群，如此完成種群的進(jìn)化，最終找到最優(yōu)個(gè)體。

標(biāo)準(zhǔn)差分進(jìn)化算法的基本步驟如下：

Step1:初始化種群參數(shù)，包括種群規(guī)模NP，縮放因子F，變異因子CR，進(jìn)化代數(shù)t=0；

Step3：個(gè)體評(píng)價(jià)。計(jì)算每個(gè)個(gè)體的適應(yīng)度值；

2.2 DE算法的改進(jìn)

DE算法具有高可靠性、強(qiáng)魯棒性以及良好的優(yōu)化性能，因此成為進(jìn)化計(jì)算領(lǐng)域的熱點(diǎn)課題，但DE算法也存在早熟收斂和搜索停止的問(wèn)題，除此之外DE算法還有以下缺點(diǎn)：標(biāo)準(zhǔn)DE算法的搜索性能對(duì)參數(shù)具有一定的依賴性[8]；算法在有限的情況下很難保證獲得全局最優(yōu)解，搜索能力需要進(jìn)一步提高[9]。

為了克服上述DE算法的缺點(diǎn)，提出混沌初始化和參數(shù)自適應(yīng)機(jī)制對(duì)標(biāo)準(zhǔn)DE算法進(jìn)行改進(jìn)。

2.2.1 混沌模型

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

xn+1=λ(1-xn)xn

(5)

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

式(5)中λx代表種群數(shù)的平均增長(zhǎng)率，而-λx2體現(xiàn)環(huán)境資源對(duì)種群繁衍的制約作用。通過(guò)設(shè)定初始值x0并研究數(shù)值序列x1,x2,…,xn,…的變化規(guī)律，就能得到種群繁衍的規(guī)律。

2.2.2 參數(shù)自適應(yīng)DE算法

由于DE算法的控制參數(shù)對(duì)整個(gè)算法的性能影響較大，所以對(duì)于控制參數(shù)值的選取至關(guān)重要[12]。文中提出一種自適應(yīng)機(jī)制動(dòng)態(tài)選取F和CR的值[13]。初始種群的縮放因子F和交叉率CR是隨機(jī)數(shù)產(chǎn)生的，范圍是0～1。子代種群中的F和CR通過(guò)下式得到。

(6)

(7)

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

參數(shù)自適應(yīng)DE算法的步驟如下：

Step1：初始化種群參數(shù)；

Step2：利用Logistic模型產(chǎn)生初始種群；

Step3：計(jì)算每個(gè)個(gè)體的適應(yīng)度值；

Step4：對(duì)種群進(jìn)行變異操作；

Step5:對(duì)種群進(jìn)行交叉操作；

Step6：進(jìn)行選擇操作，選出下一代種群個(gè)體；

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

Step8：對(duì)算法進(jìn)行終止檢驗(yàn)，如果達(dá)到最大進(jìn)化代數(shù)或滿足誤差要求，則停止進(jìn)化并輸出最優(yōu)個(gè)體，否則轉(zhuǎn)Step3。

3 實(shí)驗(yàn)分析

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

表3 算法的對(duì)比結(jié)果

圖3 算法平均適應(yīng)度值

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

4 結(jié)束語(yǔ)

建立了QoE的模糊專家系統(tǒng)的評(píng)估模型，并將其轉(zhuǎn)化為Web服務(wù)組合優(yōu)化問(wèn)題。在標(biāo)準(zhǔn)DE算法的基礎(chǔ)上，引入混沌初始化和參數(shù)自適應(yīng)機(jī)制對(duì)其進(jìn)行改進(jìn)，并應(yīng)用于Web服務(wù)組合優(yōu)化問(wèn)題[14]。實(shí)驗(yàn)結(jié)果表明，改進(jìn)DE算法具有很好的穩(wěn)定性和可靠性。然而，由于QoE的Web服務(wù)模型還不夠成熟，有待進(jìn)一步研究。同時(shí)，DE算法中各種參數(shù)的具體取值并不能給出統(tǒng)一的標(biāo)準(zhǔn)，仍然需要研究，這也是以后研究的重點(diǎn)。

[1] 夏亞梅，程 渤，陳俊亮，等.基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào),2012,35(2):270-281.

[2] 梁艷春，吳春國(guó)，時(shí)小虎，等.智能優(yōu)化算法理論及應(yīng)用[M].北京：科學(xué)出版社，2009.

[3] 汪定偉.智能優(yōu)化方法[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] 王 凌，錢 斌.混合差分進(jìn)化與調(diào)度算法[M].北京：清華大學(xué)出版社，2012.

[7] 何 兵，車林仙，劉初升.一種蛙跳和差分進(jìn)化混合算法[J].計(jì)算機(jī)工程與應(yīng)用,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] 劉榮輝.多階段自適應(yīng)差分進(jìn)化算法及應(yīng)用研究[D].上海：東華大學(xué)，2012.