基于改進蟻群算法的Ｗｅｂ 服務組合優化

摘 要：為解決基礎蟻群算法存在的前期搜索速度慢、后期容易陷入局部最優解的問題，針對服務組合的動態性、不穩定性以及非功能屬性限制等情況，提出基于改進蟻群算法的 Web 服務組合優化方法首先分別介紹基本蟻群算法和 L-I-ACO 改進蟻群算法，再將其應用到 Web 服務組合優化建模中，最后通過對比實驗測試兩種算法的性能。實驗結果表明，L-I-ACO 改進蟻群算法性能較好，它彌補了基礎蟻群算法的不足，提高了動態組合優化過程中的準確率和效率，更利于選取符合客戶要求的服務

關鍵詞：改進蟻群算法;Web 服務組合優化;動態服務組合;L-IACO 算法

中圖法分類號：TP393文獻標識碼：A

１ 引言

動態服務組合技術是當前的研究熱點，在動態服務組合的整個流程中，需要選取符合用戶要求的服務，這涉及選取相同屬性的多個服務和組合服務。隨著提供的服務不斷增多，選取服務問題的范圍快速擴大，因此解決動態服務組合中的服務選取問題變得尤為重要［１～２］ 。這種解決服務選取問題被稱為服務組合優化，是一個ＮＰ 難問題。由于Ｗｅｂ 服務或許存在狀態不穩定、服務非功能屬性經常變化等情況，因此動態服務組合中的服務選取問題需要一種能夠動態適應各種服務狀態變化的最優算法［３］ 。

目前，研究的一些主要方法包括貪心算法、遺傳算法、神經網算法等。其中，貪心算法簡單易用，但往往不能得到全局最優解；遺傳算法可以較好地處理復雜的組合優化問題，但計算量較大；神經網絡算法可以快速實現并具有適應性，但對服務的不確定性和動態性處理效果有限；傳統的蟻群算法有收斂速度慢和易于停滯等缺點，無法很好地解決組合服務優化中存在的多種非功能屬性約束的問題［４～６］ 。因此，為解決上述問題，本文使用改進蟻群算法進行服務組合優化，其不僅性能良好，而且能應付Ｗｅｂ 服務的動態特性。其特點是能適應動態服務優化，在非功能屬性值計算過程中可及時調整計算方式，而且需設參數少，操作簡單，優化速度快，結果準確性高。

２ 基于改進蟻群算法的Ｗｅｂ 服務組合優化

２．１ 基本蟻群算法描述

蟻群算法（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ） 是由Ｄｏｒｉｇｏ 等在１９９１ 年的第一屆歐洲人工生命會議上提出的一種隨機搜索算法，該算法是通過模擬大自然中螞蟻尋找食物的過程而得出的［７］ 。蟻群算法是仿生優化算法的一種，其特點有魯棒性強、并行分布式計算，以及易與其他方法結合等。經過螞蟻之間互相配合、協調工作，在多個目標優化問題中找到最好的解決方式。該方法在動態組合規劃問題、車輛路徑問題和旅行商問題等方面已得到廣泛的應用［８］ 。

采用蟻群算法處理Ｗｅｂ 服務組合優化問題的主要方式是螞蟻的位移過程，用此算法計算Ｗｅｂ 服務組合優化模型時，每當螞蟻路過一個抽象服務下的ＣＳ時都需要計算候選ＣＳ 的轉移概率，候選ＣＳ 指螞蟻所在位置的ＣＳ 和下一個ＡＳ 中間含有的全部ＣＳ。公式所示為該轉移概率計算方法：

２．２ Ｌ?Ｉ?ＡＣＯ 算法的設計與實現

２．２．１ Ｌ?Ｉ?ＡＣＯ 算法狀態轉移概率

當Ｗｅｂ 服務組合需要解決多個非功能性屬性約束的問題時，隨著循環次數不斷增加，基本蟻群算法因其具有收斂速度慢、易于停滯的缺點，容易導致信息素在局限的少量路徑上停留，易出現循環停滯現象。這樣得到的處理結果只能算是局部優化，所以基本蟻群算法無法很好地解決這個問題［９］ 。因此，本文研究了Ｌ?Ｉ?ＡＣＯ 改進蟻群算法來解決Ｗｅｂ 服務組合優化問題。

