煙花粒子群優(yōu)化算法在Web服務(wù)組合上的應(yīng)用

郭 星，陳姍姍，張以文，李 煒

1(安徽大學(xué) 計算智能與信號處理教育部重點(diǎn)實(shí)驗室，合肥 230039)

2(安徽大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601)

1 引 言

隨著大數(shù)據(jù)與云計算技術(shù)的發(fā)展，越來越多的企業(yè)與組織機(jī)構(gòu)以服務(wù)的形式發(fā)布他們的應(yīng)用資源[1]，Big service[2]應(yīng)運(yùn)而生.單一的Web服務(wù)往往不能滿足復(fù)雜的用戶需求，服務(wù)組合變得相當(dāng)重要[3].服務(wù)組合過程中存在大量功能相同而QoS不同的候選服務(wù)，QoS感知的服務(wù)組合已成為研究熱點(diǎn).QoS通常包括：響應(yīng)時間、可用性、吞吐量等[4].

針對QoS感知的Web服務(wù)組合優(yōu)化問題，目前的解決方法可分為三種[5]：

1)局部搜索方法，不同的QoS屬性值通過一個聚合函數(shù)被映射為單一指標(biāo)，在多指標(biāo)決策過程中，從每個候選服務(wù)集中選擇一個具體的服務(wù)來構(gòu)成一個組合服務(wù).這種方法對于有少量QoS限制條件的服務(wù)組合有效果，但對于大規(guī)模的有QoS屬性限制的服務(wù)組合效率很低.

2)全局優(yōu)化方法，這種方法將整個服務(wù)組合問題轉(zhuǎn)化為一個混合線性規(guī)劃問題，通過一個線性函數(shù)來尋找解決方案.這種方法的對選擇最優(yōu)組合服務(wù)的算法有一定程度的限制，所求的目標(biāo)函數(shù)必須是線性的，不能完全適用于解決Web服務(wù)組合問題.

3)智能優(yōu)化算法，解決了全局優(yōu)化算法的缺點(diǎn)，常被用來解決服務(wù)組合問題.文獻(xiàn)[6]給出有關(guān)聯(lián)關(guān)系的服務(wù)模型，使用遺傳算法來進(jìn)行服務(wù)組合查找，提出了一種云制造中有關(guān)聯(lián)意識的服務(wù)組合選擇方法.

文獻(xiàn)[7]使用粒子群算法來解決Web服務(wù)組合優(yōu)化問題.作為解決服務(wù)優(yōu)化問題的兩種典型算法，與遺傳算法相比，粒子群算法具有參數(shù)少、收斂速度快的特點(diǎn)，在很多優(yōu)化問題上表現(xiàn)出良好的搜索能力，但粒子群算法也會出現(xiàn)早熟現(xiàn)象，容易產(chǎn)生陷入局部最優(yōu)問題[8].文獻(xiàn)基于適應(yīng)性并行與串行小生境技術(shù)提出了一種子種群粒子群優(yōu)化算法[9]，在子種群的網(wǎng)格搜索單元中，根據(jù)可行解的密度來尋找最優(yōu)解，在增加種群的搜索能力的同時，種群多樣性會降低.文獻(xiàn)[10]提出了一種將候選服務(wù)分類的方法，來解決大規(guī)模的Web服務(wù)組合問題.本文針對全局服務(wù)質(zhì)量的Web服務(wù)組合優(yōu)化問題，提出了一種改進(jìn)的粒子群算法FWPSO，在增加種群多樣性的同時，進(jìn)行了防早熟處理，并提高了種群的搜索能力.理論分析和實(shí)驗結(jié)果表明，在Web服務(wù)組合優(yōu)化問題上，F(xiàn)WPSO有更好的綜合性能.

2 Web服務(wù)組合問題模型

2.1 組合服務(wù)生成過程

