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

(河南理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

0 概述

云計算[1]的概念是在原本已存在的并行處理(parallel computing)、效用計算(utility computing)以及網(wǎng)格計算(grid computing)等科學(xué)計算領(lǐng)域的基礎(chǔ)上發(fā)展起來的一種基于互聯(lián)網(wǎng)的商業(yè)模式。

隨著電子商務(wù)以及大數(shù)據(jù)時代的到來,用戶提交了大量功能復(fù)雜的服務(wù)請求,對服務(wù)質(zhì)量的需求越來越高,細(xì)粒度原子服務(wù)幾乎難以達(dá)到用戶復(fù)雜多樣的需求標(biāo)準(zhǔn)。此時,需要復(fù)合多種云服務(wù),即對云平臺上已有的服務(wù)按照一定的業(yè)務(wù)邏輯構(gòu)造粒度更粗的服務(wù),即云服務(wù)組合[2]。

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

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

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

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

1 問題描述與模型建立

1.1 云服務(wù)組合問題描述

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

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

圖1 云服務(wù)組合

1.2 數(shù)學(xué)模型

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

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

qr(CSji)}

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

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

cr(CSji)}

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

(1)

(2)

云服務(wù)組合關(guān)于全局QoS約束的數(shù)學(xué)模型如式(3)所示。

(3)

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

(4)

2 改進(jìn)的蟻群優(yōu)化算法

2.1 蟻群優(yōu)化算法

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

(5)

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

(6)

2.2 信息素更新策略

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

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

(7)

(8)

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

(9)

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

(10)

(11)

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

2.3 遺傳算法

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

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

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

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

圖2 雙點交叉操作示意圖

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

(12)

其中,τC是一個常數(shù),相當(dāng)于MMAS算法中的τmax,τG是遺傳算法求解出的最優(yōu)路徑所轉(zhuǎn)換的信息素,KG為常數(shù)。

2.4 社會認(rèn)知算法

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

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

圖3 模仿學(xué)習(xí)示意圖

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

2.5 算法基本步驟

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

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

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

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

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

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

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

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

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

步驟9通過公式Mc=Mc+1,判斷是否滿足循環(huán)條件Mc=m,如果滿足則繼續(xù)下一步,否則轉(zhuǎn)回步驟7。

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

步驟11對記錄表L中的CSSi,采用改進(jìn)的模仿和觀察學(xué)習(xí)方法,得到x條新路徑CSTi,最后從CSSi和CSTi中選出優(yōu)秀的x條路徑用來更新記錄表L。

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

步驟13重置禁忌表tabum×n,如果改進(jìn)蟻群算法達(dá)到最大迭代次數(shù)NACO-max,那么輸出具有最優(yōu)評價值的服務(wù)組合路徑,否則轉(zhuǎn)回步驟5。

2.6 算法復(fù)雜度分析

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

3 實驗結(jié)果與分析

3.1 實驗設(shè)計

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

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

3.2 結(jié)果分析

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

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

圖4 3種算法的性能比較

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

表1 算法評價值與相應(yīng)時間

4 結(jié)束語

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