李東星 陳 喆 錢雙洋 焦 揚(yáng)

(解放軍信息工程大學(xué) 河南 鄭州 450004)

改進(jìn)蟻群算法及其在云服務(wù)組合優(yōu)化中的應(yīng)用研究

李東星 陳 喆 錢雙洋 焦 揚(yáng)

(解放軍信息工程大學(xué) 河南 鄭州 450004)

針對(duì)服務(wù)組合過程中的動(dòng)態(tài)性、不穩(wěn)定性以及多種QoS屬性限制等問題，提出一個(gè)適應(yīng)服務(wù)組合的改進(jìn)蟻群算法WJ-I-ACO算法，包括基于聚類分析方法的改進(jìn)局部優(yōu)化算法和基于動(dòng)態(tài)差分的改進(jìn)全局優(yōu)化算法。通過MATLAB仿真實(shí)驗(yàn)設(shè)計(jì)，驗(yàn)證了算法的有效性和可行性；基于此，分析了云服務(wù)組合的優(yōu)化策略，給出了服務(wù)組合的路徑尋優(yōu)方法。

蟻群算法 云服務(wù) 優(yōu)化 WJ-I-ACO

0 引 言

在云服務(wù)組合中，當(dāng)服務(wù)組合模型生成后，為了給用戶提供最為適合的服務(wù)，需要將功能相同的多個(gè)云服務(wù)或組合云服務(wù)進(jìn)行動(dòng)態(tài)選擇提取，但在海量的云服務(wù)中，如何從中找出合適的服務(wù)來綁定到組合服務(wù)模式中，選擇結(jié)果的好壞關(guān)系到服務(wù)組合的結(jié)果是否滿足用戶的需求。按照選擇的依據(jù)可以將服務(wù)選擇分為：基于功能需求的服務(wù)選擇和基于QoS的服務(wù)選擇?；诠δ艿姆?wù)選擇是根據(jù)功能描述從服務(wù)注冊(cè)中心選擇出具有某種功能的服務(wù)。這種服務(wù)選擇只能選擇出在功能上滿足用戶需求的服務(wù)，但是在實(shí)際應(yīng)用中，用戶的需求不僅限于得到滿足某種功能的服務(wù)，還需要考慮服務(wù)所需的費(fèi)用、響應(yīng)時(shí)間、是否可靠等，因此服務(wù)質(zhì)量被引入到了服務(wù)選擇中，即基于QoS的服務(wù)選擇?；赒oS的服務(wù)選擇從服務(wù)注冊(cè)中心中選擇功能上滿足用戶需求且服務(wù)質(zhì)量在整體上滿足QoS要求的服務(wù)。

蟻群算法不僅可以應(yīng)用到網(wǎng)絡(luò)服務(wù)軟件測(cè)試和參數(shù)的優(yōu)化問題上，還可以應(yīng)用到TSP問題、測(cè)試集優(yōu)化、背包問題、人工智能、神經(jīng)網(wǎng)絡(luò)、信號(hào)傳輸?shù)纫幌盗袕?fù)雜問題中。但是，在實(shí)際的應(yīng)用過程中，我們發(fā)現(xiàn)蟻群算法還是有很多不足之處，例如收斂速度不快、停滯很頻繁等。隨著人們的研究，很多學(xué)者針對(duì)以上蟻群算法的缺點(diǎn)做出了不同的優(yōu)化和改進(jìn)方法，比如，針對(duì)客服停滯問題的缺點(diǎn)，Stutzle等人[1]提出了MMAS(Max-Min Ant System)算法，主要是通過局部更新信息素的方法來克服這一缺陷。另外，針對(duì)收斂速度慢的問題，黃翰等人[2]結(jié)合馬爾科夫的數(shù)學(xué)模型，給出估算收斂時(shí)間期望的理論算法。

張成文[3]提出了在優(yōu)化以前對(duì)存在的問題進(jìn)行編碼，然后在全部的組合路徑中選擇滿足用戶服務(wù)的服務(wù)方案，顯然，這個(gè)想法不符合實(shí)際需求，因?yàn)樗麤]有考慮存在的動(dòng)態(tài)性問題。Zeng等人[4]雖然考慮到了在服務(wù)選擇中用戶QoS屬性值的動(dòng)態(tài)變化，提出了用于服務(wù)指標(biāo)感知的中間件，但是他們忽略了服務(wù)的不可用性以及選擇流程中的一系列和動(dòng)態(tài)相關(guān)的問題。倪晚成等人[5]用經(jīng)典的最短路徑算法進(jìn)行服務(wù)選擇，但是他們沒有考慮到顯示狀態(tài)中復(fù)雜的服務(wù)狀態(tài)。

介于上述原因，本文針對(duì)服務(wù)組合過程中的動(dòng)態(tài)性、不穩(wěn)定性以及多種QoS屬性限制等問題，提出一個(gè)適應(yīng)服務(wù)組合的改進(jìn)蟻群算法WJ-I-ACO算法， WJ-I-ACO算法包括局部優(yōu)化算法和全局優(yōu)化算法兩部分，局部優(yōu)化算法利用聚類分析的方法將服務(wù)屬性相同或相近的服務(wù)進(jìn)行類聚，減少蟻群算法的搜尋節(jié)點(diǎn)，實(shí)現(xiàn)算法的局部優(yōu)化。全局優(yōu)化算法利用兩條路徑的動(dòng)態(tài)差分平方統(tǒng)計(jì)量將相近的路徑進(jìn)行合并，實(shí)現(xiàn)蟻群算法的全局優(yōu)化，兩種優(yōu)化使WJ-I-ACO算法能夠適應(yīng)服務(wù)組合優(yōu)化過程中發(fā)生的服務(wù)無效，以及自適應(yīng)服務(wù)中QoS變化等情況。

1 改進(jìn)蟻群算法的設(shè)計(jì)與實(shí)現(xiàn)

1.1 經(jīng)典蟻群算法描述

