,,,

(1.合肥工業(yè)大學(xué) a.管理學(xué)院;b.過(guò)程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn),合肥 230009; 2.北京航空航天大學(xué) 自動(dòng)化科學(xué)與電氣工程學(xué)院,北京 100191)

0 概述

Web服務(wù)作為一種新型的分布式計(jì)算模型,已經(jīng)成為面向服務(wù)架構(gòu)(Service Oriented Architecture,SOA)和云計(jì)算軟件即服務(wù)(Software as a Service,SaaS)的主要技術(shù)之一[1]。隨著Web服務(wù)技術(shù)的日益成熟和服務(wù)的不斷加入,出現(xiàn)了大量在網(wǎng)絡(luò)上穩(wěn)定易用且功能相對(duì)單一的Web服務(wù),但是單個(gè)Web服務(wù)能夠提供的功能有限,難以快速地滿(mǎn)足用戶(hù)復(fù)雜和多變的需求[2]。將現(xiàn)有的多個(gè)小粒度Web服務(wù)組合成一條增值的大粒度服務(wù)鏈來(lái)滿(mǎn)足用戶(hù)需求成為必然趨勢(shì)[3]。因此,服務(wù)組合技術(shù)已成為云計(jì)算按需服務(wù)的關(guān)鍵技術(shù)和研究熱點(diǎn)。

目前,基于服務(wù)質(zhì)量(Quality of Service,QoS)的Web服務(wù)動(dòng)態(tài)選擇方法主要有兩種,一種是基于QoS的局部?jī)?yōu)化原則,另一種是基于QoS的全局最優(yōu)原則。基于QoS局部最優(yōu)的Web服務(wù)選擇是在每個(gè)服務(wù)類(lèi)候選集中通過(guò)加權(quán)和排序選擇局部最優(yōu)的服務(wù),但是不能保證組合服務(wù)整體最優(yōu)[4];將基于QoS全局最優(yōu)的服務(wù)動(dòng)態(tài)選擇問(wèn)題轉(zhuǎn)化為一個(gè)帶QoS約束的多目標(biāo)服務(wù)組合優(yōu)化問(wèn)題,目前有遺傳算法、粒子群、整數(shù)規(guī)劃[5-7]等方法求解全局最優(yōu)組合問(wèn)題,但是存在收斂速度慢、易陷入局部最優(yōu)問(wèn)題。而對(duì)于云環(huán)境下的大規(guī)模服務(wù),搜索空間膨脹,造成組合效率低下的問(wèn)題,云計(jì)算技術(shù)則提供了很好的支持,如云計(jì)算環(huán)境下的并行蟻群算法[8]、并行粒子群算法[9]等,將智能算法進(jìn)行并行化,可高效、快速地解決海量數(shù)據(jù)的問(wèn)題。

螢火蟲(chóng)群優(yōu)化(Glowworm Swarm Optimization,GSO)算法是一種群智能優(yōu)化算法[10]。該算法已應(yīng)用于連續(xù)型和離散型論域優(yōu)化,如多模態(tài)函數(shù)優(yōu)化問(wèn)題[11]、旅行商問(wèn)題[12]、屬性選擇問(wèn)題[13]、聚類(lèi)[14]等多個(gè)領(lǐng)域。服務(wù)動(dòng)態(tài)選擇的實(shí)質(zhì)是多條件多目標(biāo)下的離散組合優(yōu)化問(wèn)題,但是在云計(jì)算環(huán)境下離散螢火蟲(chóng)群優(yōu)化算法的研究甚少。本文研究在云計(jì)算環(huán)境下的離散螢火蟲(chóng)群優(yōu)化算法的并行實(shí)現(xiàn)方法,提出基于MapReduce的并行離散螢火蟲(chóng)群優(yōu)化算法(MRDGSO)。該算法融合分群分治思想,定義MRDGSO的Map過(guò)程和Reduce過(guò)程,加快收斂速度和避免陷入局部最優(yōu),并且針對(duì)Web服務(wù)選擇問(wèn)題,重新定義個(gè)體的編碼、計(jì)算個(gè)體間的距離,改進(jìn)位置更新、非可行解處理以及相關(guān)參數(shù)。

1 問(wèn)題定義和描述

1.1 Web服務(wù)定義

對(duì)面向SaaS平臺(tái)的大量功能相同而非功能屬性不同的Web服務(wù)給出相關(guān)定義如下。

具體服務(wù)(Concrete Service,CS):由服務(wù)提供者在統(tǒng)一描述、發(fā)現(xiàn)和集成(Universal Description Discovery and Integration,UDDI)注冊(cè)中心中注冊(cè)的可執(zhí)行的Web服務(wù)[15],記為:CS={D,F,Q}。其中,D表示服務(wù)的信息屬性集合,F表示服務(wù)的功能屬性集合,Q表示服務(wù)的質(zhì)量屬性集合。

抽象服務(wù)(Abstract Service,AS):僅描述服務(wù)的功能和接口信息,對(duì)應(yīng)于某個(gè)服務(wù)候選集,是構(gòu)成一條服務(wù)鏈的基本邏輯單元。一個(gè)AS包含多個(gè)CS,且這些CS由不同服務(wù)提供者提供,具有不同的QoS值,記為AS={CS1,CS2,…,CSh}。

