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

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

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

中圖法分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A

１ 引言

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

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

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

２．１ 基本蟻群算法描述

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

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

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

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

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

２．２．２ Ｌ?Ｉ?ＡＣＯ 改進(jìn)蟻群算法

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

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

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

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

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

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

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

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

３ 實(shí)驗(yàn)

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

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

４ 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

作者簡(jiǎn)介：

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