蟻群算法ACO又被稱為螞蟻算法，這是一種基于在圖中尋找優(yōu)化路徑的機(jī)率型算法，同樣它也是一種群集智能算法，由意大利學(xué)者M(jìn)arco Dorigo于1992年最先提出。該算法的靈感來源于現(xiàn)實(shí)生活中螞蟻的覓食過程。在螞蟻尋找食物之前，沒有食物所在位置的任何信息，所以剛開始螞蟻都處于一種無規(guī)律的尋找狀態(tài)。一旦有螞蟻尋找到食物之后，這只螞蟻會(huì)向環(huán)境中釋放出一種具有揮發(fā)性的分泌物Pheromone(稱為信息素，該物質(zhì)會(huì)隨著時(shí)間慢慢揮發(fā)消失，其濃度大小可以表示路徑的遠(yuǎn)近)。根據(jù)這種分泌物，其他的螞蟻也會(huì)找到食物，這樣信息就會(huì)擴(kuò)散出去，使越來越多的螞蟻尋找到食物，同時(shí)在食物處產(chǎn)生更多的信息素，表現(xiàn)出一種信息素的正反饋現(xiàn)象。

螞蟻在路徑的選擇過程中，可能有的螞蟻并沒有重復(fù)其他螞蟻?zhàn)哌^的路徑，它們會(huì)另辟“蹊徑”。即周圍不存在信息素促使它選擇某條路徑，此時(shí)的螞蟻就會(huì)沿著原來的運(yùn)動(dòng)方向隨機(jī)挑選一條路徑繼續(xù)前進(jìn)。為了防止出現(xiàn)在原地打轉(zhuǎn)的情況，螞蟻會(huì)記錄并盡量避開剛走過的點(diǎn)。由于信息素會(huì)隨著時(shí)間逐漸揮發(fā)，因此路徑上信息素的多少可以表示該路徑的長短，即路徑越短，信息素就越多。螞蟻在前進(jìn)過程中，若感知到附近存在信息素，則會(huì)向信息素較大的方向前進(jìn)，直至最后找到食物。因此，若某路徑距離食物較短，這條路上的信息素就會(huì)相對(duì)較高，使螞蟻聚集在一起收斂到最短路徑上形成一種正反饋機(jī)制。具體過程如圖1所示。

圖1 服務(wù)自動(dòng)組合實(shí)現(xiàn)框架

圖1(a)中，A代表蟻穴，B代表覓食區(qū)，算法中的“螞蟻”可以經(jīng)由ACEDB和ACFDB兩條路徑往返于蟻穴和覓食區(qū)，有LACEDB=2LACFDB。先假設(shè)每個(gè)單位時(shí)間內(nèi)都有90只螞蟻從蟻穴出發(fā)經(jīng)由路徑ACEDB或ACFDB前往覓食區(qū)進(jìn)行覓食，同時(shí)有90只螞蟻從覓食區(qū)返回。單位時(shí)間內(nèi)螞蟻的移動(dòng)距離相同，并釋放等量的信息素，信息素會(huì)在(t,t+1)的時(shí)間內(nèi)揮發(fā)消失。

在某一時(shí)刻，如圖1(b)所示，C和D處各有90只螞蟻，由于兩條路徑上初始信息素均為0，所有螞蟻將隨機(jī)選擇路徑，根據(jù)概率各有45只螞蟻選擇了路徑CE、DE、DF和CF繼續(xù)前進(jìn)。

圖1(c)表示經(jīng)過一個(gè)單位時(shí)間后，即T=1時(shí)的情況，根據(jù)假設(shè)有90只新的螞蟻在C處和D處出現(xiàn)，此時(shí)路徑DE和CE在上一個(gè)單位時(shí)間內(nèi)各走過了45只螞蟻，釋放了45個(gè)單位量的信息素，而路徑DF和CF的長度是DE和CE的一半，共有90只螞蟻?zhàn)哌^，釋放了90個(gè)單位的信息素。因此此時(shí)90只新的螞蟻按照概率，選擇路徑DF和CF的螞蟻會(huì)有60只，選擇路徑DE和CE的螞蟻會(huì)有30只。隨著時(shí)間不斷增大，所有螞蟻都將選擇路徑ACFDB。

1.2 組合云服務(wù)優(yōu)化算法設(shè)計(jì)

智能優(yōu)化算法的實(shí)現(xiàn)就是直接面向問題建立優(yōu)化模型，這樣我們可以根據(jù)其無關(guān)特性給予方便的求解。隨著解空間的增加，智能優(yōu)化算法優(yōu)于經(jīng)典的優(yōu)化算法，因此，它比經(jīng)典優(yōu)化算法更加具有普遍適用性，目前存在以下三種優(yōu)化策略：

① 局部策略：是將每一個(gè)子問題都求得滿足用戶需求的最優(yōu)解，從而形成滿足用戶需求的最優(yōu)組合服務(wù)，它適用于存在局部QoS約束的情況下。在時(shí)間性能等方面，局部策略相比較其他策略來說是擁有很好的性能，但是若在處理全局QoS需求方面仍存在著很大的缺陷。

② 全局策略：全局策略相比較局部策略來說，它是站在整體的服務(wù)質(zhì)量上來說的，它根據(jù)服務(wù)對(duì)整體服務(wù)水平的貢獻(xiàn)大小來選擇服務(wù)，它著重考慮全局的質(zhì)量，用以滿足用戶對(duì)服務(wù)組合的需求。傳統(tǒng)的全局策略由于在任務(wù)的分解和服務(wù)發(fā)現(xiàn)與匹配的過程中實(shí)施面向單任務(wù)的服務(wù)組合，不能夠保證用戶需求的QoS指標(biāo)全部被滿足。在傳統(tǒng)全局優(yōu)化策略改進(jìn)的基礎(chǔ)上，另外加上了一個(gè)QoS協(xié)商約束機(jī)制，這樣就可以和全局策略配合使用，共同尋找可行方案。

