《電子技術應用》
您所在的位置:首頁 > 通信與網(wǎng)絡 > 設計應用 > 基于MapReduce改進蟻群算法的Web服務組合優(yōu)化
基于MapReduce改進蟻群算法的Web服務組合優(yōu)化
2016年微型機與應用第08期
頡斌,楊揚,王潔瑩
(北京科技大學 計算機通信工程學院,北京100083)
摘要: 對于Web服務組合優(yōu)化的問題,,蟻群算法的求解主要是串行進行,,收斂時間長,容易收斂于非最優(yōu)解。在云計算環(huán)境中,,將蟻群算法并行化,,可對Web服務組合優(yōu)化問題進行分布式并行求解,。根據(jù)多目標優(yōu)化模型給出基于多信息素的蟻群算法,,使用MapReduce并行編程框架對蟻群算法中最耗時的部分——螞蟻獨立求解的過程并行化,給出了使用MapReduce改進的基于多信息素的蟻群優(yōu)化算法,,有效地對Web服務組合進行全局優(yōu)化,,彌補傳統(tǒng)的蟻群算法求解過程的缺點。
Abstract:
Key words :

  頡斌,楊揚,王潔瑩

  (北京科技大學 計算機通信工程學院,北京100083)

  摘要:對于Web服務組合優(yōu)化的問題,,蟻群算法的求解主要是串行進行,,收斂時間長,容易收斂于非最優(yōu)解,。在云計算環(huán)境中,,將蟻群算法并行化,可對Web服務組合優(yōu)化問題進行分布式并行求解,。根據(jù)多目標優(yōu)化模型給出基于多信息素的蟻群算法,,使用MapReduce并行編程框架對蟻群算法中最耗時的部分——螞蟻獨立求解的過程并行化,給出了使用MapReduce改進的基于多信息素的蟻群優(yōu)化算法,,有效地對Web服務組合進行全局優(yōu)化,,彌補傳統(tǒng)的蟻群算法求解過程的缺點。

  關鍵詞:服務組合,;服務組合優(yōu)化,;蟻群算法

0引言

  隨著云計算的發(fā)展,Web服務組合優(yōu)化問題已經(jīng)成為了國內(nèi)外研究的熱點?,F(xiàn)有優(yōu)化算法一般是啟發(fā)式算法,。許多研究結(jié)果表明,蟻群優(yōu)化算法具有分布式計算,、魯棒性好等優(yōu)勢,,但通常需要足夠的群落大小和足夠數(shù)量的迭代。隨著目標問題規(guī)模的增長,,會導致計算效率低下,。蟻群算法的求解主要是在集中式串行環(huán)境下,而在云計算環(huán)境中,,利用云計算技術將蟻群算法并行化對問題進行分布式并行求解的研究較少,。

  大多數(shù)現(xiàn)有并行化的蟻群算法都依賴于使用傳統(tǒng)的并行編程模型來實現(xiàn)。MANFRIN M等人用消息傳遞接口(Message Passing Interface,MPI)在多機環(huán)境中實現(xiàn)了TSP的并行ACO [1],。CRAUS M等人用一種一主多從機制實現(xiàn)了基于MPI的并行ACO算法[2],。Huang Diwei等人用MapReduce實現(xiàn)了作業(yè)調(diào)度問題的遺傳算法,并得到了合理的結(jié)果[3],。參考文獻[4]用MapReduce針對TSP實現(xiàn)了并行的蟻群算法,,但存在多次迭代使算法性能降低的問題。

  本文提出將蟻群算法并行化的思想,,使用MapReduce并行化編程模型,,將基本的蟻群算法并行化,可解決云計算環(huán)境下使用蟻群算法進行Web服務組合優(yōu)化容易出現(xiàn)的求解困難的問題,。本文根據(jù)多目標優(yōu)化模型給出基于多信息素的蟻群算法,,使用MapReduce并行編程框架對蟻群算法中最耗時的部分——螞蟻獨立求解的過程并行化,給出使用MapReduce改進的基于多信息素的蟻群算法,。

