基于改進蟻群優化算法的服務組合與優化方法

沈記全,羅常委,侯占偉,劉志中

(河南理工大學 計算機科學與技術學院,河南 焦作 454000)

0 概述

云計算[1]的概念是在原本已存在的并行處理(parallel computing)、效用計算(utility computing)以及網格計算(grid computing)等科學計算領域的基礎上發展起來的一種基于互聯網的商業模式。

隨著電子商務以及大數據時代的到來,用戶提交了大量功能復雜的服務請求,對服務質量的需求越來越高,細粒度原子服務幾乎難以達到用戶復雜多樣的需求標準。此時,需要復合多種云服務,即對云平臺上已有的服務按照一定的業務邏輯構造粒度更粗的服務,即云服務組合[2]。

由于互聯網環境的復雜性、開放性以及動態性、用戶任務請求與反饋的隨意性、云服務負載的波動性等各種不確定因素的干擾,云平臺上出現了大量具有功能性等價特征的云服務。而它們的服務質量(Quality of Service,QoS)多數處于參差不齊的狀態,能達到用戶需求的較少。

到目前為止,眾多學者為了方便高效地處理QoS感知的云服務組合問題,分別提出了諸如模擬現實螞蟻群體協作尋找優化路徑的蟻群優化(Ant Colony Optimization,ACO)系統、模仿生物遺傳進化的遺傳算法(Genetic Algorithm,GA)、基于飛鳥集群覓食活動模型的粒子群優化(Particle Swarm Optimization,PSO)算法等為代表的群集協作智能算法。文獻[3]提出以3個相異的、適應度高的個體為進化核心的雙精英協同進化算法,通過采取不同的進化策略來提高算法的搜索能力。文獻[4]通過優化蟻群系統的信息素更新機制,提出一種多信息素動態更新的全局優化算法,相比于原始蟻群算法和遺傳算法,在求解服務組合優化問題時有著更優的性能。文獻[5]借鑒多目標遺傳算法的理論,提出一種基于全局QoS約束的多目標服務動態選擇優化算法GODSS,通過對多個目標函數進行優化,可以得出符合用戶需求的最優非劣解集合。文獻[6]提出一種基于頻率分配的蜂群優化算法,在求解旅行商問題的實驗中具有58.42%的改進。文獻[7]提出一種混合蟻群遺傳算法,通過對數值報告的分析,證明了該算法在處理全局復雜優化問題的可行性。上述的研究方法雖然在一定程度上可以求解服務組合問題,但都存在著各自的不足。例如:遺傳算法局部搜索能力不強,求解結果不穩定;蟻群算法初期信息素積累時間長、易陷入局部最優等。

文獻[8]提出一種新的群體智能算法——社會認知優化(Social Cognitive Optimization,SCO)算法,SCO雖然可以用來處理復雜連續函數的優化問題,但是該算法不能用來求解離散型的服務組合問題。

基于上述問題,本文對最大最小螞蟻系統進行改進,提出一種新的基于蟻群系統的云服務組合算法。該算法借鑒遺傳算法、社會認知優化算法的思想,求得最優云服務組合,并通過實驗來驗證該算法的可行性及精確性。

1 問題描述與模型建立

1.1 云服務組合問題描述

云服務組合通常被分為任務規劃、服務推薦、服務組合與優化3個步驟,本文的側重點在于云服務組合的第3個階段。多數云服務組合路徑的工作流控制模型都可分解為并行模型、選擇模型、循環模型以及順序模型。為方便研究服務組合問題,本文根據文獻[9]的方法處理并行的服務聚合流程,將其轉化為串行的順序模型。

盡管Internet中分布著海量不確定的云服務,但是功能單一的云服務往往不存在實用意義,要實現云服務的真正價值,關鍵在于將多個服務按照某種業務需求交互集成。設一條完整的云服務組合鏈如圖1所示,S1,S2,…,Sn是構成云服務組合鏈的服務節點,它們對應的候選服務簇分別為CS1,CS2,…,CSn,其中CSj(1≤j≤n)在m個功能上等價,但QoS狀態不同的服務CSji(1≤i≤m),即CSj={CSj1,CSj2,…,CSjm}。

圖1 云服務組合

1.2 數學模型