服務(wù)組合(Service Composition,SC):為每個(gè)抽象服務(wù)AS從其包含的具體服務(wù)中根據(jù)QoS選定出具體服務(wù),所形成的可執(zhí)行具體服務(wù)鏈,記為SC={AS1,AS2,…,ASm},表示每一個(gè)服務(wù)組合SC由m個(gè)AS組成,而每一個(gè)AS由k個(gè)功能相同的候選CS組成,每一個(gè)CS有nq個(gè)QoS屬性{QoSn1,QoSn2,…,QoSnq}。

服務(wù)質(zhì)量(QoS):是Web服務(wù)的一組非功能特性,包括響應(yīng)時(shí)間、吞吐量、可靠性、可用性、安全性、真實(shí)度等。本文主要考慮Web服務(wù)的5種QoS屬性,分別為執(zhí)行時(shí)間T、執(zhí)行費(fèi)用C、信譽(yù)度Rep、可靠性Rel和可用性Ava。這也是目前較常用和具有代表性的QoS屬性。

1.2 基于QoS服務(wù)選擇問(wèn)題描述

QoS全局最優(yōu)Web服務(wù)選擇就是在Web服務(wù)組合中,對(duì)各個(gè)抽象服務(wù)相對(duì)應(yīng)的候選服務(wù)集中分別選擇出一個(gè)具體服務(wù),形成一條可執(zhí)行的服務(wù)鏈,使得服務(wù)鏈滿(mǎn)足QoS約束的前提下,整體的QoS達(dá)到最優(yōu)[16]。將服務(wù)組合中基于QoS的服務(wù)選擇問(wèn)題定義如下模型,如圖1所示。

圖1 服務(wù)組合

服務(wù)組合(SC)由AS1,AS2,…,ASm,m個(gè)抽象服務(wù)組成,而每個(gè)AS由h個(gè)候選功能相同而非功能屬性不同的CS組成,表示為ASm={CSm1,CSm2,…,CSmh},每一個(gè)CS有nq個(gè)服務(wù)質(zhì)量屬性QoSn1,QoSn2,…,QoSnq,那么SC={CS1j,CS2j,…,CSmj}(j=1,2,…,h)表示滿(mǎn)足用戶(hù)需求的其中一個(gè)服務(wù)組合。服務(wù)組合就是在每一個(gè)抽象服務(wù)中選出一個(gè)具體服務(wù),并且滿(mǎn)足整體QoS屬性達(dá)到最優(yōu)。對(duì)應(yīng)于上述服務(wù)組合圖,QoS全局最優(yōu)Web服務(wù)選擇問(wèn)題可轉(zhuǎn)化為一個(gè)求從S到D的帶QoS約束條件下的多目標(biāo)最優(yōu)路徑問(wèn)題,則一個(gè)帶QoS約束的多目標(biāo)服務(wù)組合優(yōu)化模型形式化描述可表示如下:

(1)

其中,T(sc)為服務(wù)組合執(zhí)行花費(fèi)的總時(shí)間,C(sc)為服務(wù)組合執(zhí)行花費(fèi)的總成本,T(sc)和C(sc)作為2個(gè)性能評(píng)價(jià)準(zhǔn)則,Rep(sc)表示為服務(wù)組合執(zhí)行的信譽(yù)度,Rel(sc)表示為服務(wù)組合執(zhí)行的可靠性,Ava(sc)表示為服務(wù)組合執(zhí)行的可用性,Rep(sc)、Rel(sc)和Ava(sc)作為3個(gè)約束條件。

2 基本的螢火蟲(chóng)群優(yōu)化算法

GSO通過(guò)模擬自然界螢火蟲(chóng)求偶或覓食行為,聚集在一個(gè)或多個(gè)點(diǎn),該點(diǎn)即為最優(yōu)解。GSO算法主要包含4個(gè)階段,即螢火蟲(chóng)初始化、螢光素更新、位置更新和決策半徑更新[17]。算法流程如下:

步驟1初始化。在可行域中隨機(jī)生成n個(gè)螢火蟲(chóng),初始化每個(gè)螢火蟲(chóng)的螢光素l0、動(dòng)態(tài)決策域r0、感知域rs、移動(dòng)步長(zhǎng)S、鄰域閾值nt、螢光素消失率ρ、螢光素更新率γ、動(dòng)態(tài)決策域更新率β、最大迭代次數(shù)Tmax。

步驟2螢光素更新。對(duì)于極小值問(wèn)題按式(2)進(jìn)行更新:

li(t)=(1-ρ)li(t-1)+γ1/f(xi(t))

(2)

其中,f(xi(t))表示螢火蟲(chóng)i在t時(shí)刻所在位置的目標(biāo)函數(shù)值,li(t)表示螢火蟲(chóng)i在t時(shí)刻的螢光素值。

Ni(t)={j:‖xj(t)-xi(t)‖

(3)

(4)

(5)

步驟4按式(6)更新決策半徑:

β(nt-|Ni(t)|)))

(6)