組合服務(wù)的生成過程是一個根據(jù)用戶提交的任務(wù)信息，來尋找滿足用戶要求的組合服務(wù)過程.其過程主要分兩步進(jìn)行，即服務(wù)尋找過程與服務(wù)組合過程.在服務(wù)尋找過程中，將用戶提交的任務(wù)抽象為多個子任務(wù)，各個子任務(wù)間有不同的執(zhí)行關(guān)系.在基于工作流方法的Web服務(wù)組合中，對于子任務(wù)的執(zhí)行關(guān)系，工作流管理聯(lián)盟(WFMC)定義了4種基本模型，即順序(Sequence)、并行(Parallel)、選擇(Selective)，循環(huán)(Circular)等.在定義的基本模型中，循環(huán)、并行與選擇模型均可轉(zhuǎn)化為順序模型，本文選取順序模型作為研究對象.每個子任務(wù)對應(yīng)一個候選服務(wù)集，候選服務(wù)集由多個有著功能性相同而非功能性屬性不同的服務(wù)構(gòu)成，這些服務(wù)的每個屬性都滿足用戶的需求.每個子任務(wù)根據(jù)用戶提交的QoS屬性要求，從相應(yīng)的候選服務(wù)集中選擇一個候選服務(wù).

2.2 QoS預(yù)處理

在組合服務(wù)的生成過程中，為了評估每個組合服務(wù)，需要計算組合服務(wù)的適應(yīng)度值.由于Web服務(wù)的QoS每個屬性取值范圍有較大差別，不在同一個計算等級上，在進(jìn)行Web服務(wù)評估之前，必須先將QoS屬性值進(jìn)行預(yù)處理.屬性值預(yù)處理方法有多種，本文使用文獻(xiàn)[7]中方法對Web服務(wù)的屬性進(jìn)行與處理，將屬性值區(qū)間限定為[0，1].

3 基于FWPSO算法的服務(wù)組合

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

(1)

(2)

其中，c1和c2為學(xué)習(xí)因子，決定全局最優(yōu)位置和歷史最優(yōu)位置對粒子的影響程度，r1和r2為[0，1]區(qū)間上均勻分布的隨機(jī)變量.w為慣性權(quán)重，衡量著遷移時刻的速度對下次移動的影響，w值越大，表明此刻的速度對粒子下次移動的影響較大.

3.2 FWPSO算法的改進(jìn)機(jī)制

3.2.1 粒子活躍度檢測

在種群粒子尋找最優(yōu)解的過程中，粒子的多樣性對種群尋找最優(yōu)粒子有較大影響，也決定了使用粒子群算法能否找到最優(yōu)的組合服務(wù).根據(jù)搜索策略，經(jīng)過多次搜索，若粒子活動范圍小，則尋優(yōu)效果對整個種群影響不大.在本文中，引入粒子活躍度檢測機(jī)制，通過粒子的活躍度檢測，來替換不活躍粒子，增加種群多樣性.機(jī)制具體思想：在迭代過程中，記錄每個粒子的歷史最優(yōu)位置未更新次數(shù)，若粒子不是種群最優(yōu)粒子，且粒子的歷史最優(yōu)位置未更新次數(shù)達(dá)到一定的閾值，則認(rèn)為此粒子的活動范圍較小，活躍度不高，多次迭代未能逃離粒子局部搜索區(qū)域，找到的歷史最優(yōu)解決方案不變.通過重新初始化此粒子，隨機(jī)獲取粒子的位置，增加種群多樣性.

3.2.2 粒子煙花學(xué)習(xí)機(jī)制

