頡斌,楊揚,王潔瑩

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

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

　　關鍵詞：服務組合；服務組合優化；蟻群算法

0引言

　　隨著云計算的發展，Web服務組合優化問題已經成為了國內外研究的熱點。現有優化算法一般是啟發式算法。許多研究結果表明，蟻群優化算法具有分布式計算、魯棒性好等優勢，但通常需要足夠的群落大小和足夠數量的迭代。隨著目標問題規模的增長，會導致計算效率低下。蟻群算法的求解主要是在集中式串行環境下，而在云計算環境中，利用云計算技術將蟻群算法并行化對問題進行分布式并行求解的研究較少。

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

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

1問題建模

　　1.1優化目標建模

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

　　（1)服務的負載

　　QB(Si)=λ/μ(1)

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

　　（2)服務級別協議（SLA）

　　本文選取3個服務質量參數：價格C(Si) 、執行時間T(Si)、可靠性A(Si)。

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

　　QC(Si)=C(2)

　　執行時間T(Si)的密度函數為：

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

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

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

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

　　（3)用戶優先級

　　L(Si)=l(5)

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

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

　　1.2Web服務組合優化問題的建模

　　在Web服務組合優化的過程中，對非功能性屬性簡單地加和會影響某些屬性值，不能準確地表達非功能性屬性［7］。通常將Web服務組合優化問題轉換成有限方案的多目標決策問題，在各目標之間進行協調權衡，使得所有目標函數盡可能達到最優。

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

　　設單個Web服務為Sij={Fij，Qij}，其中Fij為功能性屬性集合。服務組合優化問題就是在由服務節點構成的圖中的多條路徑中選擇一條，使得這條路徑中的各個非功能屬性的匯總能夠符合用戶需求［8］。這就將服務組合優化的問題轉換為了一個多目標決策的數學問題，即針對組合服務的多個非功能性目標進行優化。本文考慮串行服務組合問題。

　　（1)負載

　　利用式(6)和式(7)對服務的各個非功能性屬性進行預處理。設這個組合服務中共包含m個子服務實例，候選服務實例共有n個，則將Web服務組合優化問題轉換為多目標優化的數學模型，多目標函數如式(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個目標函數均盡量達到最小，此時所得到的Pareto最優解集就是服務組合優化后的解集。

2基于MapReduce改進的蟻群算法

　　2.1多信息素蟻群算法

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

　　通常把信息素限制在一個區間，設為［τmin,τmax］。用于Web服務組合優化的多信息素蟻群算法1如下所述：

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

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

　　(2)設定目標函數共為n個，總的迭代循環次數為m；

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

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

　　(5)如果j=n，則計算結束，否則返回步驟（2）繼續計算。

　　2.2狀態轉移概率

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

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

　　算法2:解的構建算法

　　（1)初始化解為空；

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

　　（3)如果所有任務都已選擇完成，則返回，否則轉到步驟（2）。

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

　　2.3信息素更新規則

　　綜上所述，信息素更新規則總結如下：

　　算法3: 信息素更新規則

　　（1)初始化i=1。

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

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

　　(4)若解Si優于解Sibest，則令Sibest=Si。

　　(5)若信息素表未被完全更新，則i增加1，算法跳轉到步驟（3)；否則返回，更新信息素結束。

　　2.4MapReduce并行化改進

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

3仿真實驗

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

　　3.1算法優化效果測試

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

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

　　上述實驗證明了本文算法的有效性，結果穩定且有良好的魯棒性。

　　3.2MapReduce并行化效率提升測試

　　本實驗中，算法連續運行10次，對運行時間取平均值，結果如圖3所示。其中橫坐標是MapReduce并行化節點job個數，縱坐標是運行時間（ms）。

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

4結論

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

參考文獻

　　［1］ 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.

　　［2］ 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.

　　［4］ 夏衛雷,王立松.基于MapReduce的并行蟻群算法研究與實現［J］.電子科技,2013, 26(2):146149.

　　［5］ 徐忠勝,沈蘇彬.一種云計算資源的多目標優化的調度方法［J］.微型機與應用, 2015,34(13):1720.

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

　　［7］ 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.

　　［8］ 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.