其中,|Ni(t)|為鄰域集內(nèi)的螢火蟲(chóng)數(shù)量。

3 求解服務(wù)選擇問(wèn)題的MRDGSO算法

3.1 MRDGSO并行化設(shè)計(jì)

MRDGSO運(yùn)用云計(jì)算的MapReduce編程模式[18]將離散螢火蟲(chóng)群優(yōu)化算法并行化,設(shè)計(jì)出離散螢火蟲(chóng)群優(yōu)化算法、Map函數(shù)和Reduce函數(shù),并針對(duì)服務(wù)組合優(yōu)化問(wèn)題,重新定義了個(gè)體的編碼、距離計(jì)算、目標(biāo)函數(shù)、改進(jìn)位置移動(dòng)方式。借鑒分群分治的思想,融入到MRDGSO算法中,實(shí)現(xiàn)云環(huán)境下小規(guī)模多種群[19]并行計(jì)算,改善算法搜索速度慢和易于陷入局部最優(yōu)的缺點(diǎn),提高求解效率和對(duì)海量數(shù)據(jù)的處理能力。MRDGSO融合分群分治思想的執(zhí)行過(guò)程如圖2所示。

圖2 MRDGSO執(zhí)行過(guò)程

文獻(xiàn)[20]針對(duì)多模態(tài)函數(shù)提出了基于MapReduce的螢火蟲(chóng)群優(yōu)化算法,改善了搜索計(jì)算耗時(shí)和大規(guī)模問(wèn)題求解效率低的缺點(diǎn)。本文進(jìn)一步優(yōu)化,將分群分治思想融入到改進(jìn)的DGSO算法中,具有快速和高效地求解高維海量數(shù)據(jù)的能力。

MRDGSO主要分為4個(gè)階段,即初始化階段、分群搜索階段、優(yōu)良解保留階段和合并搜索階段。

步驟1在初始化階段創(chuàng)建一個(gè)初始的螢火蟲(chóng)群,在給定的搜索空間內(nèi)采用空間分割法[21]隨機(jī)生成m維的初始位置Xi,并對(duì)目標(biāo)函數(shù)J、螢光素L0和決策半徑Rd0進(jìn)行初始化,最后將所有螢火蟲(chóng)平均分配在不同的種群中,以螢火蟲(chóng)位置信息、目標(biāo)函數(shù)信息、螢光素信息、決策半徑信息和種群信息組成的螢火蟲(chóng)結(jié)構(gòu)體形式進(jìn)行存儲(chǔ),螢火蟲(chóng)結(jié)構(gòu)體形式如圖3所示。其中,K表示螢火蟲(chóng)群的種群編號(hào),i表示螢火蟲(chóng)編號(hào)。最后在給定的Web服務(wù)集合中計(jì)算出理想點(diǎn)T*、C*。

圖3螢火蟲(chóng)結(jié)構(gòu)體

步驟2在分群搜索階段應(yīng)用Map函數(shù)分別對(duì)不同的種群用DGSO算法獨(dú)立搜索,并行螢火蟲(chóng)算法中最耗時(shí)的部分——螢火蟲(chóng)之間的距離計(jì)算和鄰域搜索,應(yīng)用Reduce函數(shù)來(lái)更新螢火蟲(chóng)的螢光素、目標(biāo)函數(shù),并保存種群內(nèi)的最優(yōu)解,最后將更新后的螢火蟲(chóng)以結(jié)構(gòu)體形式作為輸出結(jié)果,作為下一代Map函數(shù)的輸入,反復(fù)循環(huán)迭代,直至所有種群收斂或滿(mǎn)足閾值。

步驟3在優(yōu)良解保留階段保留K個(gè)種群的優(yōu)良解。在合并整個(gè)可行域的解時(shí),通過(guò)控制算法的感知域Rs來(lái)控制螢火蟲(chóng)的飛行范圍,從而實(shí)現(xiàn)在不同種群之間的信息共享。

步驟4在合并搜索階段將保留下來(lái)的優(yōu)良解作為新的螢火蟲(chóng)群初始位置,應(yīng)用MapReduce計(jì)算模型搜索全局最優(yōu)解,直至種群收斂或滿(mǎn)足閾值。

3.2 離散螢火蟲(chóng)群優(yōu)化求解方法

文獻(xiàn)[12]中的離散螢火蟲(chóng)群優(yōu)化算法在求解離散組合優(yōu)化問(wèn)題時(shí),簡(jiǎn)單、易實(shí)現(xiàn)而且魯棒性強(qiáng)。應(yīng)用DGSO解決服務(wù)組合問(wèn)題的關(guān)鍵是解向量構(gòu)造和初始化、螢火蟲(chóng)個(gè)體間距離計(jì)算、目標(biāo)函數(shù)構(gòu)造、螢火蟲(chóng)個(gè)體位置更新和非可行解處理。