③ 混合策略：混合策略就是在上述兩種策略的基礎(chǔ)上尋求一種平衡。它的主要設(shè)計(jì)辦法簡單敘述如下，首先將全局的服務(wù)約束分成幾個(gè)面向各個(gè)子問題的QoS約束；其次在各個(gè)子問題中局部約束的前提下，實(shí)現(xiàn)分布式的組合和優(yōu)化過程?；旌喜呗钥此菩阅芴嵘瞬簧伲撬匀徊荒軘[脫在傳統(tǒng)全局策略下組合和優(yōu)化所面臨的缺點(diǎn)。

在云服務(wù)組合中，當(dāng)服務(wù)組合模型生成后，為了給用戶提供最為適合的服務(wù)，需要將功能相同的多個(gè)云服務(wù)或組合云服務(wù)進(jìn)行動(dòng)態(tài)選擇提取，但在海量的云服務(wù)中，如何從中找出合適的服務(wù)來綁定到組合服務(wù)模式中，選擇結(jié)果的好壞關(guān)系到用戶使用的滿意程度。

因此，如何建立一個(gè)合理的質(zhì)量評(píng)價(jià)模型和使用何種高效算法可以在最短的時(shí)間內(nèi)提供最優(yōu)的服務(wù)就成為服務(wù)選擇方法的有效性動(dòng)態(tài)服務(wù)組合中急需解決的問題。這個(gè)動(dòng)態(tài)的選擇提取本質(zhì)上就是組合云服務(wù)的優(yōu)化，因此可將其歸結(jié)為服務(wù)組合優(yōu)化問題。

服務(wù)組合優(yōu)化問題需要系統(tǒng)地考慮QoS屬性約束，假設(shè)單一服務(wù)具有個(gè)QoS屬性 ，對(duì)于每個(gè)QoS屬性的服務(wù)相應(yīng)的限定值 ，則各個(gè)QoS屬性滿足相應(yīng)的約束，服務(wù)組合優(yōu)化是在滿足這些相應(yīng)約束條件下，查找QoS總值最高的服務(wù)。與此同時(shí)我們也應(yīng)該注意到各個(gè)QoS之間也存在著差異，比如數(shù)量級(jí)不同。如果QoS屬性的值是成比例的服務(wù)質(zhì)量的服務(wù)，較高的值表示較高的QoS，如帶寬，一些服務(wù)質(zhì)量屬性的服務(wù)是成反比例的，比如服務(wù)響應(yīng)時(shí)間。因此簡單地加總不能反映真實(shí)服務(wù)的QoS，該問題的本質(zhì)就是要解決單個(gè)服務(wù)選擇問題，即局部優(yōu)化問題。

在服務(wù)組合選擇系統(tǒng)中，通過對(duì)多個(gè)單一服務(wù)進(jìn)行選擇來組合成一個(gè)復(fù)合服務(wù)，從而獲得QoS更優(yōu)的組合服務(wù)。單一服務(wù)的最優(yōu)并不能保證組合服務(wù)的最優(yōu)，因此通過局部組合優(yōu)化后還需進(jìn)行全局優(yōu)化。

目前的服務(wù)組合方法都是伴隨動(dòng)態(tài)服務(wù)組合過程而動(dòng)態(tài)生成的，其過程可以用一個(gè)有向圖直觀表述其結(jié)構(gòu)，如圖2所示。

圖2 動(dòng)態(tài)服務(wù)組合方法簡單結(jié)構(gòu)圖

這里I表示輸入接口，O表示輸出接口，WSi(i=1,2,…)表示服務(wù)，WSi與WSj之間連線弧表示W(wǎng)Si的輸出接口與WSi的輸入接口匹配。

圖2是較為簡單的示例圖，包含服務(wù)節(jié)點(diǎn)和服務(wù)邊，圖中非常容易找出最優(yōu)的組合路徑。但在復(fù)雜度較高的服務(wù)組合系統(tǒng)中，節(jié)點(diǎn)和邊也相應(yīng)較多，優(yōu)化過程的復(fù)雜性也隨之提升。因此，我們可以通過網(wǎng)狀圖形路徑尋優(yōu)的方法來解決服務(wù)組合優(yōu)化問題。

定義1 服務(wù)組合有許多特性，其中包括順序性、并發(fā)性等。順序性指的是所有任務(wù)序列根據(jù)任務(wù)的執(zhí)行順序依次執(zhí)行，這樣的順序就可以用單一路徑圖來表示；并發(fā)性指的是多個(gè)服務(wù)同時(shí)執(zhí)行，不能用單一條路徑表示，這種情況不適用于優(yōu)化算法的使用，所以就需要把并行服務(wù)的先后順序在邏輯上轉(zhuǎn)換為順序執(zhí)行，即對(duì)服務(wù)進(jìn)行串行處理。這種轉(zhuǎn)換方式即利于優(yōu)化算法的運(yùn)行也不會(huì)影響實(shí)際的服務(wù)組合流程。

定義2 服務(wù)組合圖的原點(diǎn)和終點(diǎn)分別表示服務(wù)輸入，是動(dòng)態(tài)生成的單向連接圖。除了原點(diǎn)和終點(diǎn)不存在其他孤立點(diǎn)和懸點(diǎn)，所有節(jié)點(diǎn)的入度與出度均大于等于1，而且沒有循環(huán)。至少有一個(gè)從原點(diǎn)到終點(diǎn)的路徑。

在服務(wù)組合模擬圖中每段弧表示一個(gè)抽象的服務(wù)(相同功能的同種類型的服務(wù)，作為候選服務(wù)的具體示例并未在圖中給出)?；趩蝹€(gè)服務(wù)組合的QoS優(yōu)化，可以根據(jù)QoS的服務(wù)組合優(yōu)化的總和來進(jìn)行。服務(wù)組合模擬圖如圖3所示。

圖3 服務(wù)組合模擬圖

這里Si(i=1,2,…)表示不同的服務(wù)，Qi(i=1,2,…)表示不同的QoS屬性。根據(jù)上圖所示，服務(wù)組合優(yōu)化問題就是在動(dòng)態(tài)服務(wù)組合圖中尋找最短路徑的問題，將基于蟻群算法來解決該問題。蟻群算法其本身存在著收斂速度慢，易于停滯等缺陷，無法解決組合服務(wù)中多種QoS屬性約束的問題；并且當(dāng)循環(huán)次數(shù)逐漸增加后，信息素很容易聚集在少數(shù)幾條路徑上，使得易出現(xiàn)循環(huán)停滯、早熟等問題，從而得出的最終解決方案是一個(gè)局部最優(yōu)方案。針對(duì)這些問題，下面將從局部和全局兩個(gè)方面綜合考慮給出一個(gè)改進(jìn)的蟻群算法，為描述方便，在下文中表述為WJ-I-ACO算法。

1.3WJ-I-ACO算法狀態(tài)轉(zhuǎn)移概率

蟻群算法具有一定選擇服務(wù)比較優(yōu)良的概率，后來越來越多的螞蟻通過正反饋機(jī)制選擇更好的服務(wù)，最后發(fā)現(xiàn)在全域范圍內(nèi)最好的服務(wù)。因此，必須首先給出WJ-I-ACO算法狀態(tài)轉(zhuǎn)移概率的計(jì)算問題。不失一般性，設(shè)M為蟻群中螞蟻的數(shù)目，N代表服務(wù)組合圖的節(jié)點(diǎn)的數(shù)目，τij(t)為狀態(tài)轉(zhuǎn)移概率，我們可以分為兩種情況來討論狀態(tài)轉(zhuǎn)移概率τij(t)的計(jì)算方法。

1) 對(duì)單個(gè)QoS進(jìn)行服務(wù)組合優(yōu)化