２．２．２ Ｌ?Ｉ?ＡＣＯ 改進蟻群算法

一個抽象服務含有多個候選服務實例，如圖１ 所示，多個候選服務存在于２ 個節點中間。若優化處理每一個路徑，則是一個十分大的計算工程，大幅增加了組合優化問題的難度。但是，若努力縮小優化問題的范圍，將大范圍分解成小范圍，則可降低算法的尋優難度。

Ｌ?Ｉ?ＡＣＯ 算法從預計算部分和隨機選取尋優部分兩個方面展開計算，預計算部分把近似同類屬性的服務分到一起，成為一個節點并增加限定要求，去掉屬性不相近的服務，以縮小搜索范圍。

給同類屬性分類時，可采用近似值匹配的方法。若把含有ｎ 個非功能性屬性Ｑ 的服務設為ｓ，將代表這些屬性的量化值轉換成函數Ｑ１（ｓ），Ｑ２（ｓ），…，Ｑｎ（ｓ），把含有ｍ 個非功能性屬性Ｑ 的服務設為ｓ′，將代表這些屬性的量化值轉換成函數Ｑ′１（ｓ′），Ｑ′２（ｓ′），…Ｑ′ｍ（ｓ′），若ｓ 和ｓ′服務屬性相似，則ｎ≈ｍ，Ｑ１（ｓ）≈Ｑ′１（ｓ′）…，因此可以計算這２ 個服務的指標，如公式（６）所示：

Ｃ（ｓ，ｓ′）＝ Σ ｍｉｎ（ｎ，ｍ）ｒ ＝１ （Ｑｒ（ｓ）－Ｑ′ｒ（ｓ′））２ （６）

可以看出，若ｓ 和ｓ′相似，則Ｃ（ｓ，ｓ′）接近于０，因此可以判斷２ 個服務的近似度。但此方法并不完善，若ｓ 和ｓ′的匹配度接近０，同時ｓ′和ｓ″的匹配度也接近０，則此時很難自動把該３ 個服務規分為一類。這種狀況下，需考慮先把ｓ′和ｓ″分到一類，之后繼續分配其他服務，待計算好所有服務近似匹配分類后，若發現ｓ″與某一類的大部分服務匹配度接近０，則可把ｓ″分到這一類。

由于動態服務組合以及服務質量的諸多因素具有不確定性，因此對狀態轉移概率的路徑選取進行了改變，具體做法如下：首先，采用改變計算概率值或隨機的方式選取服務；其次，篩選出不滿足條件的服務，這時就可采用狀態轉移概率的方式，這一操作可縮小服務選擇范圍，降低計算難度，提高計算速度，詳細算法如下。

假如最大循環次數可用Ｎｃｍａｘ 表示；螞蟻個數用Ｍ 表示；最優服務列表用Ｌｉｊ表示，其中ｉ 和ｊ 代表需要服務選擇分類的服務組合中的抽象服務，即Ｓｉｊ 中設ｔ＝０ 代表初始化時間、Ｎｃ ＝０代表循環控制變量、ｋ ＝０ 代表螞蟻循環變量。

為解決服務組合優化問題，則需使式（１９）中的５個目標函數都達到最小，服務組合優化后的解集便是得到的Ｐａｒｅｔｏ 最優解集。

３ 實驗

本實驗在兩種情況下分別測試基本蟻群算法和Ｌ?Ｉ?ＡＣＯ 改進蟻群算法的Ｗｅｂ 服務組合優化的成功率，情況１ 是任務節點數是２０，服務數是４８；情況２ 是任務節點數是３５，服務數是１１０。每種情況測試８ 次。結果如圖２、圖３ 所示。