1)解向量構(gòu)造和初始化。本文基于符號(hào)的編碼,將每只螢火蟲(chóng)的序列編碼看作一個(gè)組合服務(wù),序列編碼中的每個(gè)元素對(duì)應(yīng)于服務(wù)候選集中的一個(gè)具體服務(wù)編號(hào),其解向量編碼表示為:Xi=(Xi1,Xi2,…,Xik),Xik∈[1,Hk]。其中,Xi表示第i只螢火蟲(chóng),不同的螢火蟲(chóng)表示不同的服務(wù)組合,Xik表示第i只螢火蟲(chóng)在第k個(gè)服務(wù)類(lèi)下的具體服務(wù)編號(hào),取值為區(qū)間[1,Hk]上的整數(shù)。在MapReduce模式下的螢火蟲(chóng)結(jié)構(gòu)體為:Gi=(Xi,J(Xi),Li,Rdi,Ki),其信息包含基本的螢火蟲(chóng)位置Xi、目標(biāo)函數(shù)J(Xi)、螢光素Li、決策半徑Rdi和種群編號(hào)Ki。初始解采用文獻(xiàn)[21]中的區(qū)間分割法生成,在解空間上均勻分布,保證隨機(jī)產(chǎn)生的各個(gè)解向量具有差別性并且滿(mǎn)足QoS多約束條件,以避免陷入局部最優(yōu),增強(qiáng)了全局搜索的能力。

2)個(gè)體間距離計(jì)算公式。螢火蟲(chóng)個(gè)體間的距離由維度間距離和維度內(nèi)距離兩部分組成,由維度間距離引導(dǎo)維度內(nèi)距離,使得相同的維度數(shù)量越多,距離越小,其次在相同的維度數(shù)量情況下,維度內(nèi)距離越小,則距離越小。設(shè)個(gè)體i、j在第t次迭代的位置編碼分別為序列xi(t)=(xi1,xi2,…,xik)和xj(t)=(xj1,xj2,…,xjk),則個(gè)體i、j在第t次迭代的距離計(jì)算公式定義為:

(7)

(8)

(9)

其中,dij(t,k)表示xj(t,k)-xi(t,k),1/m是維度引導(dǎo)系數(shù),Hk是第k維度上的取值上限,也指在服務(wù)組合上第k個(gè)抽象服務(wù)的候選服務(wù)數(shù)量,C為常數(shù),表示距離系數(shù)。由式(9)可知dij(t)∈[0,C],個(gè)體i、j之間的距離滿(mǎn)足對(duì)稱(chēng)性,即dij=dji。參數(shù)C取值太大或者太小都不利于鄰域集更新。

3)目標(biāo)函數(shù)構(gòu)造。本文將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題來(lái)求解全局QoS最優(yōu),求得的最優(yōu)解作為多目標(biāo)的最優(yōu)解,采用TOPSIS法構(gòu)造目標(biāo)函數(shù)。

(10)

其中,f+(k)表示為第k個(gè)抽象服務(wù)的QoS理想解。

對(duì)于約束條件下的單目標(biāo)求最小化問(wèn)題則表示為:

f+=min{f(m)|R(m)≥R0,k∈[1,m]}

對(duì)于約束條件下的單目標(biāo)求最大化問(wèn)題則表示為:

f+=max{f(m)|R(m)≥R0,k∈[1,m]}

4)螢火蟲(chóng)個(gè)體位置更新。對(duì)于求解離散組合優(yōu)化問(wèn)題,DGSO算法是在各維上相同位置則保持不變,不同位置則以一定的概率選擇更新公式進(jìn)行更新,從而實(shí)現(xiàn)整個(gè)位置的更新。具體更新公式如下:

xik(t+1)

(11)

5)非可行解處理。在每次迭代過(guò)程中,某些解向量有可能不滿(mǎn)足于約束條件或者偏離可行解域,成為非可行解。在進(jìn)入下一次迭代之前,丟棄本次迭代中所有非可行解,采用上述區(qū)間分割法隨機(jī)產(chǎn)生可行解替換非可行解,并且重新初始化其決策半徑,從而提高搜索效率和保持種群多樣性。

3.3 Map函數(shù)設(shè)計(jì)

Map函數(shù)的任務(wù)是分別對(duì)k個(gè)種群內(nèi)的個(gè)體螢火蟲(chóng)i在其各自的種群內(nèi)獨(dú)自搜索,將螢火蟲(chóng)最耗時(shí)的鄰域搜索和位置更新并行化,得到新位置的個(gè)體螢火蟲(chóng)i,同時(shí)更新移動(dòng)后的決策半徑。Map函數(shù)輸出的鍵值對(duì)形式為<種群編號(hào),螢火蟲(chóng)結(jié)構(gòu)體>。Map函數(shù)描述如下。

函數(shù)1MRDGSO的Map函數(shù)

Function Map(Key,value)

1.Ki←key,Ni←?

2.Xi,J(Xi),Li,Rdi,Ki←getInfo(value)

3.Temp←getTempSwarm(distributedCache)

//HDFS Distributed Cache

4.for each j∈Temp do

5.Xj,J(Xj),Lj,Rdj,Kj←getInfo(Temp)

6.dij←getDistance(Xi, Xj)// using Equation (9)

7. if (dij< Rdiand Li< Ljand Ki= Kj) then

Ni←Ni∪j // using Equation (3)

8.end for

9.if (|Ni|>0) then

