基于蟻群算法的Web服務選擇

摘 要： Web服務組合是為Web用戶提供高質量、個性化服務的主要手段，而Web服務選擇是進行組合的前提和基礎。闡述了蟻群算法的原理，分析了Web服務選擇的模型，把蟻群算法引入Web服務選擇領域，將基于QoS的Web服務選擇問題轉化為最優路徑選擇問題。給出了使用蟻群算法解決Web服務選擇問題的實施步驟，對比分析了蟻群算法在不同參數下對服務選擇正確率的影響，通過具體的場景測試了蟻群算法對于解決Web服務選擇問題的有效性。

關鍵詞： 蟻群算法； 群智能； Web服務選擇； 服務質量

中圖分類號： TN911?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2013）12?0009?03

0 引 言

如何滿足服務請求者的個性化和多樣化的要求，而又能高效合理的利用網絡資源，這是Web服務組合研究的重點問題。網絡上的Web服務種類和數目繁多，不免會出現功能重疊的情況，基于服務質量（Quality of Service，QoS）的Web服務選擇不失為一種行之有效的解決方法。與此同時引入智能搜索算法尋找最佳組合方案，能夠使Web服務組合過程更為高效合理。

文獻[1]將QoS引入Web服務領域，用Web服務的QoS屬性來區別功能相近的Web服務；文獻[2]和文獻[3]統一定義了Web服務的QoS屬性；文獻[4]考慮到QoS屬性之間的獨立性和量綱不統一的問題，給出了一種基于分型理論和多目標決策理論的服務選擇算法；文獻[5]提出一種動態選擇算法，利用遺傳算法的智能進化原理來進行服務選擇，但是其編碼模型在面對較大規模的Web服務時，選擇性能較差；文獻[6]提出了遺傳算法解決Web服務選擇問題的二次編碼模型，克服了一維編碼方式的局限性，但性能改善有限并可能陷入局部最優；文獻[7]在遺傳算法的基礎上采用矩陣編碼的方式，提出一種QoS感知的Web服務選擇算法。

本文在以上研究的基礎上，考慮到蟻群算法的群智能性和正反饋機制，將蟻群算法引入Web服務選擇領域，將Web服務的選擇問題轉化為尋找從起始功能服務到終止功能服務的最優路徑問題。文章介紹了蟻群算法的起源和基本思想，闡述了基于蟻群算法的Web服務選擇問題描述，給出基于蟻群算法的Web服務選擇算法的實施步驟，并通過具體場景測試蟻群算法對于解決Web服務選擇問題的有效性。

1 基于QoS的Web服務選擇模型

本文用一個順序流程的場景來描述一般Web服務選擇問題。若一個Web服務由M個不同功能的原子服務組成，每個服務又包含N個功能相同或相似的原子服務，稱為候選服務，但他們的非功能屬性，即QoS屬性是各不相同的，基于QoS屬性，擇優取一，那么存在的可行

解就有Nm個。基于實際情況，本文將響應時間（Time），價格（Price），可靠性（Availablity）這三個QoS指標作為描述服務的非功能屬性。基于QoS的Web服務選擇就是要根據用戶提出的QoS請求，作為約束條件，在可行解中找到最優解。這樣就將服務選擇問題轉化為了多目標決策問題，從而使用智能搜索算法來解決。

2 蟻群算法介紹

2.1 蟻群算法源起

受自然界中真實蟻群集體行為的啟發，意大利學者Dorigo于1991年首次系統地提出了一種基于螞蟻種群的新型優化算法——蟻群算法[8]，并用該方法解決了一系列組合優化問題，蟻群算法在解決這類問題中取得了較好的實驗結果，開始被眾多研究者應用到實際工程中。

蟻群算法提出了人工螞蟻和信息素的概念，自然界中的螞蟻會在它們覓食的路徑上留下信息素這種化學物質，影響和吸引其他螞蟻。最終當覓食的螞蟻數量足夠多時，最優路徑上的信息素濃度必然最高。據此可以找到螞蟻覓食的最佳路徑，即一般問題的最優解。

2.2 蟻群算法數學模型

蟻群算法最常見的應用是用來解決旅行商問題（TSP）[9]，本文即以此為例來介紹蟻群算法的數學模型。

3 Web服務選擇的蟻群算法描述

在第1節描述的Web服務選擇模型中，若把起點作為蟻巢，結束點作為食物。那么尋找最佳組合方案的過程就對應于螞蟻尋找食物的最佳路徑的過程。

螞蟻的移動過程是蟻群算法解決Web服務選擇問題的核心，根據蟻群算法的原理，結合Web服務選擇模型，螞蟻每經過一個服務類，在前往下一個服務類的過程中，需要計算螞蟻由當前服務到下一個服務類中每一個服務的轉移概率，這里使用式（1）確定轉移概率，本文中采用輪盤賭算法作為選擇算子確定螞蟻的移動方向。

4 蟻群算法的服務選擇流程

5 模擬驗證

5.1 蟻群算法參數對測試結果的影響

5.2 服務測試數據

表2 蟻群算法獨立運行10次的結果

在第6次測試中，進化值沒有達到最優解，也未達到最大迭代次數，說明陷入了局部最優。導致該問題的原因可能是參數的設定還有待優化，或螞蟻在位置移動時的選擇算子不合適。由于蟻群算法的正反饋機制，隨著迭代次數增加，會出現概率轉移不均勻，從而使算法陷入局部最優。

6 結 語

本文闡述了蟻群算法的基本原理和思想，分析了Web服務的選擇模型，將蟻群算法引入Web服務選擇領域，將Web服務選擇問題轉化為最優路徑選擇問題，結合蟻群算法的生物學基礎，給出了蟻群算法解決Web服務選擇問題的實施步驟，最后通過具體的場景測試了蟻群算法在Web服務選擇領域的有效性，并分析了蟻群算法在該領域應用中容易出現的問題和原因，拓寬了Web服務選擇問題的解決思路。但是如何在蟻群算法中選用合適的選擇算子，避免在解決Web服務選擇問題時過早的陷入局部最優，仍然需要進一步的研究與測試。

參考文獻

[1] ZENG Liang?zhao， BENATALLAH B， ANNE H H， et al. QoS?aware middleware for Web service composition [J]. IEEE Tran?

sactions on Software Engineering， 2004， 30（5）： 311?327.

[2] ISO. ISO 8402 quality management and quality assurance： vocabulary [S]. [S.l.]： ISO， 2000.

[3] International Telecommunication Union?T. ITU?T E.800 terms and definitions related to quality of service and network performance including dependability [S]. [S.l.]： International Telecommunication Union?T， 1994.

[4] 陳彥萍，李增智，郭志勝.Web服務組合中基于服務質量的服務選擇算法[J].西安交通大學學報，2006（8）：897?900.

[5] 劉書雷，劉云翔，張帆.一種服務聚合中QoS全局最優服務動態選擇算法[J].軟件學報，2007，18（3）：646?656.

[6] WANG Rong?xi， MA Li， CHEN Yan?ping. The Web service selection based on the genetic algorithm [J]. Computer Science and Service System， 2011， 6： 1861?1864.

[7] 彭曉明，何炎祥，朱兵艦.蟻群算法在Web服務組合中的應用[J].計算機工程，2009，35（10）：182?187.

[8] 黃友銳.智能優化算法及其應用[M].北京：國防工業出版社，2008.

[9] 雷德明，嚴新平.多目標智能優化算法及其應用[M].北京：科學出版社，2009.

[10] 盧宇凡，張莉.自適應蟻群算法在求解TSP問題中的應用[J].微型機與應用，2012，31（17）：78?83.