當(dāng)服務(wù)組合只考慮單一的QoS時(shí)，WJ-I-ACO算法就退變成為了基本蟻群算法，因而τij(t)的計(jì)算公式與基本蟻群算法相同。通過單一累加即可得到。

2) 對(duì)QoS總和進(jìn)行服務(wù)組合優(yōu)化

當(dāng)考慮進(jìn)行QoS總和來計(jì)算服務(wù)組合時(shí)，則需要將多種QoS屬性值帶入WJ-I-ACO算法求解τij(t)。

設(shè)s為路徑(i,j)的一個(gè)服務(wù)，s共包含n個(gè)QoS屬性Q1,Q2,…,Qn，這些屬性對(duì)應(yīng)的量化值轉(zhuǎn)換函數(shù)為Q1(s),Q2(s),…,Qn(s)，則WJ-I-ACO算法中服務(wù)s的第r個(gè)QoS屬性對(duì)應(yīng)的信息素的計(jì)算公式為：

其中，w1,w2,…,wn為相應(yīng)的權(quán)值。

綜合以上兩個(gè)計(jì)算公式得到τij(t)的計(jì)算式，下面進(jìn)一步給出WJ-I-ACO算法的狀態(tài)轉(zhuǎn)移概率計(jì)算公式：

1.4WJ-I-ACO算法的設(shè)計(jì)與實(shí)現(xiàn)

針對(duì)蟻群算法收斂速度慢且易于陷入局部最優(yōu)解等缺點(diǎn)，將通過分析組合云服務(wù)QoS優(yōu)化的，給出WJ-I-ACO算法設(shè)計(jì)依據(jù)的尋優(yōu)更新方法。

一方面，當(dāng)利用螞蟻算法進(jìn)行組合云服務(wù)QoS尋優(yōu)時(shí)，沒有任何可以利用的先驗(yàn)信息可以使用，但當(dāng)進(jìn)行過多輪尋優(yōu)之后，由貝葉斯判決可知，可以利用已查找到的路徑信息，重新評(píng)估之前的路徑，更新獲得更優(yōu)的路徑。由此可以得到WJ-I-ACO算法尋優(yōu)更新方法1。

方法1 經(jīng)過多輪螞蟻尋優(yōu)后，比較每條路徑中各節(jié)點(diǎn)的信息素濃度的大小，針對(duì)不同路徑中服務(wù)相同的節(jié)點(diǎn)，重新評(píng)估之前所有路徑，以信息素濃度大的節(jié)點(diǎn)重新構(gòu)造新的路徑，使該路徑中濃度達(dá)到最大(表示QoS總和最大)，從而更新出新的最優(yōu)路徑。

另一方面，當(dāng)利用螞蟻算法進(jìn)行組合云服務(wù)QoS尋優(yōu)時(shí)，如果有一只螞蟻優(yōu)化過程中選擇了全局最優(yōu)路徑，只要能夠采取有效的方法證明該路徑就是要找的最優(yōu)路徑，WJ-I-ACO算法就可以使算法找到全局最優(yōu)解?？梢酝ㄟ^建立最優(yōu)列表方法來解決該問題，由此可以得到WJ-I-ACO算法尋優(yōu)更新方法2。

方法2 設(shè)定最優(yōu)路徑列表L，把每一輪蟻群尋優(yōu)后的濃度中最大的(對(duì)應(yīng)的QoS)路徑進(jìn)行比較，按照最優(yōu)順序保存l個(gè)最優(yōu)路徑(濃度最大)到路徑L中，濃度最大的排在第一位，以后以此類推。當(dāng)算法達(dá)到循環(huán)的最大次數(shù)后，所排列的第一個(gè)元素與列表中每個(gè)路徑的最高濃度進(jìn)行比較，如果得到的結(jié)果相同，那么我們就可以根據(jù)該算法求得全局最優(yōu)解，服務(wù)組合最優(yōu)解即為濃度最高的路徑；如果不同，則表示算法收斂于局部最優(yōu)解。

方法2是一個(gè)簡單而有效的解決方案，但是其中存在著一個(gè)問題，就是當(dāng)螞蟻在選擇路徑的時(shí)候沒有選擇最優(yōu)的路徑，這時(shí)我們依據(jù)該算法就得不到最優(yōu)解。為避免此類情況，通過對(duì)算法進(jìn)行動(dòng)態(tài)跟蹤，判斷算法是否收斂于局部最優(yōu)解，如果是，則忽略掉此次螞蟻選路的概率，使得算法趨向于最優(yōu)解的概率增加。

這里盡管給出了WJ-I-ACO算法設(shè)計(jì)依據(jù)的尋優(yōu)更新方法，但也只是從宏觀上給出了解決方案，對(duì)于算法在實(shí)際尋優(yōu)過程中具體如何操作尚沒有解決，下面從局部尋優(yōu)優(yōu)化和全局尋優(yōu)兩個(gè)方面分析給出WJ-I-ACO算法的具體方案。

1)WJ-I-ACO算法局部優(yōu)化算法