10. for each j∈Nido

11. Pij←getProbability(Li,Lj)

12. end for

13.end if

14.Xi←getBestNeighbor(Pij)

15.Xnew←getNewX(Xi,Xj)//using Equation (11)

16.Rdnew←getNewRd(Rdi,| Ni|)

// using Equation (6)

17.Glowwormnew←setInfo(Xnew, J(Xi), Li, Rdnew)

18.Emit(Ki, Glowwormnew)

End

3.4 Reduce函數(shù)設(shè)計(jì)

Reduce函數(shù)的任務(wù)是對(duì)Map產(chǎn)生的新位置的螢火蟲(chóng)i更新螢光素,并根據(jù)QoS屬性值利用理想點(diǎn)法更新螢火蟲(chóng)的目標(biāo)函數(shù)值,選出當(dāng)前種群內(nèi)最優(yōu)的服務(wù)組合,保存當(dāng)前種群內(nèi)螢火蟲(chóng)的最優(yōu)解。Reduce函數(shù)輸出的鍵值對(duì)形式為<種群編號(hào),新螢火蟲(chóng)結(jié)構(gòu)體> 。Reduce函數(shù)描述如下。

函數(shù)2MRDGSO的Reduce函數(shù)

Function Reduce(key,valueList)

1.K←key;Glowwormbest←? ;

2.for each j∈valueList

3. Xj,J(Xj),Lj,Rdj,Kj←getInfo(valueList)

4. Jnew(Xj)←getNewJ(Xj)//using Equation (10)

5. Lnew←getNewL(Lj, Jnew(Xj))

//using Equation (2)

6. Glowwormnew←setInfo(Xj, Jnew(Xj), Lnew, Rdj)

7. Emit(K, Glowwormnew)

8.end for

End

3.5 時(shí)間復(fù)雜度分析

設(shè)螢火蟲(chóng)總數(shù)目為n,種群數(shù)為k,有效迭代次數(shù)為T(mén)iter,Web服務(wù)總規(guī)模為N,抽象服務(wù)的屬性個(gè)數(shù)為m。則算法時(shí)間復(fù)雜度分析如下:

1)第1階段初始化解的過(guò)程時(shí)間復(fù)雜度為O(n+N)。

2)一次迭代中,第2階段Map函數(shù)的總時(shí)間復(fù)雜度為O(mn2/k)。

3)一次迭代中,第2階段Reduce函數(shù)的總時(shí)間復(fù)雜度為O(n)。

4)第3階段保留種群優(yōu)良解過(guò)程的總時(shí)間復(fù)雜度為O(n2/k)。

5)一次迭代中,第4階段Map函數(shù)的總時(shí)間復(fù)雜度為O(mk2)。

6)一次迭代中,第4階段Reduce函數(shù)的總時(shí)間復(fù)雜度為O(k)。

故迭代Titer次的算法時(shí)間復(fù)雜度為:

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)硬件環(huán)境:Inter Core i5處理器;內(nèi)存為4 GB;64位Linux操作系統(tǒng);3臺(tái)VMware。實(shí)驗(yàn)所需的軟件包括Centos 6.5、Hadoop-0.20.0、JDK1.7.0、Eclipse4.5。將其中1臺(tái)主機(jī)節(jié)點(diǎn)作為master,其他2臺(tái)主機(jī)節(jié)點(diǎn)作為slave,搭建hadoop集群。根據(jù)文獻(xiàn)[12]中建議的參數(shù),并結(jié)合本文多次實(shí)驗(yàn),將MRDGSO參數(shù)設(shè)置選定如表1所示。

表1 DGSO參數(shù)設(shè)置

此外,式(8)、式(10)分別取值為C=20,p1=0.05,p2=0.95。

本文的實(shí)驗(yàn)測(cè)試數(shù)據(jù)參照文獻(xiàn)[8]中隨機(jī)方式生成各具體服務(wù)CS的QoS值,QoS的取值范圍為:0

表2 各組不同規(guī)模的測(cè)試數(shù)據(jù)

4.2 結(jié)果分析

4.2.1 可行性和有效性分析

為了驗(yàn)證本文算法的可行性和有效性,引入了文獻(xiàn)[2]中的基于粒子群進(jìn)化的服務(wù)選擇算法(PSO-GODSS)、文獻(xiàn)[20]中的MRGSO算法和傳統(tǒng)的DGSO進(jìn)行比較。圖4給出了PSO-GODSS、MRGSO、DGSO、MRDGSO在基于上文所述的QoS評(píng)價(jià)指標(biāo)上的實(shí)驗(yàn)結(jié)果,并且采用G1組規(guī)模下對(duì)算法性能進(jìn)行測(cè)試,發(fā)現(xiàn)在該G1組規(guī)模下迭代第30次之前,MRDGSO、MRGSO和DGSO算法前期收斂速度略快于PSO-GODSS,而迭代第45次時(shí)DGSO算法陷入局部最優(yōu),迭代第84次時(shí)MRGSO算法陷入局部最優(yōu),迭代第100次時(shí)PSO-GODSS算法陷入局部最優(yōu),MRDGSO算法在第315次達(dá)到全局最優(yōu)解,其全局搜索能力略?xún)?yōu)于其他算法。圖5給出了上述算法在G2組規(guī)模下對(duì)算法性能的測(cè)試結(jié)果,發(fā)現(xiàn)在較大規(guī)模服務(wù)下MRDGSO算法的收斂速度和全局搜索能力明顯優(yōu)于DGSO和PSO-GODSS算法,而在全局搜索能力上優(yōu)于MRGSO算法。