目前不同標準下建立的QoS參數體系總會有些出入,通常云服務的QoS參數是由一些諸如服務價格、執行時間、可靠性、可用性等不僅能夠體現服務本身固有的質量屬性,而且能夠體現用戶需求的非功能屬性構成[10]。根據順序結構的QoS聚合方法[9],可以計算出CSji的任何一個QoS屬性向量。一般而言,可定義服務CSji的QoS屬性向量為:

QoSji= {q1(CSji),q2(CSji),…,qk(CSji),…,

qr(CSji)}

其中,qk(CSji)(1≤k≤r)表示候選服務CSji的第k個屬性。根據用戶對服務綜合性能的不同需求定義了全局QoS約束條件如下:

Conji= {c1(CSji),c2(CSji),…,ck(CSji),…,

cr(CSji)}

每個候選云服務CSji都具有各種各樣的QoS屬性qk(CSji),大體上可以分成2種:一種是QoS屬性值越大越好的積極屬性(positive attribute),比如服務可用性、可靠性;另一種是考慮QoS屬性值最小化的消極屬性(negative attribute),比如服務價格、反應時間。顯而易見,qk(CSji)的度量單位及取值區間也不盡相同。通過采用簡單加權法(Simple Additive Weighting,SAW),按式(1)對多個QoS屬性值進行標準化處理。

(1)

(2)

云服務組合關于全局QoS約束的數學模型如式(3)所示。

(3)

云服務全局QoS需要滿足的約束條件如式(4)所示。

(4)

2 改進的蟻群優化算法

2.1 蟻群優化算法

最大最小螞蟻系統(MMAS)是文獻[11]基于螞蟻系統提出的仿生優化算法,并且在眾多的應用領域中得到了大力推廣和廣泛應用,是目前蟻群優化系統中性能最好的算法之一。螞蟻在尋優時以選擇概率為啟發式規則,會在不同的服務CSjk之間向著選擇概率最大的節點進行轉移,直到遍歷完所有的服務節點。本文采用了輪盤賭的方式增加算法搜索的隨機性來選擇候選云服務。

(5)

式(5)為螞蟻c在t時刻由當前云服務節點Sj的第k個候選服務CSjk,向下一個服務節點Sj+1的第i個候選服務CSj+1,l轉移的選擇概率。其中,α為信息啟發式因子,反映了螞蟻在遍歷過程中積累的信息素對后來螞蟻所起到的作用,β為期望啟發式因子,表示螞蟻在遍歷過程中的啟發信息對于螞蟻選擇路徑時的相對重要程度,allowdc={C-tabuc}表示螞蟻c下一步允許選擇的服務CSj+1,l,即還未曾被訪問到的候選服務,τkl(t)表示t時刻候選服務CSjk與CSj+1,l之間的信息素強度,ηkl(t)表示t時刻從候選云服務CSjk轉移到CSj+1,l的啟發函數,本文將目標函數設置為啟發函數:

(6)

2.2 信息素更新策略

考慮到信息啟發式因子α和期望啟發式因子β在算法運行中是保持相對穩定的,那么信息素的更新機制就成為了影響狀態轉移概率Pkl(t)的決定性因素。最大最小蟻群算法的信息素更新機制在原始的蟻群算法上進行了優化,選擇螞蟻迭代過程中的最優路徑增長信息素,這條路徑可能是當前循環中得到最佳路徑,也可能是第一次循環以來得到最佳路徑。然而一旦有大多數螞蟻都經過同一條路徑的情況發生,那么就大大降低了算法的隨機搜索能力。這樣可能會引起局部較優路徑上殘留信息素過多,從而導致啟發信息被淹沒,算法過早收斂于局部最優解。為了使算法搜索效率更高,本文設計的全局信息素更新公式如式(7)～式(9)所示。

τkl(t+1)=ρτkl(t)+Δτklg(t)

(7)

(8)

τkl(t+1)=(1-ρ)τkl(t)

(9)

當所有螞蟻都經歷過一次遍歷路徑尋優后,按照式(7)增長評價值處于前x位的螞蟻路徑的信息素,按照式(9)衰減評價值最差的x位螞蟻路徑上的信息素,用來影響螞蟻種群下一次循環遍歷的尋優過程。為了避免信息素連續不斷的積累,ρ的取值范圍取為ρ?[0,1),其中,ρ為全局信息素保留因子,(1-ρ)表示信息素揮發因子,Δτklg(t)代表第g只螞蟻在候選服務CSjk與CSj+1,l路徑上的信息素增量,f(CSg)代表處于第g只螞蟻經過路徑的評價值,el代表螞蟻尋優經過的第l條邊,Lg代表螞蟻經過的整條路徑。為了避免搜索停滯,陷入局部最優,對于各條路徑上的信息素τkl(t)都有τkl(t)∈[τmin,τmax]。最大最小信息素量如式(10)、式(11)[12]所示。