上述分析表明一個(gè)抽象服務(wù)有多個(gè)候選服務(wù)實(shí)例，這也確定了兩節(jié)點(diǎn)之間有多個(gè)候選服務(wù)，如圖4所示。如果所有路徑都進(jìn)行優(yōu)化，那么優(yōu)化計(jì)算規(guī)模將是非常巨大的，組合優(yōu)化問題隨著問題規(guī)模的增加而成倍增加。

圖4 多候選服務(wù)結(jié)構(gòu)圖

事實(shí)上，如果能把大規(guī)模的優(yōu)化問題分解或減成小規(guī)模的優(yōu)化問題，盡可能縮小問題的規(guī)模，那么將大大提高算法的尋優(yōu)能力。

WJ-I-ACO算法局部優(yōu)化算法包含兩部分：預(yù)計(jì)算部分和隨機(jī)選取尋優(yōu)部分。預(yù)計(jì)算部分將服務(wù)屬性相同或相近的服務(wù)進(jìn)行聚類，將這些服務(wù)歸作一個(gè)服務(wù)節(jié)點(diǎn)不再單獨(dú)區(qū)分。此外，也可以在預(yù)計(jì)算中設(shè)定限定條件將不滿足的服務(wù)從尋優(yōu)列表中刪除，達(dá)到減少搜索量的目的。

顯然，當(dāng)兩個(gè)服務(wù)s與s′相同或相近的時(shí)候，C(s,s′)的值將趨向于零，以此來判斷兩個(gè)服務(wù)的相近程度。但這樣的判定方法也存在如下問題：當(dāng)服務(wù)s與s′的匹配指標(biāo)趨向于零，而且服務(wù)s′與s″的匹配指標(biāo)也趨向于零。但s′與s″的匹配指標(biāo)確有可能并不趨向于零，這時(shí)候就難以將這三個(gè)服務(wù)歸為一個(gè)分類。針對(duì)這種情況，采取將服務(wù)s與s′歸為一類，將服務(wù)s″作為待定類，當(dāng)所有屬性近似的服務(wù)的匹配指標(biāo)計(jì)算后，如果服務(wù)s″和某一類服務(wù)中的大多數(shù)服務(wù)的匹配指標(biāo)都趨向于零，則將其歸為其同類。

此外，考慮到動(dòng)態(tài)服務(wù)組合和服務(wù)質(zhì)量存在不確定因素，因此我們可以將狀態(tài)轉(zhuǎn)移概率的路徑選取策略做如下調(diào)整：首先我們不通過計(jì)算概率值來選擇服務(wù)，而是隨機(jī)選擇服務(wù)，然后利用狀態(tài)轉(zhuǎn)移概率計(jì)算作為過濾服務(wù)，把那些不能夠滿足用戶需求的服務(wù)及QoS值低的服務(wù)去掉(對(duì)應(yīng)于濃度低的弧)，通過這個(gè)辦法我們可以縮小服務(wù)選擇空間，提高運(yùn)算效率。具體地，WJ-I-ACO局部優(yōu)化算法由算法1給出。

設(shè)Ncmax為最大循環(huán)次數(shù)，M為螞蟻個(gè)數(shù)，Lij為最優(yōu)服務(wù)列表，下標(biāo)i，j對(duì)應(yīng)表示本次服務(wù)選擇對(duì)應(yīng)的服務(wù)組合圖中的抽象服務(wù)Sij，初始化時(shí)間片t=0，循環(huán)控制變量Nc=0，螞蟻循環(huán)變量k=0。

算法1WJ-I-ACO局部優(yōu)化算法

Step1 匹配指標(biāo)計(jì)算

根據(jù)服務(wù)組合中各服務(wù)的屬性集合的不同，計(jì)算其匹配指標(biāo)，其計(jì)算公式如下：

根據(jù)C(s,s′)的不同對(duì)服務(wù)進(jìn)行分類，將屬性集合看作路徑節(jié)點(diǎn)。

Step2 服務(wù)隨機(jī)選取

將螞蟻所在節(jié)點(diǎn)對(duì)應(yīng)服務(wù)的QoS屬性Q1,Q2,…,Qn與其限定值q1,q2,…,qn進(jìn)行比較，若達(dá)到要求則計(jì)算該服務(wù)的QoS總和，否則忽略該服務(wù)，并采用更新方法1對(duì)最優(yōu)服務(wù)列表Lij中服務(wù)更新。

Step3循環(huán)迭代

如果Nc

Step4 轉(zhuǎn)移概率計(jì)算

如服務(wù)存在，則在服務(wù)列表Lij中選取最優(yōu)服務(wù)計(jì)算其轉(zhuǎn)移概率，選取其中轉(zhuǎn)移概率最大的服務(wù)計(jì)算值，即是我們所選的最優(yōu)服務(wù)。如服務(wù)列表Lij為空，則表示本輪服務(wù)選擇失敗。

Step5 服務(wù)刪除算法

通過迭代計(jì)算，選取最優(yōu)服務(wù)后，刪除其他備選服務(wù)。

不考慮第一步預(yù)計(jì)算部分，該算法的復(fù)雜度是O(Ncmax×M)，其中Ncmax為最大循環(huán)次數(shù)，M為螞蟻數(shù)量。該算法的最大復(fù)雜度為O(N×M)，其中N為候選服務(wù)個(gè)數(shù)。

2)WJ-I-ACO算法全局優(yōu)化算法

通過對(duì)每個(gè)抽象服務(wù)進(jìn)行局部優(yōu)化后，再在全局內(nèi)進(jìn)行尋優(yōu)的組合服務(wù)。全局優(yōu)化算法首先通過一定的搜索后建立尋優(yōu)路徑列表，從歷史經(jīng)驗(yàn)條件出發(fā)，以歷史經(jīng)驗(yàn)最優(yōu)路徑為標(biāo)準(zhǔn)，通過動(dòng)態(tài)求差的方法，對(duì)建立的路徑列表進(jìn)行篩選，縮小最優(yōu)路徑搜索空間，最后再搜索空間中濃度最高的路徑進(jìn)而得到最優(yōu)路徑。

針對(duì)全局搜索的情況，當(dāng)所有的螞蟻選擇的路徑都不是最優(yōu)的，我們可以采取將歷史經(jīng)驗(yàn)最優(yōu)路徑設(shè)為最優(yōu)路徑，進(jìn)行全局最有搜索。