圖4 在G1組下的全局最優(yōu)收斂過(guò)程

圖5 在G2組下全局最優(yōu)收斂過(guò)程

表3給出了MRPSO、DGSO、MRDGSO、MRGSO算法分別在不同規(guī)模下求得的全局最優(yōu)解及其所消耗的時(shí)間結(jié)果,其中MRPSO是上述PSO-GODSS在MapReduce框架下實(shí)現(xiàn)的并行化,可以看出MRDGSO的全局搜索能力表現(xiàn)優(yōu)秀,始終優(yōu)于DGSO和MPRPSO。而在G1、G2和G3數(shù)據(jù),并行化的MRDGSO、MRGSO和MRPSO運(yùn)行時(shí)間比非并行的DGSO慢,而在大規(guī)模服務(wù)G4和G5下并行算法明顯比非并行的快。圖6展示了4種算法在不同服務(wù)規(guī)模下的運(yùn)行時(shí)間走勢(shì)情況,從而體現(xiàn)了MRDGSO并行算法求解大規(guī)模問(wèn)題的優(yōu)勢(shì),也進(jìn)一步從執(zhí)行效率上證明了MRDGSO算法的可行性和有效性。

表3 4種算法在不同服務(wù)規(guī)模下的全局最優(yōu)解及其計(jì)算代價(jià)

圖6 3種算法在不同服務(wù)規(guī)模下的運(yùn)行時(shí)間

綜合上述實(shí)驗(yàn)表明,本文提出的MRDGSO算法在求解服務(wù)選擇問(wèn)題上具有可行性和有效性,且其求解全局QoS最優(yōu)在解的質(zhì)量上和算法性能上均比PSO-GODSS、MRPSO、DGSO算法有顯著提升。

4.2.2 MRDGSO的擴(kuò)展性及性能分析

圖7給出了抽象服務(wù)AS數(shù)量m分別為20、40、60、80、100,候選服務(wù)數(shù)H從100增加到500,并以100為步長(zhǎng),統(tǒng)計(jì)出MRDGSO算法進(jìn)行服務(wù)選擇執(zhí)行20次的平均計(jì)算時(shí)間開(kāi)銷(xiāo)。實(shí)驗(yàn)結(jié)果表明,候選服務(wù)數(shù)量的變化對(duì)算法時(shí)間沒(méi)有明顯的影響,而抽象服務(wù)規(guī)模越大,算法運(yùn)行時(shí)間越長(zhǎng)。圖8給出了候選服務(wù)數(shù)H固定為100,服務(wù)數(shù)量N從2 000增加到10 000,即抽象服務(wù)AS數(shù)量以步長(zhǎng)20從20增加到100,統(tǒng)計(jì)出MRDGSO算法進(jìn)行服務(wù)選擇執(zhí)行20次的平均計(jì)算時(shí)間開(kāi)銷(xiāo)。實(shí)驗(yàn)結(jié)果表明,服務(wù)數(shù)量的增加或者抽象服務(wù)AS數(shù)量的增加,算法運(yùn)行時(shí)間呈現(xiàn)增長(zhǎng)的趨勢(shì)。說(shuō)明該算法有良好的擴(kuò)展性,而且能夠應(yīng)對(duì)大規(guī)模服務(wù)集合的組合問(wèn)題。

圖7 候選服務(wù)數(shù)量對(duì)本文算法性能的影響

圖8 服務(wù)數(shù)量對(duì)本文算法性能的影響

在云計(jì)算平臺(tái)Hadoop下,MRDGSO實(shí)現(xiàn)并行化的實(shí)際時(shí)間開(kāi)銷(xiāo)除了平臺(tái)自身消耗以外,還跟所選取的mapper數(shù)量有關(guān)。設(shè)定每個(gè)節(jié)點(diǎn)最多可運(yùn)行10個(gè)mapper,那么整個(gè)map的容量是10×3(節(jié)點(diǎn))=30個(gè)。圖9給出了在給定10 000個(gè)變量的總規(guī)模下,隨著mapper數(shù)量的增加所消耗的時(shí)間逐漸減小,而超過(guò)30個(gè)mapper時(shí),由于資源缺乏而無(wú)法容納更多的mapper,每次迭代所耗費(fèi)的時(shí)間會(huì)增加。

圖9 在恒定規(guī)模問(wèn)題下本文算法的可擴(kuò)展性

圖10給出了在每個(gè)mapper設(shè)置為150個(gè)變量下,開(kāi)始隨著mapper數(shù)量的增加逐漸上升,然后隨著mapper數(shù)量的增加不會(huì)改變迭代時(shí)間。在mapper數(shù)量達(dá)到30個(gè)后,map的容量飽和導(dǎo)致迭代時(shí)間略有增加。