(10)

(11)

其中,Sbest是到目前為止具有最優評價值的螞蟻路徑,如果信息素τkl(t)出現?τkl(t)?[τmin,τmax]的情況,當τkl(t)≥τmax時,將τkl(t)的大小設定為τkl(t)=τmax,當τkl(t)≤τmin時,則將τkl(t)賦值為τkl(t)=τmin。

2.3 遺傳算法

由于蟻群算法具有正反饋、分布并行能力,能夠借助信息素的保留和更新而收斂于最優路徑,因此非常適合用來求解較為困難的組合優化問題。然而,因為蟻群算法在搜索初期時信息素極度匱乏,需要耗費大量時間積累信息素,導致了蟻群算法經常會出現搜索速度慢、易于停滯等問題,蟻群算法中至少有60%的時間都被用來形成初期信息素值[13]。借鑒生物進化過程中存在的自然選擇、優勝劣汰的鐵律以及基因的遺傳變異原理,美國密歇根大學的John Holland教授于1975年首先提出了遺傳算法,它具有隨機性、魯棒性和全局解空間搜索的特性,適合用來求解群體性全局優化問題[14]。但是當用遺傳算法來求解更精確的服務組合問題時,往往會出現不能充分利用系統中反饋信息的情況,而且當運行到某個階段時常常會產生許多沒有價值的冗余迭代,從而導致收斂能力較低。

為了集成2種算法的優點,達到揚長避短的目的。在采取蟻群的并行性、正反饋以及啟發式搜索等優勢求解服務路徑之前,首先借助遺傳算法的快速性、隨機性和全局搜索的能力初始化服務節點路徑上的信息素。

由于在云環境中不同用戶對于服務的要求往往差距較大,而且云服務簇中包含大量參差不齊的候選服務,因此不僅要參考服務質量的好壞,更要注重用戶個人的需求傾向。在遺傳算法中,一條完整的服務路徑CSGi代表染色體長度,采用十進制整數編碼,每一個基因對應于服務CSji。適應度函數的選取同樣關系到算法的收斂速度與最終解的優劣,本文選取式(3)作為遺傳算法的適應度函數。

交叉操作:在保證云服務路徑節點組合方式不變的前提下,隨機選擇節點服務CSji和CSj+d,i+d進行雙點交叉操作,如圖2所示。交叉概率和變異概率分別為常數PC和Pm,在算法運行中利用random生成r∈[0,1],如果r

圖2 雙點交叉操作示意圖

變異操作:遍歷服務組合路徑CSGi,由變異概率Pm決定該組合路徑上的服務節點CSji是否用候選服務CSjk進行替換,從而形成一個新的路徑組合。如果需要變異,則使用輪盤賭策略對路徑中的節點CSji進行變異,否則不采取任何行為。依靠這種操作,比較重新生成的服務路徑適應度評價值,除了評價值有所優化的服務組合之外,不接受其余的情況。當遺傳算法運行到最大迭代次數之后,選擇服務組合中居于前10%的適應值f10%better(CSi),并以式(12)生成改進蟻群算法中的初始信息素分布。

(12)

其中,τC是一個常數,相當于MMAS算法中的τmax,τG是遺傳算法求解出的最優路徑所轉換的信息素,KG為常數。

2.4 社會認知算法

很多研究群居性生物的科學家通過模擬昆蟲群落的集體行為,相繼研發出多種仿生優化算法,如GA、ACO、ABC等群集智能算法。然而,從現實中的生物群落來看,群居性昆蟲的合作終究較為簡單,人類社會比昆蟲群落具有更完整的社會形態與更高級的智慧層次。人類的學習過程是在利用觀察學習的同時,思考其他人因為不同選擇而引發的結果,并且將這個過程進一步轉化為符號的活動。類似這種采取觀察以及模仿其他人的言行舉止,從而不斷積累知識量的學習過程被定義為觀察學習,由于這樣的觀察學習是要求在人類社會的環境中才能發生的,因此也將觀察學習形象地稱之為社會學習。

