李東星 陳 喆 錢雙洋 焦 揚

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

改進蟻群算法及其在云服務組合優(yōu)化中的應用研究

李東星 陳 喆 錢雙洋 焦 揚

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

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

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

0 引 言

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

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

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

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

1 改進蟻群算法的設計與實現(xiàn)

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

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

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

圖1 服務自動組合實現(xiàn)框架

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

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

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

1.2 組合云服務優(yōu)化算法設計

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

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

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

③ 混合策略：混合策略就是在上述兩種策略的基礎上尋求一種平衡。它的主要設計辦法簡單敘述如下，首先將全局的服務約束分成幾個面向各個子問題的QoS約束；其次在各個子問題中局部約束的前提下，實現(xiàn)分布式的組合和優(yōu)化過程。混合策略看似性能提升了不少，但是它仍然不能擺脫在傳統(tǒng)全局策略下組合和優(yōu)化所面臨的缺點。

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

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

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

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

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

圖2 動態(tài)服務組合方法簡單結構圖

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

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

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

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

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

圖3 服務組合模擬圖

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

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

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

1) 對單個QoS進行服務組合優(yōu)化

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

2) 對QoS總和進行服務組合優(yōu)化

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

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

其中，w1,w2,…,wn為相應的權值。

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

1.4WJ-I-ACO算法的設計與實現(xiàn)

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

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

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

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

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

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

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

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

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

圖4 多候選服務結構圖

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

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

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

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

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

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

Step1 匹配指標計算

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

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

Step2 服務隨機選取

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

Step3循環(huán)迭代

如果Nc

Step4 轉移概率計算

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

Step5 服務刪除算法

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

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

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

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

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

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

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

設定最大循環(huán)次數(shù)Ncmax，螞蟻個數(shù)M，初始化時間片t=0，循環(huán)控制變量Nc=0，螞蟻循環(huán)變量k=0，最優(yōu)組合服務列表L。將螞蟻放置于服務組合圖中的初始節(jié)點，令組合圖中每條弧對應的各種QoS濃度值τij(t)為由WJ-I-ACO局部優(yōu)化算法所選擇服務對應的濃度值，如果沒有相應的濃度值時，可令服務對應弧上的τij(t)=const，其中const為常數(shù)，歷史經(jīng)驗最優(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 按照轉移概率計算公式，求出螞蟻的所狀態(tài)轉移，即選擇了當前兩節(jié)點間對應的服務。如果選取服務的各QoSQ1,Q2,…,Qn的屬性值過低或者服務不可用，則刪除這個服務，同時在剩余節(jié)點中選擇下一節(jié)點。

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

Step5 根據(jù)已選出的節(jié)點路徑，得出其對應的服務組合，計算服務的各個子服務新增的加總。若螞蟻總數(shù)k

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

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

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

2 MATLAB仿真分析

2.1 仿真實驗設計

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

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

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

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

執(zhí)行過程描述：

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

執(zhí)行過程描述：

//為每個服務添加QoS屬性綜合值

If(E≠?)

{for(eacheinE)

{for(eachserciceinservice(e))

{if(service-added==false)

//false表示服務的QoS值還沒有添加;

{

character-value=F(service);

//添加QoS屬性值;

service-added=true;

}

}}}

//在途中標注所有輸入節(jié)點；

for(eachsi1insi)

{if(tag(si1)==false)

{標注節(jié)點si1;

tag(si1)=true;

}

elsecontinue;

}

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

for(eachsi1→si2inkq)

{if(si1不可達si2)

//沒有滿足這種要求的服務;

buildingnewservice;

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

//有一條路徑滿足要求并求出路徑上所有邊標識服務集

//合中服務性能最佳的服務

selectservicesonthispath;

else

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

}

}

2.2 有效性的實驗

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

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

2.3 可行性的實驗

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

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

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

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

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

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

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

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

3 結 語

針對服務組合過程中的動態(tài)性、不穩(wěn)定性以及多種QoS屬性限制等問題，提出一種優(yōu)化的及適應服務組合的動態(tài)聚合信息素更新蟻群算法WJ-I-ACO以適應服務組合優(yōu)化過程中發(fā)生的服務無效以及服務中QoS變化等情況。在此基礎上，提出了一個以WJ-I-ACO算法為核心的云服務組合優(yōu)化方法，并對云服務組合進行了動態(tài)性設計。下一步我們準備將語義網(wǎng)理論應用到蟻群算法之中，實現(xiàn)優(yōu)化過程更高的智能化，并進一步尋找制約蟻群算法收斂速度的深層次原因以及算法對數(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].計算機學報,2007,30(8):1344-1353.

[3] 張成文,蘇森,陳俊亮.基于遺傳算法的QoS感知的Web服務選擇[J].計算機學報,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] 倪晚成,劉連臣,吳澄,等.基于概念關聯(lián)程度的網(wǎng)格服務組合方法[J].清華大學學報:自然科學版,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。李東星，碩士生，主研領域：云計算及其可靠性。陳喆，副教授。錢雙洋，碩士生。焦揚，碩士生。

TP3

A

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