圖10 在恒定負(fù)載下本文算法的可擴(kuò)展性

綜合上述實(shí)驗(yàn),表明本文提出的MRDGSO并行化算法有良好的可擴(kuò)展性,克服了離散螢火蟲(chóng)群優(yōu)化算法解決服務(wù)選擇問(wèn)題計(jì)算效率低的困難,而且能夠處理大規(guī)模問(wèn)題。但也存在以下不足:1)用Map函數(shù)并行計(jì)算螢火蟲(chóng)鄰域集在計(jì)算耗時(shí)問(wèn)題上可進(jìn)一步優(yōu)化;2)Reduce函數(shù)并不適應(yīng)計(jì)算所有問(wèn)題的評(píng)價(jià)函數(shù);3)由于MapReduce模型的一些限制,并未表現(xiàn)出其線性擴(kuò)展性。

4.2.3 參數(shù)分析

圖11給出了參數(shù)n和k對(duì)MRDGSO算法的影響結(jié)果,展示了在G1組規(guī)模和螢火蟲(chóng)總數(shù)n分別為500、1 000和1 500的種群規(guī)模下,MRDGSO分成種群k與n之間的關(guān)系。從圖中可以看出,在一定的螢火蟲(chóng)群體規(guī)模下,隨著分成種群k數(shù)量的不斷增加,全局最優(yōu)搜索能力先是逐漸增強(qiáng),當(dāng)k達(dá)到一定值后又逐漸降低;當(dāng)n=500時(shí),k在[15,30]范圍內(nèi)全局搜索能力最強(qiáng),當(dāng)n=1 000時(shí),k在[35,50]范圍內(nèi)全局搜索能力最強(qiáng),當(dāng)n=1 500時(shí),k在[60,80]范圍內(nèi)全局搜索能力最強(qiáng);滿(mǎn)足n/k∈[15,30]時(shí),即每個(gè)種群的螢火蟲(chóng)數(shù)量控制在[15,30]范圍內(nèi),全局搜索能力最強(qiáng)。

圖11 n和k對(duì)本文算法性能的影響

MRDGSO算法在求解服務(wù)選擇離散組合問(wèn)題的關(guān)鍵在于p1和p2參數(shù)的取值,直接影響算法的收斂速度和全局搜索能力。圖12給出了參數(shù)p1和p2對(duì)MRDGSO算法的影響結(jié)果,展示了在G1服務(wù)規(guī)模下,不同的p1和p2取值對(duì)算法性能的影響。從圖中可以說(shuō)明不同的參數(shù)p1和p2取值影響算法的收斂速度和全局搜索能力。當(dāng)p1和p2取值為(0.05,0.95)時(shí),MRDGSO收斂速度最快,全局搜索能力最強(qiáng);當(dāng)p1和p2取值為(0.15,0.85)時(shí),MRDGSO收斂速度最慢,全局搜索能力最差;當(dāng)p1和p2取值為(0.02,0.98)和(0.10,0.90)時(shí),MRDGSO收斂速度較慢,全局搜索能力還未達(dá)到最強(qiáng)。

圖12 參數(shù)p1和p2對(duì)本文算法性能的影響

由式(9)中可知,2個(gè)螢火蟲(chóng)個(gè)體之間的距離dij(t)∈[0,C],引入距離系數(shù)C,且設(shè)置為20,使得所有的螢火蟲(chóng)個(gè)體之間的距離在[0,20]范圍內(nèi),而其感知半徑和決策半徑的大小直接引導(dǎo)著螢火蟲(chóng)的搜索方向和最優(yōu)解的質(zhì)量。圖13給出了在G1服務(wù)規(guī)模下參數(shù)Rs對(duì)本文算法的影響。從圖中可以看出,感知半徑Rs=20時(shí),全局搜索能力最強(qiáng)。圖14給出了在G1服務(wù)規(guī)模下,且Rs固定為20,參數(shù)Rd對(duì)本文算法的影響。從圖中可以看出,決策半徑Rd在[18,20]范圍內(nèi),求得的全局最優(yōu)解質(zhì)量較高,且當(dāng)Rd=20時(shí),全局搜索能力最強(qiáng)。綜合上述實(shí)驗(yàn),對(duì)參數(shù)感知半徑和初始決策半徑設(shè)置為Rs=Rd=20,p1和p2設(shè)置為p1=0.05,p2=0.95,n和k的設(shè)置為n/k∈[15,30]。

圖13 感知半徑對(duì)本文算法性能的影響

圖14 決策半徑對(duì)本文算法性能的影響

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