在種群粒子尋找Web組合服務(wù)的最優(yōu)解決方案過程中，每個粒子的歷史最優(yōu)位置對粒子的移動有較大影響.本文中，采用一種新的粒子學(xué)習(xí)機(jī)制，在粒子的歷史最優(yōu)位置周圍尋找更優(yōu)的粒子，增強(qiáng)種群粒子的搜索能力.我們采用煙花算法[12]中的基于煙花爆炸半徑計算原理尋找最優(yōu)解的思想來指導(dǎo)粒子學(xué)習(xí).對于一個多目標(biāo)求解問題，每個煙花被看作一個可行解，采取煙花爆炸學(xué)習(xí)機(jī)制，在粒子歷史最優(yōu)位置周邊進(jìn)行搜索.根據(jù)煙花爆炸半徑的公式計算粒子在歷史最優(yōu)位置的搜索半徑.煙花爆炸半徑如公式(3)所示：

(3)

粒子進(jìn)行煙花學(xué)習(xí)的算法流程如下：

Algorithm1粒子煙花學(xué)習(xí)機(jī)制

For each i

If(the ith particle is not best particle)

Gengrate Ai

For(j

End for

End if

End for

3.2.3 粒子自反向?qū)W習(xí)

在種群粒子搜索過程中，全局最優(yōu)粒子對于種群粒子位置的遷移具有牽引作用.經(jīng)過多次迭代，種群大量粒子會圍繞在局部最優(yōu)粒子周圍，種群粒子尋找組合服務(wù)最優(yōu)解決方案的范圍逐漸縮小.為解決這一問題，引入粒子反向?qū)W習(xí)機(jī)制[13]，牽引種群粒子離開局部范圍.具體方法如下：

1)構(gòu)建學(xué)習(xí)對象：為了在種群陷入局部最優(yōu)情況下使粒子迅速逃離局部最優(yōu)區(qū)域，需要構(gòu)建粒子的學(xué)習(xí)對象：粒子歷史最差位置和初始全局較差粒子位置.種群粒子在搜索過程中記錄歷史最差位置，在進(jìn)行反向?qū)W習(xí)時，每個粒子根據(jù)歷史最差位置進(jìn)行更新.種群在后期搜索過程中逐漸陷入局部最優(yōu)區(qū)域，構(gòu)造初始全局較差粒子，可以有效牽引種群移動.為增加種群反向?qū)W習(xí)的多樣性，在初始時構(gòu)造m個較差粒子，當(dāng)種群需要反向?qū)W習(xí)時，從這些m個較差粒子中隨機(jī)選出一個作為學(xué)習(xí)對象.

m個較差粒子應(yīng)該滿足以下兩個條件：第一，粒子應(yīng)有較差的適應(yīng)度值，可以保證粒子在種群陷入局部最優(yōu)時沿著運(yùn)動的反方向逃出局部最優(yōu)區(qū)域；第二，這些粒子應(yīng)均勻分布在搜索區(qū)域中，可以保證種群粒子反向?qū)W習(xí)的多樣性.使用歐氏距離來計算這些粒子兩兩間的距離，只有大于給定的閾值，才是理想的學(xué)習(xí)對象.選取的閾值計算公式(4)：

(4)

其中ximax和ximin分別為粒子第i維的取值上限和下限，即代表在候選服務(wù)集WSi中可選擇的服務(wù)個數(shù)，n為粒子搜索維度，代表組合服務(wù)中的子任務(wù)個數(shù).在初始種群時，選出達(dá)到要求的粒子不足m個，則再隨機(jī)生成新的粒子，檢測是否滿足要求，直至選出m個粒子.

2)反向?qū)W習(xí)：當(dāng)檢測到種群全局最優(yōu)位置在一定迭代次數(shù)內(nèi)未更新，則認(rèn)為整個種群陷入緩慢移動狀態(tài)，開始執(zhí)行反向?qū)W習(xí)策略.反向?qū)W習(xí)第i個粒子的速度更新公式為：

(5)

3.3 服務(wù)組合算法

針對服務(wù)組合問題，使用改進(jìn)的粒子群算法FWPSO來尋找最優(yōu)的組合服務(wù).我們先對種群粒子編碼處理，根據(jù)適應(yīng)度值函數(shù)對種群粒子選出的組合服務(wù)解決方案進(jìn)行評估，選出種群中最優(yōu)的服務(wù)組合方案.