社會認知算法的概念中包括了對模仿選擇的定義,從根本上來看,也就是利用不同知識點之間存在的優劣好壞,然后通過簡單的對比選擇出較好的知識點,沒有可能涉及到現實社會中人類群體之間彼此互通有無、共同成長的背后意義。鑒于此,為了達到讓SCO能夠處理離散型云服務組合優化問題的目的,本文結合文獻[15]提出的協作學習(collaborative learing)理念,改進了螞蟻群體間的模仿選擇。當螞蟻群體在每一次循環遍歷尋找最優路徑的過程中,參照螞蟻路徑評價值的優劣進行排序,直到選擇出x條較優的螞蟻路徑CSSi(1≤i≤x)作為模板,然后分別和剩余的m-1條螞蟻路徑一起分成相等的子路徑,對應的子路徑之間再進行模仿選擇,模仿學習示意圖如圖3所示。這樣就可以將m條螞蟻路徑CSRi(1≤i≤m)的局部優點集成到一起,進而得到x條優于其他路徑的新路徑CSTi(1≤i≤x)。

圖3 模仿學習示意圖

由SCO定義的學習代理是一個能夠在知識庫中進行搜索知識點的行為個體。憑借位于不同水準層次的知識點,行為個體能夠采取領域搜索的手段重新定位到一個水準更高的知識點,然而這種學習規則只能用來解決滿足解集合連續這一要求的學術研究。為了更好地處理離散型云服務組合路徑的優化問題,在SCO觀察學習規則的基礎上執行變異操作:當螞蟻群體完成協作學習的程序,為了搜索新的螞蟻路徑,對每一條經過協作學習程序的螞蟻路徑采取基于多點變異的操作,并且螞蟻路徑每進行過一次變異,就挑選出原路徑與變異之后路徑的較優者作為新路徑。經過多次變異的觀察學習操作,能夠得到更廣泛、更優秀的螞蟻路徑,還可以防止算法過早收斂于非全局最優值。其中螞蟻路徑變異的節點個數設為o,變異次數設為y。

2.5 算法基本步驟

在基于改進蟻群算法的云服務組合優化研究中,螞蟻經過的路徑CSRi代表服務組合方式,利用目標函數求解云服務組合路徑的聚合QoS評價值。初始時刻,輸入用戶QoS約束及偏好。具體步驟如下:

步驟1初始化云服務CSji以及QoS屬性值qk(CSji),按照式(4)的全局QoS約束條件初步篩選服務,設置遺傳算法的最大迭代次數NGA-max。

步驟2依次從節點Sj的候選服務簇CSji中選出具體服務組成染色體,形成規模為N的初始種群,并利用式(3)得到評價值排在前m條的染色體CSGi。

步驟3先根據交叉概率Pc選擇染色體進行雙點交叉操作,再由變異概率Pm決定基因是否需要采取變異操作,產生新的染色體。

步驟4判斷是否達到最大迭代次數NGA-max,若滿足條件,則停止遺傳算法,進入步驟5,否則返回步驟3。

步驟5初始化參數,設置螞蟻個數m,螞蟻循環變量Mc=1,改進蟻群算法的最大迭代次數NACO-max,禁忌表矩陣tabum×n,代表優秀螞蟻路徑的記錄表L,較差螞蟻路徑的記錄表R。

步驟6根據式(12)生成改進蟻群算法的初始信息素分布,其中KG=1。

步驟7按照式(5)計算出每只螞蟻移動到下一個服務節點的選擇概率Pkl(t),采用輪盤賭的方式增加改進蟻群算法搜索的隨機性。

步驟8更新禁忌表tabum×n,當螞蟻經過最后一個節點,計算路徑CSRi的聚合QoS評價值并排序。

步驟9通過公式Mc=Mc+1,判斷是否滿足循環條件Mc=m,如果滿足則繼續下一步,否則轉回步驟7。

步驟10選擇前x條螞蟻路徑CSSi放入記錄表L,選擇最差的x條路徑放入記錄表R。

步驟11對記錄表L中的CSSi,采用改進的模仿和觀察學習方法,得到x條新路徑CSTi,最后從CSSi和CSTi中選出優秀的x條路徑用來更新記錄表L。

步驟12采用上文提到的全局信息素更新策略,分別按照式(7)、式(9)對記錄表L和記錄表R中路徑的信息素進行增加和衰減。

