基于改進蟻群算法的Ｗｅｂ 服務(wù)組合優(yōu)化

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

關(guān)鍵詞：改進蟻群算法;Web 服務(wù)組合優(yōu)化;動態(tài)服務(wù)組合;L-IACO 算法

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

１ 引言

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

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

２ 基于改進蟻群算法的Ｗｅｂ 服務(wù)組合優(yōu)化

２．１ 基本蟻群算法描述

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

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

２．２ Ｌ?Ｉ?ＡＣＯ 算法的設(shè)計與實現(xiàn)

２．２．１ Ｌ?Ｉ?ＡＣＯ 算法狀態(tài)轉(zhuǎn)移概率

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

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

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

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

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

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

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

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

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

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

３ 實驗

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

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

４ 結(jié)束語

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

參考文獻：

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

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

［３］ 陳宇鋒．改進蟻群算法在ＷＥＢ 服務(wù)中應(yīng)用與實現(xiàn)［Ｄ］．長沙：湖南大學，２０１９．

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

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

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

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

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

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

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

作者簡介：

裴毓（ １９８９—）， 碩士， 助理工程師， 研究方向： 計算機網(wǎng)絡(luò)。