設(shè)通過搜尋獲得的按大小順序保存的最優(yōu)路徑列表為L={lQ1,lQ2,…}，歷史經(jīng)驗(yàn)最優(yōu)路徑為lQ，把L={lQ1,lQ2,…}路徑與路徑為lQ進(jìn)行如下動(dòng)態(tài)差值運(yùn)算，這里記為D(lQi,lQ)。

顯然，當(dāng)lQ與lQi越接近，D(lQi,lQ)的值將越小，以此來判斷兩個(gè)路徑的接近程度。搜索完所有最優(yōu)路徑列表L={lQ1,lQ2,…}中的路徑，只保留列表中與lQ接近的路徑，以此完成對(duì)路徑列表的優(yōu)化。為了提高算法運(yùn)行的效率，縮小服務(wù)組合的選擇空間，我們過濾掉不滿足要求的服務(wù)及QoS值低的服務(wù)(對(duì)應(yīng)于濃度低的弧)，具體WJ-I-ACO全局優(yōu)化算法由算法2給出。

設(shè)定最大循環(huán)次數(shù)Ncmax，螞蟻個(gè)數(shù)M，初始化時(shí)間片t=0，循環(huán)控制變量Nc=0，螞蟻循環(huán)變量k=0，最優(yōu)組合服務(wù)列表L。將螞蟻放置于服務(wù)組合圖中的初始節(jié)點(diǎn)，令組合圖中每條弧對(duì)應(yīng)的各種QoS濃度值τij(t)為由WJ-I-ACO局部優(yōu)化算法所選擇服務(wù)對(duì)應(yīng)的濃度值，如果沒有相應(yīng)的濃度值時(shí)，可令服務(wù)對(duì)應(yīng)弧上的τij(t)=const，其中const為常數(shù)，歷史經(jīng)驗(yàn)最優(yōu)路徑為lQ。

算法2WJ-I-ACO全局優(yōu)化算法

Step1 隨著循環(huán)輪數(shù)的不斷增加，即Nc=Nc+1，若出現(xiàn)Nc>Ncmax的情況，則跳出循環(huán)到Step7。

Step2 隨著螞蟻總數(shù)的不斷增多，即k=k+1，若出現(xiàn)k>M的情況，則跳出循環(huán)到Step6。

Step3 按照轉(zhuǎn)移概率計(jì)算公式，求出螞蟻的所狀態(tài)轉(zhuǎn)移，即選擇了當(dāng)前兩節(jié)點(diǎn)間對(duì)應(yīng)的服務(wù)。如果選取服務(wù)的各QoSQ1,Q2,…,Qn的屬性值過低或者服務(wù)不可用，則刪除這個(gè)服務(wù)，同時(shí)在剩余節(jié)點(diǎn)中選擇下一節(jié)點(diǎn)。

Step4 如果螞蟻停止尋找下一節(jié)點(diǎn)且對(duì)應(yīng)于組合圖終點(diǎn)，則停止尋找服務(wù)，并將該節(jié)點(diǎn)路徑保存到列表L中，跳轉(zhuǎn)到Step5，否則跳轉(zhuǎn)到Step3。

Step5 根據(jù)已選出的節(jié)點(diǎn)路徑，得出其對(duì)應(yīng)的服務(wù)組合，計(jì)算服務(wù)的各個(gè)子服務(wù)新增的加總。若螞蟻總數(shù)k

Step6 根據(jù)L中最大的服務(wù)組合將其置于序列L的首位，如果列表已滿，對(duì)表的路徑計(jì)算：

只保留D(lQi,lQ)值較小的路徑。

Step7 利用方法2，通過比較最優(yōu)路徑和最優(yōu)組合列表L中的服務(wù)，得到算法的最優(yōu)解即為最優(yōu)的組合服務(wù)。

2 MATLAB仿真分析

2.1 仿真實(shí)驗(yàn)設(shè)計(jì)

本節(jié)我們主要是通過對(duì)一個(gè)城市規(guī)劃的應(yīng)用實(shí)例為背景來驗(yàn)證WJ-I-ACO算法的可行性和有效性。城市規(guī)劃應(yīng)用是通過將地理上分布的不同的空間數(shù)據(jù)資源和空間信息資源進(jìn)行整合來自動(dòng)地處理城市規(guī)劃部門的問題。不同的數(shù)據(jù)和信息資源包括眾多的服務(wù)類，如何從這些服務(wù)類中按具體需求選出最優(yōu)服務(wù)組合，從而為城市規(guī)劃部門的時(shí)間預(yù)算或經(jīng)費(fèi)預(yù)算提供有效的理論支持。

城市規(guī)劃服務(wù)流程的具體的執(zhí)行過程如圖5所示。流程包含六個(gè)不同類型的服務(wù)群，每個(gè)服務(wù)群中含有不同數(shù)量、不同QoS屬性的基礎(chǔ)服務(wù)，服務(wù)群的建立和維護(hù)過程由指定的服務(wù)組合流程實(shí)現(xiàn)和管理框架來完成。其中，t1：請(qǐng)求解析服務(wù)；t2：地理編碼服務(wù)；t3：行政區(qū)劃分服務(wù)；t4：影像集成服務(wù)；t5：道路鋪設(shè)數(shù)據(jù)服務(wù)；t6：數(shù)據(jù)集成服務(wù)。工作流程可敘述如下：接到規(guī)劃部門的請(qǐng)求，對(duì)規(guī)劃過程進(jìn)行解析處理；將指點(diǎn)的規(guī)劃區(qū)域通過空間定點(diǎn)描述轉(zhuǎn)換成地理坐標(biāo)；按照具體規(guī)劃要求通過坐標(biāo)劃分行政管理區(qū)；對(duì)區(qū)域內(nèi)進(jìn)行攝像集成，形成圖片描述展示直觀信息；對(duì)主要的道路進(jìn)行規(guī)劃分析，通過最后所有數(shù)據(jù)的集成使得規(guī)劃部門對(duì)周邊地理環(huán)境信息做出直觀、精確的判斷，然后作出科學(xué)的決策。

圖5 城市規(guī)劃流程圖