3.3.1 粒子編碼

在進(jìn)行組合服務(wù)的選擇時將一個粒子看作一個組合服務(wù)的解決方案，尋找最優(yōu)組合服務(wù).分解的抽象子任務(wù)T=(T1，T2，…，Ti，…，Tn)代表粒子的各維搜索空間，n代表分解的抽象子任務(wù)個數(shù)，同時也表示粒子的搜索空間有n維.每個抽象子任務(wù)所對應(yīng)的候選服務(wù)集WSi中Web服務(wù)的個數(shù)設(shè)為m個，即表示粒子在這一維搜索空間中的最大向量長度.具體編碼模式如圖1所示：

圖1 組合服務(wù)的編碼Fig.1 Theencoding of composition service

粒子選出各維的向量值后就完成了Web服務(wù)組合解決方案的選擇.通過適應(yīng)度值評估函數(shù)對每個粒子所對應(yīng)的組合方案進(jìn)行評估，來尋找最優(yōu)解的服務(wù)組合方案.使用這種編碼方式，Web服務(wù)的組合選擇問題即可轉(zhuǎn)化為n元向量的求解問題，即尋找最優(yōu)向量(x1，x2，…，xi，…，xn)的過程.

3.3.2 適應(yīng)度函數(shù)設(shè)計

在Web組合服務(wù)的選取中，組合服務(wù)的整體QoS對服務(wù)評估有較大影響，根據(jù)組合服務(wù)中單個節(jié)點(diǎn)服務(wù)的QoS屬性值進(jìn)行聚合計算，得出整體組合服務(wù)的QoS指標(biāo).適應(yīng)度函數(shù)作為Web組合服務(wù)的評估函數(shù)，計算方法有多種，本文中適應(yīng)度值計算函數(shù)為：

(6)

3.3.3 算法描述

基于以上分析和設(shè)計，下面給出服務(wù)組合優(yōu)化算法描述.

Algorithm2：FWPSO

Input：N，m，Vmax，Vremax，Ltimes，N1，RLs，T

Output：Pgbest

Initialization N particles

Compute fitness

Generate the m worst particles

t=0

For i

Update position and speed

Compute fitness

If( activeness is slow)

Initlization the ith particle

End if

End for

Perform the explosion learning strategy

If(the standard of reserve learning )

While(j

For each i

Updateparticle

End for

For each N1

Update particle

End for

End while

End if

t=t+1

Generate the best particle

4 實(shí)驗設(shè)計與結(jié)果分析

4.1 實(shí)驗數(shù)據(jù)與環(huán)境

在本文中，我們將改進(jìn)的粒子群算法與IDPSO[10]、ZPSO[14]算法進(jìn)行對比，來驗證我們提出的改進(jìn)算法的優(yōu)化效率.實(shí)驗數(shù)據(jù)采用Zeng等的QWS公用有效數(shù)據(jù)集[15，16].在本文實(shí)驗中，我們分別測試了不同的子任務(wù)數(shù)，并將QWS數(shù)據(jù)集中的服務(wù)分別分配到這些子任務(wù)中，用來作為子任務(wù)的候選服務(wù)集.我們選擇數(shù)據(jù)集其中的4個屬性作為本文QoS評價指標(biāo)，即響應(yīng)時間(RT)，可用性(A)，吞吐量(T)，可靠性(Rel)，weight(RT，A，T，Rel)=(0.2，0.3，0.2，0.3) 為用戶偏好.實(shí)驗環(huán)境為Windows 7 OS，Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz，16GB RAM，64位操作系統(tǒng).

4.2 實(shí)驗參數(shù)設(shè)置

實(shí)驗具體參數(shù)設(shè)定如表1所示.本文中每組實(shí)驗均進(jìn)行50次，實(shí)驗最終結(jié)果為50次實(shí)驗的平均值.

表1 參數(shù)設(shè)置Table 1 Parameter setting

其中，反向?qū)W習(xí)閾值是指全局最優(yōu)粒子的位置的連續(xù)未變化的迭代次數(shù)，當(dāng)達(dá)到反向?qū)W習(xí)閾值時，種群粒子開始進(jìn)行反向?qū)W習(xí).在反向?qū)W習(xí)階段，整個種群中有N1個反向?qū)W習(xí)的粒子，速度不會超過最大反向?qū)W習(xí)速度；剩下的粒子仍然以正向速度進(jìn)行正向?qū)W習(xí)，速度會小于最大正向?qū)W習(xí)速度.在對粒子活躍度檢測時，若粒子的歷史最優(yōu)位置達(dá)到檢測閾值時，將此粒子廢棄，重新初始化新粒子.