步驟13重置禁忌表tabum×n,如果改進蟻群算法達到最大迭代次數NACO-max,那么輸出具有最優評價值的服務組合路徑,否則轉回步驟5。

2.6 算法復雜度分析

假設遺傳算法種群規模為N,迭代次數為NGA,則算法復雜度為O(NGA·N2)。蟻群算法復雜度為O(M+AN2+NACO×M2),M為蟻群規模大小,AN為初始解,NACO為進化代數。文中的蟻群優化算法的時間復雜度主要包括2個部分,分別為初始信息素生成和螞蟻遍歷尋優過程。信息素由遺傳算法生成,其復雜度為O((a+b)NGA×N×Nbetter),a表示目標函數的規模,b表示約束條件的個數,Nbetter表示遺傳算法進化過程中的精英種群。螞蟻尋優過程的時間復雜度為O(NACO·M·Mbetter),Mbetter表示蟻群算法迭代過程中的精英種群,那么蟻群優化算法的時間復雜度為O((a+b)NGA×N×Nbetter+NACO×M×Mbetter)。

3 實驗結果與分析

3.1 實驗設計

為了驗證上述改進蟻群算法在求解云服務組合優化問題上的有效性,本文實驗借鑒文獻[16]的方法,在一定的取值區間內隨機生成模擬云服務的QoS屬性值。測試案例中的云服務節點數一共有9個,且這些服務節點分別對應的候選云服務數目為50個。模擬實驗所采用的QoS屬性包括服務價格、執行時間2種消極屬性以及可靠性和可用性2種積極屬性。其中費用、反應時間的取值區間分別是[0,100]和[0,30],可靠性以及可用性的取值區間都設定為[0.80,1],它們對應的向量偏好比重被設定為{0.35,0.3,0.25,0.1}。在遺傳算法中的主要參數如下:初始種群N=100,最大迭代次數NGA-max=50,交叉率Pc=0.75,變異率Pm=0.15;在改進蟻群優化算法中,m=50,β=5,α=1,ρ=0.6,τmax=2,τmin=0.1,x=10。在社會認知優化算法中,螞蟻路徑被分成以下的子路徑,o=5,y=10。

改進蟻群優化算法實現工具為Microsoft Visual Studio 2012,運行環境PC的具體配置為Windows7操作系統,RAM為2.00 GB,處理器為Intel(R)Core(TM)2 Duo CPU E7500 @ 2.93 GHz。

3.2 結果分析

為了驗證改進蟻群算法處理云服務組合與優化問題的優越性,本文同時還采用最大最小蟻群算法、遺傳蟻群算法進行求解,它們都是在相同的實驗環境下通過C++編程語言實現。

3種算法求解云服務問題的性能如圖4所示。由圖4可見,最大最小蟻群算法經過30次迭代收斂,求得的評價值最低,與之相比,遺傳蟻群算法的求解結果有明顯提高,但是卻需要80次迭代才求得穩定結果。最終的改進蟻群算法擁有協作學習的能力,其25次迭代后所求得的服務組合方案已經收斂于最優解。

圖4 3種算法的性能比較

隨機從3種算法中選擇的服務組合方案評價值以及相應運行時間如表1所示。最大最小蟻群算法收斂于0.488,耗費26.988 s,所需時間最長;遺傳蟻群算法在32.84 s之后穩定在0.654 s,但是比最大最小蟻群算法耗時更久;本文的改進蟻群算法在求解云服務組合方案上,其在運行11.309 s時收斂于0.697 s,綜合性能明顯優于另外2種算法。

表1 算法評價值與相應時間

4 結束語

服務組合是目前服務計算領域研究的熱點,面對網絡上功能等價、服務質量卻參差不齊的海量云服務,用戶得到高質量服務組合的難度不斷增加。目前遺傳算法和蟻群算法等模擬進化算法在處理云服務組合與優化問題中的局限性越來越突出,社會認知算法的應用范圍又局限于連續性的組合優化研究。基于此,本文考慮了上述3種算法各自的優缺點,利用遺傳算法生成蟻群算法初始信息素分布,在尋優過程中引入社會認知優化算法的學習操作。實驗結果表明,改進后的蟻群算法在求解云服務組合與優化的問題中具有更高的求解效率,能夠得到精確度更高的最優解。