1問題建模

  1.1優(yōu)化目標建模

  本文選擇子服務的負載,、服務級別協(xié)議[5](Service Level Agreement, SLA)(包括價格C(Si)、執(zhí)行時間T(Si),、可靠性A(Si))以及用戶優(yōu)先級這3個非功能性屬性約束條件來制定服務組合優(yōu)化的目標準則,。利用排隊論思想,定義這些指標為隨時間t變化而變化的密度分段函數(shù),。

 ?。?)服務的負載

  QB(Si)=λ/μ(1)

  其中,λ為任務到達率,,μ為服務率,。

  (2)服務級別協(xié)議(SLA)

  本文選取3個服務質(zhì)量參數(shù):價格C(Si) ,、執(zhí)行時間T(Si),、可靠性A(Si)。

  服務的價格C(Si)表示為:

  QC(Si)=C(2)

  執(zhí)行時間T(Si)的密度函數(shù)為:

  QT(Si)=p(T(Si))=(μ-λ)e-(μ-λ)t,t>0(3)

  服務Si的可靠性A(Si)反映了服務的可靠程度,即單位時間內(nèi)服務可用的時間與服務的失效率成反比,。出錯率的分布函數(shù)為:

  QA(Si)=p(A(Si))=βt,0<t<T(4)

  其中,,T為出錯維護時間。

 ?。?)用戶優(yōu)先級

  L(Si)=l(5)

  本文采用參考文獻[6]中的預處理方法,,將這些非功能性屬性的值進行標準化的轉(zhuǎn)換。設一個Web服務Sij,,具有n個非功能性屬性,,表示為Qij={q1ij,q2ij,…,qnij},。通過式(6),、式(7)進行轉(zhuǎn)換。若第r個屬性為正屬性,,則用式(6)處理,;若第r個屬性為負屬性,則用式(7)處理,。

  67.png

  其中,,qrmax為組合服務中全部Web服務中第r個屬性中的最大值,∑qrml為組合服務中全部Web服務的第r個屬性之和,。

  1.2Web服務組合優(yōu)化問題的建模

  在Web服務組合優(yōu)化的過程中,,對非功能性屬性簡單地加和會影響某些屬性值,不能準確地表達非功能性屬性[7],。通常將Web服務組合優(yōu)化問題轉(zhuǎn)換成有限方案的多目標決策問題,,在各目標之間進行協(xié)調(diào)權衡,使得所有目標函數(shù)盡可能達到最優(yōu),。

  將多目標優(yōu)化問題定義為一個三元組:(X,C,F),。其中X代表一個n維決策空間,即x=(x1,x2,…,,xn)∈X,;C代表一個集合,包含了一組決策變量所同時滿足的約束條件,;F是一個矢量,,包含所有的目標函數(shù),個數(shù)m≥2,,可表示為:F=(f1(x),f2(x),…,,fm(x))。多目標優(yōu)化就是使這些不同的目標函數(shù)同時達到最小,。當多個目標要同時達到最優(yōu)時,,最優(yōu)解就是Pareto最優(yōu)集,。

  設單個Web服務為Sij={Fij,Qij},,其中Fij為功能性屬性集合,。服務組合優(yōu)化問題就是在由服務節(jié)點構(gòu)成的圖中的多條路徑中選擇一條,使得這條路徑中的各個非功能屬性的匯總能夠符合用戶需求[8],。這就將服務組合優(yōu)化的問題轉(zhuǎn)換為了一個多目標決策的數(shù)學問題,,即針對組合服務的多個非功能性目標進行優(yōu)化,。本文考慮串行服務組合問題,。

  (1)負載

  812.jpg

  利用式(6)和式(7)對服務的各個非功能性屬性進行預處理,。設這個組合服務中共包含m個子服務實例,,候選服務實例共有n個,則將Web服務組合優(yōu)化問題轉(zhuǎn)換為多目標優(yōu)化的數(shù)學模型,,多目標函數(shù)如式(13)所示,。

  f1=∑mi=1λiμi∑ni=1λiμi

  f2=m(QCmax+1)∑ni=1Ci-1

  f3=m(QTmax+1)τe-τt-1

  f4=∑mi=1βit∑ni=1βit

  f5=∑mi=1li∑ni=1li(13)

  算法的目標就是使式(13)中的5個目標函數(shù)均盡量達到最小,此時所得到的Pareto最優(yōu)解集就是服務組合優(yōu)化后的解集,。