改進(jìn)蟻群算法WJ-I-ACO用MATLAB實(shí)現(xiàn)，其中各個(gè)服務(wù)群中服務(wù)的QoS參數(shù)采用隨機(jī)方法在一定范圍內(nèi)生成。

執(zhí)行過程描述：

算法主要實(shí)現(xiàn)如下：

執(zhí)行過程描述：

//為每個(gè)服務(wù)添加QoS屬性綜合值

If(E≠?)

{for(eacheinE)

{for(eachserciceinservice(e))

{if(service-added==false)

//false表示服務(wù)的QoS值還沒有添加;

{

character-value=F(service);

//添加QoS屬性值;

service-added=true;

}

}}}

//在途中標(biāo)注所有輸入節(jié)點(diǎn)；

for(eachsi1insi)

{if(tag(si1)==false)

{標(biāo)注節(jié)點(diǎn)si1;

tag(si1)=true;

}

elsecontinue;

}

//求出滿足用戶需求的所有最佳路徑;

for(eachsi1→si2inkq)

{if(si1不可達(dá)si2)

//沒有滿足這種要求的服務(wù);

buildingnewservice;

else{if(onlyonepathsatisfiedsi1→si2andmin(service(e)))

//有一條路徑滿足要求并求出路徑上所有邊標(biāo)識(shí)服務(wù)集

//合中服務(wù)性能最佳的服務(wù)

selectservicesonthispath;

else

利用WJ-I-ACO算法求出所有min(service(e)中的最短路徑

}

}

2.2 有效性的實(shí)驗(yàn)

在求解過程中，如果算法的每一次迭代時(shí)間過長將會(huì)造成具體問題求解速度慢的后果，即便算法能最后找到最優(yōu)解也無法滿足實(shí)際應(yīng)用，此時(shí)算法就是無效的。為了驗(yàn)證改進(jìn)蟻群算法WJ-I-ACO的有效性，我們?cè)O(shè)計(jì)了通過計(jì)算計(jì)算機(jī)CPU時(shí)間開銷的方法來測(cè)量算法運(yùn)行速度的實(shí)驗(yàn)。具體實(shí)驗(yàn)設(shè)計(jì)如下：首先將服務(wù)群規(guī)模設(shè)計(jì)了三種不同的類型，分別為5、10和20藉此來驗(yàn)證隨著服務(wù)群規(guī)模的增加對(duì)算法運(yùn)行時(shí)間的影響。其次，為了方便測(cè)量，限定算法的迭代次數(shù)，本實(shí)驗(yàn)中將最大迭代次數(shù)限定為100、200、300和400四種情況，為了避免計(jì)算機(jī)穩(wěn)定性對(duì)算法帶來的影響，對(duì)每種情況取10次平均值。由圖6可以看出，WJ-I-ACO算法的有效性是非常明顯的，因?yàn)榉?wù)群規(guī)模的倍數(shù)增加并沒有造成算法消耗時(shí)間的成倍增加，在服務(wù)群規(guī)模為10的時(shí)候，算法循環(huán)400次僅需要12秒，這個(gè)運(yùn)行時(shí)間也能滿足大部分用戶在服務(wù)組合時(shí)對(duì)時(shí)間要求的需要。

圖6 WJ-I-ACO平均執(zhí)行時(shí)間

2.3 可行性的實(shí)驗(yàn)

在驗(yàn)證了算法的有效性之后，還需對(duì)算法進(jìn)行可行性實(shí)驗(yàn)，因?yàn)橐粋€(gè)好的算法除了速度快之外，還應(yīng)具有求解準(zhǔn)確、優(yōu)秀的特點(diǎn)，即能在一個(gè)限定的循環(huán)次數(shù)內(nèi)，較大概率地找到最優(yōu)解。為了驗(yàn)證采用WJ-I-ACO算法能夠找到QoS全局最優(yōu)服務(wù)鏈，我們做了以下實(shí)驗(yàn)。實(shí)驗(yàn)中采用的是窮舉法，即列出所有可執(zhí)行服務(wù)流程的最優(yōu)解，驗(yàn)證在這些解集中存在最優(yōu)結(jié)果的概率。為了實(shí)驗(yàn)驗(yàn)證方便，統(tǒng)計(jì)WJ-I-ACO算法循環(huán)200次的性能和開銷的全局最優(yōu)結(jié)果的百分率，如圖7所示，服務(wù)群規(guī)模在5、10、20三種情況下，WJ-I-ACO算法在經(jīng)過200次循環(huán)之后，性能和開銷指標(biāo)的最優(yōu)值概率都超過了百分之九十。特別是在服務(wù)群較小的時(shí)候，算法在循環(huán)200次之后完全可以得到最優(yōu)指標(biāo)值，因此WJ-I-ACO算法在解決實(shí)際問題中是可行的。

圖7 最優(yōu)解的比例

2.4 優(yōu)化策略分析

WJ-I-ACO算法先對(duì)每個(gè)抽象服務(wù)進(jìn)行局部最優(yōu)尋找后，然后再在全局內(nèi)尋找最優(yōu)的組合。首先通過一定的搜索后建立尋優(yōu)路徑列表，從歷史經(jīng)驗(yàn)條件出發(fā)，以歷史經(jīng)驗(yàn)最優(yōu)路徑為標(biāo)準(zhǔn)，通過動(dòng)態(tài)求差的方法，對(duì)建立的路徑列表進(jìn)行篩選，縮小最優(yōu)路徑搜索空間，最后再搜索空間中濃度最高的路徑進(jìn)而得到最優(yōu)路徑。

為了驗(yàn)證WJ-I-ACO局部優(yōu)化算法的時(shí)效性，將目前在實(shí)際應(yīng)用中經(jīng)典的局部優(yōu)化算法粒子群算法(PSO)和WJ-I-ACO算法比較。圖8 為在服務(wù)群規(guī)模分別為5、10、20的情況下，求得設(shè)定的一個(gè)特定解，算法PSO 與WJ-I-ACO花費(fèi)時(shí)間比較，這里的時(shí)間為PSO 與WJ-I-ACO分別運(yùn)行10次取平均。分析該圖我們可以得到：在服務(wù)群規(guī)模較小的時(shí)候，粒子群優(yōu)化算法尋找到某一局部最優(yōu)解的時(shí)間比WJ-I-ACO算法短，但是隨著服務(wù)群規(guī)模的增長，PSO算法花費(fèi)的時(shí)間呈幾何倍數(shù)增長。本實(shí)驗(yàn)中，在服務(wù)群規(guī)模等于5的時(shí)候，算法WJ-I-ACO開始比PSO求特定解的速度快，隨著服務(wù)群規(guī)模的持續(xù)增加，WJ-I-ACO算法的優(yōu)勢(shì)愈加明顯，尋優(yōu)能力更加突出。