通過分析圖２ 和圖３ 曲線可得：基本蟻群算法在服務數是４８ 時，隨著迭代次數的增加，成功率呈波動狀態，不穩定，且總體成功率都在０．７ 以下。當服務數是１１０ 時，曲線波動減少，但是成功率較低且一直沒有超過０．６，說明基本蟻群算法收斂速度慢，容易陷入局部最優解，無法高成功率地實現最終服務組合優化。Ｌ?Ｉ?ＡＣＯ 改進蟻群算法性能相對較好，在服務數是４８ 和服務數是１１０ 時，都能達到平均成功率９０％以上，雖在迭代初期曲線稍有波動，但最后都達到平穩高度，證明本文研究的Ｌ?Ｉ?ＡＣＯ 改進蟻群算法既彌補了基本蟻群算法的不足，又能大幅提高了Ｗｅｂ 服務組合優化的成功率。

４ 結束語

隨著互聯網技術的發展，網絡上涌現了大量種類繁多的Ｗｅｂ 服務，但其中很大一部分Ｗｅｂ 服務提供的功能是相互重疊的，并且這些服務的功能多數是小粒度的，難以充分滿足用戶需求。為解決這些問題，Ｗｅｂ 服務組合技術應運而生。Ｗｅｂ 服務組合將具有相同功能的Ｗｅｂ 服務合并為集合，并根據用戶需求選擇組合多個簡單的Ｗｅｂ 服務，以形成新的功能更強大的Ｗｅｂ 服務。本文旨在提出一種高效方法，從眾多的Ｗｅｂ 服務數據庫中，選擇出滿足用戶需求且滿足ＱｏＳ 限制的Ｗｅｂ 服務，進而組合成更優的Ｗｅｂ 服務。本文通過對基本蟻群算法進行改進，提出了Ｌ?Ｉ?ＡＣＯ 改進蟻群算法，既彌補了普通蟻群算法的不足，又能高效率、高準確率地選取滿足客戶需求的Ｗｅｂ 服務組合。

參考文獻：

［１］ 倪志偉，方清華，李蓉蓉，等．改進蟻群算法在基于服務質量的ＷＥＢ 服務組合優化中的應用［Ｊ］．計算機應用，２０１５，３５（８）：２２３８?２２４３＋２２７９．

［２］ 頡斌，楊揚，王潔瑩．基于ＭＡＰＲＥＤＵＣＥ 改進蟻群算法的ＷＥＢ 服務組合優化［Ｊ］．微型機與應用，２０１６，３５（８）：６１?６４．

［３］ 陳宇鋒．改進蟻群算法在ＷＥＢ 服務中應用與實現［Ｄ］．長沙：湖南大學，２０１９．

［４］ 曹騰飛，符云清，鐘明洋．融合遺傳蟻群算法的ＷＥＢ 服務組合研究［Ｊ］．計算機系統應用，２０１２，２１（６）：８１?８５．

［５］ 承松，周井泉，常瑞云．混沌蟻群算法的ＷＥＢ 服務組合優化研究［Ｊ］．計算機技術與發展，２０１７，２７（２）：１７８?１８１＋１８６．

［６］ 夏亞梅，程渤，陳俊亮，等．基于改進蟻群算法的服務組合優化［Ｊ］．計算機學報，２０１２，３５（２）：２２７０?２２８１．

［７］ 謝琴．蟻群算法在ＷＥＢ 日志挖掘中的研究與應用［Ｄ］．重慶：重慶大學，２００６．

［８］ 馬文龍，王錚，趙燕偉．基于改進蟻群算法的制造云服務組合優化［Ｊ］．計算機集成制造系統，２０１６，２２（１）：１１３?１２１．

［９］ 承松．云計算環境下基于蟻群算法的ＷＥＢ 服務組合研究［Ｄ］．南京：南京郵電大學，２０１７．

［１０］ 李東星，陳喆，錢雙洋，等．改進蟻群算法及其在云服務組合優化中的應用研究［Ｊ］．計算機應用與軟件，２０１７，３４（３）：１３?２０＋２６．

作者簡介：

裴毓（ １９８９—）， 碩士， 助理工程師， 研究方向： 計算機網絡。