2基于MapReduce改進的蟻群算法

  2.1多信息素蟻群算法

  基本的蟻群算法是針對于單一種類信息素的,,因而無法解決組合服務中多屬性約束的問題。但本文是針對Web服務組合中的多個非功能性屬性進行優(yōu)化,,因此要對蟻群算法進行改進,。在本文的改進蟻群算法中,啟發(fā)式信息和信息素都用服務的多個非功能性屬性來表示,,每個非功能性屬性都對應一個目標函數(shù),。

  通常把信息素限制在一個區(qū)間,設為[τmin,τmax],。用于Web服務組合優(yōu)化的多信息素蟻群算法1如下所述:

  算法1:多信息素蟻群算法

  (1)所有信息素初始化都為τmax,;

  (2)設定目標函數(shù)共為n個,總的迭代循環(huán)次數(shù)為m,;

  (3)蟻群算法開始,,每只螞蟻開始行動。第j代螞蟻單獨選路時,,隨機選取一個優(yōu)化目標函數(shù)(設為第i個),,然后以第i個信息素表中的信息素求解一個解(求解方法見算法2);

  (4)單獨選路完畢,,即更新第i個信息素表中的所有信息素值,;

  (5)如果j=n,則計算結(jié)束,,否則返回步驟(2)繼續(xù)計算,。

  2.2狀態(tài)轉(zhuǎn)移概率

  將服務實體Sij的第k個非功能性屬性的信息素表示為τki(j),,將第k個非功能性屬性的啟發(fā)式信息表示為ηki(j)。狀態(tài)轉(zhuǎn)移概率的計算公式如式(14)所示,,其中α和β參數(shù)分別決定了信息素和啟發(fā)式信息的相對影響力,。

  14.png

  規(guī)定式(14)中的啟發(fā)式信息ηi(j)為用戶所關注的所有非功能屬性的啟發(fā)式信息(即n個優(yōu)化目標)之和,由式(15)求出,。根據(jù)這個規(guī)則求解即可完成組合服務的多目標優(yōu)化,。利用這個轉(zhuǎn)移概率,基于多信息素的蟻群算法中螞蟻根據(jù)信息素求解的過程如下:

  算法2:解的構(gòu)建算法

 ?。?)初始化解為空,;

  (2)按照式(14)計算出下一子任務中所有子服務實體的轉(zhuǎn)移概率,,選擇轉(zhuǎn)移概率最大的服務實體,,更新解空間;

 ?。?)如果所有任務都已選擇完成,,則返回,否則轉(zhuǎn)到步驟(2),。

  ηi(j)=∑nk=1ηki(j)(15)

  2.3信息素更新規(guī)則

  綜上所述,,信息素更新規(guī)則總結(jié)如下:

  1618.png

  算法3: 信息素更新規(guī)則

  (1)初始化i=1,。

 ?。?)首先按照式(16)求出新的第i個信息素表中的信息素值,范圍已設定為[τmin,τmax],,若超過,,則取邊界值。

  (3)利用目標函數(shù)fi的公式計算出所有解的目標函數(shù)值,,根據(jù)式(17)求出Δτk,,利用式(18)計算最新的信息素。更新后的信息素值若在[τmin,τmax]之外,,則一律取邊界值,。

  (4)若解Si優(yōu)于解Sibest,則令Sibest=Si,。

  (5)若信息素表未被完全更新,,則i增加1,算法跳轉(zhuǎn)到步驟(3),;否則返回,,更新信息素結(jié)束。

  2.4MapReduce并行化改進

  本文為了使用蟻群算法解決多目標優(yōu)化的問題并減少計算量,,將基于多信息素的蟻群算法進行并行化的改進,。在云計算環(huán)境下,,引入MapReduce思想,改進蟻群算法,,應用Map函數(shù)來并行化每只螞蟻的獨立求解過程,,用Reduce函數(shù)分解出問題的解和值,求得較優(yōu)解并處理信息素更新,。從整體結(jié)構(gòu)上,,應用云計算的管道能力實現(xiàn)逐代的計算。具體設計如下:將多個Map,、Reduce函數(shù)首尾相連,,本代任務的輸出作為下一代任務的輸入,開始下一個并行計算任務,。將多對Map,、Reduce任務串行起來,,形成一個Map1Reduce1Map2Reduce2…MapnReducen的執(zhí)行序列,。