為了驗(yàn)證WJ-I-ACO全局優(yōu)化算法求最全局優(yōu)解的能力，設(shè)計(jì)在大規(guī)模服務(wù)群的情況下的仿真實(shí)驗(yàn)。圖9所示的是在服務(wù)群規(guī)模為200，算法WJ-I-ACO和算法PSO的最優(yōu)解的分布情況。分析該圖可以得到，WJ-I-ACO算法的最優(yōu)解的性能和分布比算法PSO更加優(yōu)秀。WJ-I-ACO雖然提高了計(jì)算復(fù)雜性，但是通過該算法得到最優(yōu)解的性能和質(zhì)量好，PSO計(jì)算復(fù)雜性較低，但從圖可以看出，在服務(wù)群規(guī)模增加到一定程度的時(shí)候，PSO算法將陷入局部最優(yōu)，求得的解的性能和質(zhì)量差，甚至在服務(wù)群規(guī)模特別大的時(shí)候?qū)o法求得全局最優(yōu)解。

圖8 WJ-I-ACO和PSO的平均執(zhí)行時(shí)間

圖9 WJ-I-ACO和PSO的優(yōu)化解集

3 結(jié) 語

針對(duì)服務(wù)組合過程中的動(dòng)態(tài)性、不穩(wěn)定性以及多種QoS屬性限制等問題，提出一種優(yōu)化的及適應(yīng)服務(wù)組合的動(dòng)態(tài)聚合信息素更新蟻群算法WJ-I-ACO以適應(yīng)服務(wù)組合優(yōu)化過程中發(fā)生的服務(wù)無效以及服務(wù)中QoS變化等情況。在此基礎(chǔ)上，提出了一個(gè)以WJ-I-ACO算法為核心的云服務(wù)組合優(yōu)化方法，并對(duì)云服務(wù)組合進(jìn)行了動(dòng)態(tài)性設(shè)計(jì)。下一步我們準(zhǔn)備將語義網(wǎng)理論應(yīng)用到蟻群算法之中，實(shí)現(xiàn)優(yōu)化過程更高的智能化，并進(jìn)一步尋找制約蟻群算法收斂速度的深層次原因以及算法對(duì)數(shù)據(jù)敏感性的規(guī)律。

[1] Singh S,Chana I.Resource provisioning and scheduling in clouds:QoS perspective[J].Journal of Supercomputing,2016:1-35.

[2] 黃翰,郝志峰,吳春國,等.蟻群算法的收斂速度分析[J].計(jì)算機(jī)學(xué)報(bào),2007,30(8):1344-1353.

[3] 張成文,蘇森,陳俊亮.基于遺傳算法的QoS感知的Web服務(wù)選擇[J].計(jì)算機(jī)學(xué)報(bào),2006,29(7):1029-1037.

[4] Zeng Liangzhao,Boualen Benatallah.QoS-aware middle-ware for Web services composition[C].IEEE Transactions on Software Eengineering,2004,30(2):311-327.

[5] 倪晚成,劉連臣,吳澄,等.基于概念關(guān)聯(lián)程度的網(wǎng)格服務(wù)組合方法[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版,2007,47(10):1581-1585.

[6] Aloes A,et al.Web Services Business process Execution Language,Version2.0 OASIS Standard (April 2007)[S].http://docs.oasis-open.org/wsbpel/2.0/OS/wsbpel- v2.0-OS.html.

[7] Comi A,Fotia L,Messina F,et al.A Reputation-Based Approach to Improve QoS in Cloud Service Composition[C]//Enabling Technologies:Infrastructure for Collaborative Enterprises (WETICE),2015 IEEE 24th International Conference on.IEEE,2015:108-113.

[8]LiuS,WeiY,TangK,etal.QoS-awarelong-termbasedservicecompositionincloudcomputing[C]//EvolutionaryComputation(CEC),2015IEEECongresson.IEEE,2015.

[9]KazemAAP,PedramH,AbolhassaniH.BNQM:ABayesianNetworkbasedQoSModelforGridservicecomposition[J].ExpertSystemswithApplications,2015,42(20):6828-6843.

[10]JatothC,GangadharanGR.QoS-AwareWebServiceCompositionUsingQuantumInspiredParticleSwarmOptimization[M]//IntelligentDecisionTechnologies.SpringerInternationalPublishing,2015:255-265.

[11]ZhengH,FengY,TanJ.AfuzzyQoS-awareresourceserviceselectionconsideringdesignpreferenceincloudmanufacturingsystem[J].InternationalJournalofAdvancedManufacturingTechnology,2016:1-9.

IMPROVED ANT COLONY ALGORITHM AND ITS APPLICATION IN CLOUDSERVICE COMPOSITION OPTIMIZATION

Li Dongxing Chen Zhe Qian Shuangyang Jiao Yang

(PLAInformationEngineeringUniversity,Zhengzhou450004,Henan,China)

Aiming at the dynamic, instability, multiple QoS attribute restrictions and other issues in service composition process, we propose an optimized and service combination fitted dynamic aggregation pheromone updating ant colony algorithm (WJ-I-ACO) , including improved local optimization algorithm based on clustering analysis and improved global optimization algorithm based on dynamic differential. The effectiveness and feasibility of the algorithm are verified through MATLAB simulations. Based on this, we analyze the optimization strategy of cloud service composition and give the path optimization method for service composition.

Ant colony algorithm Cloud service Optimization WJ-I-ACO

2016-03-15。李東星，碩士生，主研領(lǐng)域：云計(jì)算及其可靠性。陳喆，副教授。錢雙洋，碩士生。焦揚(yáng)，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.03.003