4.3 可行性

為驗證本文提出的算法在Web服務(wù)組合選擇領(lǐng)域的可行性，在迭代次數(shù)為500次，每個子任務(wù)可選擇的候選服務(wù)數(shù)為100個，考察不同的子任務(wù)數(shù)下，三種算法尋找最優(yōu)解決方案的能力，具體的實(shí)驗結(jié)果如表2所示.

表2 適應(yīng)度值對比Table 2 Comparison results of fitness values

從表2中可以看出，在測試的不同的子任務(wù)數(shù)實(shí)驗中，F(xiàn)WPSO算法所找到的組合服務(wù)的適應(yīng)度值較優(yōu).

4.4 收斂性

本組實(shí)驗主要分析FWPSO算法應(yīng)用在Web服務(wù)組合選擇的收斂度問題上，在本組實(shí)驗中，我們將每個子任務(wù)對應(yīng)的候選服務(wù)集設(shè)置為100個服務(wù)，在不同的子任務(wù)數(shù)下分別進(jìn)行實(shí)驗，在每組實(shí)驗中，考察迭代次數(shù)對組合服務(wù)選擇的影響.實(shí)驗結(jié)果如圖2至圖5所示.

圖2 5個子任務(wù)數(shù)下,迭代次數(shù)對平均適應(yīng)度值的影響Fig.2 Influence of the iteration number on the average fitness of 5 subtasks圖3 10個子任務(wù)數(shù)下,迭代次數(shù)對平均適應(yīng)度值的影響Fig.3 Influence of the iteration number on the average fitness under10 subtasks圖4 15個子任務(wù)數(shù)下,迭代次數(shù)對平均適應(yīng)度值的影響Fig.4 Influence of the iteration number on the ave-rage fitness under 15 subtasks圖5 20個子任務(wù)數(shù)下,迭代次數(shù)對平均適應(yīng)度值的影響Fig.5 Influence of the iteration number on the average fitness under 20 subtasks

從圖中可以看出，在不同的子任務(wù)數(shù)下，各種算法所找到的平均最優(yōu)適應(yīng)度值隨著迭代次數(shù)的增加呈現(xiàn)不同的變化趨勢.IDPSO算法的收斂雖然也較快，但其最終收斂的適應(yīng)度值劣于FWPSO算法.相比之下，無論子任務(wù)數(shù)為多少，F(xiàn)WPSO算法的收斂速度較快.

5 結(jié) 論