3仿真實驗

  本實驗以校園云平臺為背景、以平臺上的服務組合實例為基礎進行,。組合服務實例共有5個子任務,,將每個子任務上部署10個服務實例。實驗部署在Apache Hadoop 0.21.0環(huán)境中,,MapReduce集群包含了16個節(jié)點,。實驗中螞蟻數(shù)=100,循環(huán)次數(shù)n=2 000,,集群中計算機數(shù)目=2,。其他參數(shù)取值為:τmin=10,τmax=100,,ρ=0.01,,啟發(fā)式信息按照式(15)取值,信息素按算法3進行迭代更新,。

  3.1算法優(yōu)化效果測試

  每輪測試10次,,取平均數(shù)。針對兩種情況進行對比實驗:α=2,,β=2,;α=1,β=4,,輸出結(jié)果如圖1,、圖2所示。圖中縱軸代表各個目標函數(shù)的結(jié)果的平均值,。

  

001.jpg

002.jpg

  由圖1,、圖2可見,,5個目標函數(shù)隨著循環(huán)次數(shù)增加全部呈減小趨勢,并且在一定的循環(huán)次數(shù)時趨近于穩(wěn)定值,。圖2中目標函數(shù)收斂得更快一點,,可見通過改進的蟻群算法,使得服務組合得到了有效優(yōu)化,。第二組參數(shù)取值中,,β取值較大,說明螞蟻在選路時,,受到啟發(fā)式信息的影響更大,,所以目標函數(shù)收斂速度更快。

  上述實驗證明了本文算法的有效性,,結(jié)果穩(wěn)定且有良好的魯棒性,。

  3.2MapReduce并行化效率提升測試

  本實驗中,算法連續(xù)運行10次,,對運行時間取平均值,,結(jié)果如圖3所示。其中橫坐標是MapReduce并行化節(jié)點job個數(shù),,縱坐標是運行時間(ms),。

  

003.jpg

  由圖3可見,折線圖呈近線性下降趨勢,,表明該并行化方法達到了近線性的加速優(yōu)化,,說明基于MapReduce對蟻群算法中最耗時的螞蟻獨立求解部分進行并行化,有效提高了優(yōu)化效率,。

4結(jié)論

  本文改進了傳統(tǒng)的蟻群算法,,增加多信息素,使其適用于多目標優(yōu)化的數(shù)學問題,,同時考慮到蟻群算法的隱含并行性質(zhì),,利用MapReduce框架將算法中最耗時的螞蟻獨立求解過程并行化。根據(jù)制定好的目標準則,,使用改進過的蟻群算法對云計算環(huán)境下的Web服務組合進行有效的全局性優(yōu)化,。通過仿真實驗驗證了方法的有效性。

參考文獻

 ?。?] MANFRIN M, BIRATTARI M, STTZLE T, et al. Parallel multicolony ACO algorithm with exchange of solutions[C]. BelgiumNetherlands Conference on Artificial Intelligence, 2006.

 ?。?] CRAUS M, RUDEANU L. Parallel framework for antlike algorithms[C]. 2004 Third International Symposium on Parallel and Distributed Computing, 2004 Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks,  IEEE, 2004:3641.

  [3] Huang Diwei, Lin Jimmy. Scaling populations of a genetic algorithm for job shop scheduling problems using MapReduce[C]. Proceedings of the 2010 IEEE Second International Conference on Cloud Computing Technology and Science, IEEE Computer Society, 2010:780785.

 ?。?] 夏衛(wèi)雷,王立松.基于MapReduce的并行蟻群算法研究與實現(xiàn)[J].電子科技,2013, 26(2):146149.

 ?。?] 徐忠勝,沈蘇彬.一種云計算資源的多目標優(yōu)化的調(diào)度方法[J].微型機與應用, 2015,34(13):1720.

  [6] 劉彬,張仁津.基于QoS多目標優(yōu)化的Web服務組合方法[J].計算機工程與設計,2012, 33(3):885889.

 ?。?] AKBAR M M, MANNING E G, SHOJA G C, et al. Heuristic solutions for the multiplechoice multidimension knapsack problem[M]. Computational Science ICCS 2001. Springer Berlin Heidelberg, 2001:659668.

 ?。?] WADA H, SUZUKI J,YAMANO Y, et al. E3: a multiobjective optimization framework for SLAaware service composition[J]. IEEE Transactions on Services Computing, 2012, 5(3):358372.


此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權禁止轉(zhuǎn)載。