針對(duì)云計(jì)算下大規(guī)模服務(wù)組合中的QoS全局最優(yōu)Web服務(wù)選擇問(wèn)題,本文在云計(jì)算平臺(tái)下利用MapReduce計(jì)算模型實(shí)現(xiàn)了離散螢火蟲(chóng)群優(yōu)化算法并行化,提出了求解該問(wèn)題的基于MapReduce的并行離散螢火蟲(chóng)群優(yōu)化算法。對(duì)傳統(tǒng)的DGSO算法進(jìn)行了改進(jìn),設(shè)計(jì)了離散螢火蟲(chóng)群優(yōu)化算法、Map函數(shù)和Reduce函數(shù),并將分群分治思想融入到算法中,避免算法過(guò)早陷入局部最優(yōu),加快算法收斂速度和提高算法的全局搜索能力。實(shí)驗(yàn)結(jié)果表明,MRDGSO算法在服務(wù)選擇問(wèn)題上得到了成功的應(yīng)用,具有對(duì)高維和大規(guī)模問(wèn)題的求解能力,表現(xiàn)出良好的擴(kuò)展性。今后將針對(duì)MRDGSO算法存在的問(wèn)題作進(jìn)一步改進(jìn),使之應(yīng)用到其他領(lǐng)域上,擴(kuò)展算法的實(shí)際應(yīng)用價(jià)值。

[1] 劉 旋,廖明潮.基于人工魚(yú)群算法的QoS全局最優(yōu)Web服務(wù)選擇的研究[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(8):87-90.

[2] 康國(guó)勝,劉建勛,唐明董,等.QoS全局最優(yōu)動(dòng)態(tài)Web服務(wù)選擇算法[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(1):73-76.

[3] 倪志偉,吳 昊,尹道明,等.云和聲搜索算法及其在知識(shí)服務(wù)組合中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用究,2013,30(3):806-809.

[4] 劉書(shū)雷,劉云翔,張 帆,等.一種服務(wù)聚合中QoS全局最優(yōu)服務(wù)動(dòng)態(tài)選擇算法[J].軟件學(xué)報(bào),2007,18(3):646-656.

[5] 張成文.基于遺傳算法的具有全局QoS限制的Web服務(wù)選擇[D].北京:北京郵電大學(xué),2007.

[6] 范小芹,蔣昌俊,方賢文,等.基于離散微粒群算法的動(dòng)態(tài)Web服務(wù)選擇[J].計(jì)算機(jī)研究與發(fā)展,2010,47(1):147-156.

[7] ZENG Liangzhao,BENATALLAH B,DUMAS M,et al.Web Engineering:Quality Driven Web Service Composition[C]//Proceedings of World Wide Web Conference.New York,USA:ACM Press,2003:411-421.

[8] 王會(huì)潁,倪志偉,伍章俊.基于MapReduce和多目標(biāo)蟻群算法的多租戶(hù)服務(wù)定制算法[J].模式識(shí)別與人工智能,2014,27(12):1105-1116.

[9] MCNABB A W,MONSON C K,SEPPI K D.Paralled PSO Using MapReduce[C]//Proceedings of the Congress on Evolutionary Computation.Singapore:[s.n.],2007:7-14.

[10] KRISHNANAND K N,GHOSE D.Glowworm Swarm Based Optimization Algorithm for Multimodal Functions with Collective Robotics Applications[J].Multiagent & Grid Systems,2006,2(3):209-222.

[11] KRISHNANAND K N,GHOSE D.Glowworm Swarm Optimization for Simultaneous Capture of Multiple Local Optima of Multimodal Functions[J].Swarm Intelligence,2009,3(2):87-124.

[12] 周永權(quán),黃正新,劉洪霞.求解TSP問(wèn)題的離散型螢火蟲(chóng)群優(yōu)化算法[J].電子學(xué)報(bào),2012,40(6):1164-1170.

[13] 倪志偉,肖宏旺,伍章俊,等.基于改進(jìn)離散型螢火蟲(chóng)群優(yōu)化算法和分形維數(shù)的屬性選擇方法[J].模式識(shí)別與人工智能,2013,26(12):1169-1178.

[14] ALJARAH I,LUDWIG S A.A New Clustering Approach Based on Glowworm Swarm Optimization[C]//Proceedings of IEEE Congress on Evolutionary Computation.Washington D.C.,USA:IEEE Press,2013:2642-2649.

[15] 龔小勇,朱慶生.支持QoS的Web服務(wù)選擇模型的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2008,34(24):55-57.

[16] 康國(guó)勝,劉建勛,唐明董,等.基于差異演化算法的QoS全局最優(yōu)動(dòng)態(tài)Web服務(wù)選擇[J].電信科學(xué),2011,27(12):67-71.

[17] 祝華正.螢火蟲(chóng)群算法的改進(jìn)及其應(yīng)用[D].南寧:廣西民族大學(xué),2011.

[18] JIN C,VECCHIOLA C,BUYYA R.An Extension of MapReduce for Parallelizing Genetic Algorithms[C]//Proceedings of the 4th International Conference on Escience.Washington D.C.,USA:IEEE Press,2008:214-221.

[19] 祝華正,何登旭.一種小規(guī)模多種群螢火蟲(chóng)群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(23):48-50.

[20] ALJARAH I,LUDWIG S A.A MapReduce Based Glowworm Swarm Optimization Approach for Multimodal Functions[J].Swarm Intelligence,2013,8237:22-31.

[21] ZHANG Kangli,CHEN Shouyuan,SHAO Zengzhen.The Improvement of Harmony Search Algorithm[J].Artificial Intelligence and Robotics Research,2015,4(4):32-39.