本文研究了改進(jìn)的粒子群算法在Web服務(wù)組合優(yōu)化問題中的應(yīng)用，提出FWPSO算法，解決了傳統(tǒng)粒子群算法在服務(wù)組合優(yōu)化領(lǐng)域中的一些問題.在改進(jìn)的FWPSO算法中，我們通過粒子活躍度檢測機(jī)制，剔除不活躍粒子，增加種群粒子的多樣性，引入煙花算法中煙花爆炸搜索的理論，改進(jìn)了粒子的學(xué)習(xí)策略，增強(qiáng)種群的搜索能力，使用粒子的反向?qū)W習(xí)，有效解決了種群陷入局部最優(yōu)問題.在仿真實(shí)驗中，我們對改進(jìn)的算法的可行性、收斂性等方面進(jìn)行了研究，實(shí)驗結(jié)果表明，本文提出的改進(jìn)粒子群算法FWPSO在Web服務(wù)組合優(yōu)化問題上的綜合性能更高，在下一步工作中，我們將研究服務(wù)組合優(yōu)化領(lǐng)域中，服務(wù)組合關(guān)聯(lián)度對服務(wù)選擇問題的影響.

：

[1] Yao Y，Cao J，Jiang Y，et al.An optimal engine component placement strategy for cloud workflow service[C].IEEE International Conference on Web Services，2016：380-387.

[2] Xu X，Sheng Q Z，Zhang L J，et al.From big data to big service[J].IEEE Computer，2015，48(7)：80-83.

[3] Klai K，Ochi H.Model checking of composite cloud services[C].IEEE International Conference on Web Services，2016：356-363.

[4] Barakat L，Miles S，Poernomo I，et al.Efficient multi-granularity service composition[C].IEEE International Conference on Web Services，2011：227-234.

[5] Huo Y，Zhuang Y，Gu J，et al.Discrete gbest-guided artificial bee colony algorithm for cloud service composition[J].Applied Intelligence，2015，42(4)：661-678.

[6] Jin H，Yao X，Chen Y.Correlation-aware QoS modeling and manufacturing cloud service composition[J].Journal of Intelligent Manufacturing，2015：1-14.

[7] Wen Tao，Sheng Guo-jun，Guo Quan，et al.Web service composition based on modified particle swarm optimization[J].Chinese Journal of Computers，2013，36(5)：1031-1046.

[8] Chen Y，Huang J，Lin C.Partial selection：an efficient approach for QoS-aware web service composition[C].IEEE International Conference on Web Services，2014：1-8.

[9] Liao J，Liu Y，Zhu X，et al.Accurate sub-swarms particle swarm optimization algorithm for service composition[J].Journal of Systems and Software，2014，90(1)：191-203.

[10] Zhang Y，Jing Z，Zhang Y.MR-IDPSO：a novel algorithm for large-scale dynamic service composition[J].Tsinghua Science and Technology，2015，20(6)：602-612.

[11] Eberhart R，Kennedy J.A new optimizer using particle swarm theory[C].Proceedings of the Sixth International Symposiumon Micro Machine and Human Science，1995：39-43.

[12] Tan Y,Zhu Y.Fireworks algorithm for optimization[C].International Conference in Swarm Intelligence,Springer，Berlin,Heidelberg,2010:355-364.

[13] Xia X，Liu J，Li Y.Particle swarm optimization algorithm with reverse-learning and local-learning behavior[J].Journal of Software，2014，9(2)：350-357.

[14] Zhang T.QoS-aware Web service selection based on particle swarm optimization[J].Journal of Networks，2014，9(3)：565-570.

[15] Zeng L，Benatallah B，Dumas M，et al.Quality driven web services composition[C].Proceedings of the 12th International Conference on World Wide Web，2003：411-421.

[16] Zeng L，Benatallah B，Ngu A H H，et al.Qos-aware middleware for web services composition[J].IEEE Transactions on Software Engineering，2004，30(5)：311-327.

[17] Seghir F，Khababa A.A hybrid approach using genetic and fruit fly optimization algorithms for QoS-aware cloud service composition[J].Journal of Intelligent Manufacturing，2017：1-20.

附中文參考文獻(xiàn)：

[7] 溫 濤，盛國軍，郭 權(quán)，等.基于改進(jìn)粒子群算法的Web服務(wù)組合[J].計算機(jī)學(xué)報，2013，36(5)：1031-1046.