史振華

　　(紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000)

        摘要：針對(duì)云計(jì)算中無法合理分配資源的問題,提出了采用改進(jìn)的粒子群算法對(duì)其進(jìn)行分配。由于粒子群算法存在局部收斂速度快,容易陷入局部最優(yōu)解的情況,從粒子的選擇、參數(shù)調(diào)整和預(yù)防過早收斂三個(gè)方面進(jìn)行改進(jìn): (1)選擇粒子的時(shí)候采用適應(yīng)值最小的粒子,并根據(jù)約束函數(shù)淘汰不合格的粒子;(2)對(duì)慣性因子、個(gè)體最優(yōu)因子和全局最優(yōu)因子進(jìn)行改進(jìn);(3)通過設(shè)定系數(shù)來防止算法過早收斂。仿真說明,將改進(jìn)后的算法運(yùn)用在云計(jì)算方面,在云計(jì)算的資源失效、云端用戶完成時(shí)間和云計(jì)算環(huán)境下的能量消耗三個(gè)方面都優(yōu)于粒子群算法。

　　關(guān)鍵詞：粒子群算法;云計(jì)算;資源分配

　　中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.06.019

　　引用格式：史振華. 一種改進(jìn)的粒子群算法在云計(jì)算資源中的研究［J］.微型機(jī)與應(yīng)用，2017,36（6）：62-65.

0引言

　　云計(jì)算技術(shù)不斷發(fā)展,現(xiàn)在已經(jīng)成為了計(jì)算機(jī)界研究的一個(gè)熱點(diǎn)。相應(yīng)地，云計(jì)算服務(wù)不斷發(fā)展壯大,其應(yīng)用領(lǐng)域越來越廣泛。云計(jì)算是通過互聯(lián)網(wǎng)技術(shù)將海量的IT資源通過有償?shù)姆绞教峁┙o云端用戶,云計(jì)算服務(wù)商通過云計(jì)算數(shù)據(jù)中心對(duì)云環(huán)境中的資源進(jìn)行統(tǒng)一的管理和分配,最大限度地保證云端負(fù)載均衡［1］。由于云計(jì)算中的資源是動(dòng)態(tài)的,而云端用戶的需求是實(shí)時(shí)性和多樣性的,因此采用固定資源分配的方式無法滿足云端用戶的需求,云計(jì)算服務(wù)商提供的服務(wù)以資源調(diào)度方案最優(yōu),整體利益最大化為主要目標(biāo)。云計(jì)算資源調(diào)度是一個(gè)多任務(wù)的NP問題,不同的學(xué)者從不同的角度進(jìn)行了研究。文獻(xiàn)［2］提出了采用蛙跳結(jié)合神經(jīng)網(wǎng)絡(luò)的算法來解決云計(jì)算資源分配問題；文獻(xiàn)［3］提出將改進(jìn)的蟻群算法運(yùn)用到云計(jì)算資源調(diào)度中,取得了比較好的效果；文獻(xiàn)［4］提出了采用改進(jìn)的布谷鳥算法來進(jìn)行資源分配,提高了資源的分配效率;文獻(xiàn)［5］提出將多維模型與蟻群算法進(jìn)行相結(jié)合來進(jìn)行云計(jì)算資源的分配,取得了比較好的效果；文獻(xiàn)［6］提出了生物中的膜計(jì)算與蝙蝠算法相結(jié)合來解決云計(jì)算中的資源分配；文獻(xiàn)［7］提出了采用粒子群算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合的方法分配云計(jì)算資源,取得了比較好的效果。

　　本文將粒子群算法運(yùn)用到云計(jì)算中進(jìn)行資源分配,對(duì)于粒子算法存在的問題,分別從粒子的選擇、參數(shù)調(diào)整和預(yù)防過早收斂三個(gè)方面進(jìn)行改進(jìn)。仿真實(shí)驗(yàn)說明本文算法相比于基本粒子群算法在資源分配方面有了明顯的改進(jìn)。

1云計(jì)算資源簡(jiǎn)述

　　云計(jì)算中的資源調(diào)度關(guān)系到云計(jì)算的運(yùn)行效率、能量消耗和時(shí)間花費(fèi)等問題。云計(jì)算中的每一個(gè)云用戶是云環(huán)境中的一個(gè)節(jié)點(diǎn),每一個(gè)節(jié)點(diǎn)既使用服務(wù)又提供服務(wù),云用戶之間相互協(xié)作實(shí)現(xiàn)資源優(yōu)化配置。因此資源調(diào)度算法就成為資源配置的關(guān)鍵,如何設(shè)計(jì)一個(gè)良好的云計(jì)算資源算法是十分必要的。云計(jì)算資源的調(diào)度過程如圖1所示。

　　在云計(jì)算資源調(diào)度中,無論采用什么樣的資源調(diào)度策略,其目的都是為了更好地使用云計(jì)算資源為云用戶提供高質(zhì)量的服務(wù)。高效的云計(jì)算資源調(diào)度目標(biāo)是在調(diào)度資源的時(shí)候保證云計(jì)算的服務(wù)質(zhì)量(包括服務(wù)的時(shí)間、效率和可靠性),全面提高資源的利用率和負(fù)載均衡,實(shí)現(xiàn)利益的最大化。

　　目前,用于云計(jì)算資源調(diào)度的是啟發(fā)式的算法,這些算法包括粒子群算法、遺傳算法、蟻群算法和人工神經(jīng)網(wǎng)絡(luò)算法等,這些算法都具有良好的尋求最優(yōu)解的性能優(yōu)點(diǎn),但容易因自身的原因陷入局部而造成算法收斂。

　2改進(jìn)的粒子算法在云計(jì)算中的應(yīng)用

　　2.1基本的粒子群算法

　　粒子群算法是通過個(gè)體之間的相互協(xié)作和相互影響不斷地通過迭代來獲得最優(yōu)解的,群體之間的信息共享協(xié)助群體進(jìn)化。設(shè)定粒子群算法的目標(biāo)搜索空間是N維的,粒子群由m個(gè)粒子構(gòu)成,粒子的位置就是一個(gè)解,設(shè)Vmax為粒子的最大速度,因此群體中的粒子位置和速度采用N維向量來表示。其中,第k個(gè)粒子的位置為: Xk=(xk1,xk2,…，xkn)，k∈［1,m］,第k個(gè)粒子的速度為Vk=(vk1,vk2,…，vkn)，k∈［1,m］,粒子在迭代過程中的最佳位置就是個(gè)體最優(yōu)解的位置:Pkbest=(Pk1,Pk2,…，PkN),k=1,2,3,…，m,全局最優(yōu)解為:Gkbest=(Pg1,Pg2，…,PgN)。當(dāng)找到最優(yōu)解之后,通過目標(biāo)函數(shù)求出粒子的適應(yīng)值,通過適應(yīng)度的大小衡量粒子的位置,然后繼續(xù)以個(gè)體最優(yōu)解和全局信息解來更新自身的位置改變粒子的運(yùn)動(dòng)速度,逐步獲得最優(yōu)解。因此,粒子的更新速度和位置如下:

　　Vki=ηVki+αλ(Pkn－Vkn)+βμ(Pgn－Xgn)(1)

　　Xkn=Xkn+Vkn(2)

　　式中,η為慣性參數(shù),α和β分別是學(xué)習(xí)因子,α是調(diào)節(jié)粒子向個(gè)體最優(yōu)位置靠近飛行,β是粒子向群體最優(yōu)位置飛行,通常情況下,慣性系數(shù)η取值為1,λ和μ為相互獨(dú)立的隨機(jī)數(shù),Vmax為設(shè)置的最大速度。從以上分析可以發(fā)現(xiàn)粒子群算法中的最優(yōu)解是通過粒子之間的協(xié)作和相互競(jìng)爭(zhēng)來獲得的,粒子在空間以一定的速度飛行,每個(gè)粒子的運(yùn)動(dòng)通過個(gè)體與群體來不斷地調(diào)整速度和運(yùn)動(dòng)方向,從而獲得最優(yōu)解。

　　2.2粒子群算法的改進(jìn)

　　在粒子群算法中,沒有辦法對(duì)粒子進(jìn)行選擇,如果出現(xiàn)一些劣質(zhì)的粒子則會(huì)降低算法的收斂速度,影響算法的整體性能。此外,粒子是按照一定的準(zhǔn)則進(jìn)行更新的,根據(jù)粒子群的適應(yīng)度值進(jìn)行參數(shù)調(diào)整使得粒子向最優(yōu)解靠攏,但是在迭代過程中的參數(shù)調(diào)整對(duì)后期的算法影響比較大,有可能導(dǎo)致搜索精度降低，所以參數(shù)的設(shè)置對(duì)于算法的改進(jìn)具有一定的影響。因此根據(jù)粒子群算法實(shí)現(xiàn)的流程,本文從幾個(gè)方面進(jìn)行改進(jìn):(1)對(duì)優(yōu)良粒子進(jìn)行選擇,淘汰差的粒子;(2)對(duì)慣性因子、學(xué)習(xí)因子和群體因子進(jìn)行調(diào)整；(3)通過早熟對(duì)算法進(jìn)行判斷和處理。

　　2.2.1選擇粒子

　　粒子在進(jìn)行算法初始化后,都有一個(gè)適應(yīng)值,對(duì)于最大優(yōu)化問題認(rèn)定適應(yīng)值大的表示該粒子為優(yōu),反之,對(duì)于最小優(yōu)化問題則選擇適應(yīng)度值最小的粒子為優(yōu)。云計(jì)算中的資源調(diào)度目標(biāo)是以花費(fèi)最少資源,花費(fèi)最少使用時(shí)間為代價(jià)來滿足用戶的需求，因此在選擇粒子的時(shí)候應(yīng)該考慮適應(yīng)值最小的粒子。本文的適應(yīng)度函數(shù)為:

　　式中,T(i)表示第i個(gè)資源的時(shí)間消耗,C(i)表示第i個(gè)資源的成本消耗,D(i)表示第i個(gè)資源的帶寬消耗。

　　由于粒子算法在運(yùn)行過程中必須對(duì)粒子的運(yùn)動(dòng)進(jìn)行一定的約束,比如限定粒子的速度和運(yùn)動(dòng)的區(qū)域等條件,因此設(shè)定一個(gè)約束函數(shù)進(jìn)行解決,約束函數(shù)如下:

　　Con(i)=∑hj=1max(0,gj(x))+∑rp=1|hp(x)|

　　s.tgj(x)≥0,j=1,2,…，h

　　hp(x)=0,p=1,2,…，r(4)

　　式中g(shù)j(x)是不等式的約束條件,hp(x)為等式約束條件,它反映了粒子距離的區(qū)域的程度,約束值越大的粒子應(yīng)該最先被淘汰。因此選擇粒子的策略如下:

　　(1)根據(jù)目標(biāo)函數(shù)計(jì)算出粒子群中所有的粒子的初始值,并對(duì)其進(jìn)行按照從大到小的順序進(jìn)行排序。

　　(2)由約束函數(shù)計(jì)算出粒子群中的粒子的約束值。

　　(3)根據(jù)實(shí)際情況對(duì)粒子進(jìn)行淘汰,根據(jù)式(3)和式(4)的結(jié)果對(duì)不合格的粒子進(jìn)行淘汰,通過設(shè)定一定的比例和閾值對(duì)其粒子進(jìn)行篩選。

　　2.2.2參數(shù)調(diào)整

　　前文已經(jīng)闡述了粒子群算法中的參數(shù)的影響對(duì)于粒子的性能是巨大的,由于慣性因子對(duì)于算法的優(yōu)化性能非常直接,當(dāng)慣性因子的值小的時(shí)候,可以加速算法的收斂,當(dāng)慣性因子的值大的時(shí)候,可以跳出局部最優(yōu)解,學(xué)習(xí)因子α影響著個(gè)體最優(yōu)的搜索效率,群體學(xué)習(xí)因子β影響著整個(gè)群體的最優(yōu)的搜索,因此,本文對(duì)這三個(gè)參數(shù)進(jìn)行調(diào)整。

　　(1)對(duì)于慣性因子的調(diào)整:

　　式中,ηmax和ηmin分別為慣性因子的最大值和最小值,ηbest為當(dāng)前狀態(tài)中的最優(yōu)值,ηbest+ηmax－ηminηmax+ηmin為整體增量。

　　(2)對(duì)于個(gè)體學(xué)習(xí)因子的調(diào)整：

　　α=α+φN(6)

　　式中,φ為群體增量系數(shù),N為種群規(guī)模，φN為個(gè)體學(xué)習(xí)因子增量。

　　(3)對(duì)于群體學(xué)習(xí)因子的調(diào)整：

　　β=β+ψN(7)

　　式中,ψ為群體學(xué)習(xí)增量系數(shù),N為種群規(guī)模,ψN為群體學(xué)習(xí)因子。

　　2.2.3算法過早收斂判斷

　　粒子群算法自身的結(jié)構(gòu)并不復(fù)雜,但算法在實(shí)現(xiàn)過程中容易出現(xiàn)粒子向著局部最優(yōu)位置靠近的情況,這樣很容易造成算法的局部過早收斂,過早得到局部最優(yōu)解從而耽誤了出現(xiàn)全局最優(yōu)解的可能,使得算法過早地陷入了早熟的情況。因此算法有必要對(duì)早熟進(jìn)行判斷。由于粒子群算法中的粒子的位置決定著粒子適應(yīng)度,換而言之，粒子的適應(yīng)度反映了粒子的位置關(guān)系,因此可以將粒子的適應(yīng)度作為是否早熟的條件來進(jìn)行判斷。假設(shè)粒子群算法的數(shù)目為k,F(i)avg表示粒子群的平均適應(yīng)度值,Ω表示粒子的聚集度：

　　其中Ω表示粒子群算法聚合離散的程度,Ω的值越大說明聚集度越低,反之,說明聚集度越高。因此Ω數(shù)值越小越好,當(dāng)Ω值越來越大的時(shí)候,粒子群中的粒子越來越分散,當(dāng)大到一定程度的時(shí)候,算法滿足了終止條件,就陷入了收斂,因此設(shè)定一個(gè)常數(shù)Λ來避免這種情況的發(fā)生,當(dāng)Ω>Λ的時(shí)候,就需要進(jìn)行處理。由于慣性權(quán)重比較小的時(shí)候是有利于算法收斂的,但式(5)的值不斷變大調(diào)整,因此需要引入一個(gè)系數(shù)Γ來約束慣性權(quán)重不斷地增大。當(dāng)Ω>Λ時(shí),η=Γη。

　　2.3建立云計(jì)算的數(shù)學(xué)模型

　　在云計(jì)算的資源調(diào)度過程中,需要從整個(gè)網(wǎng)絡(luò)的帶寬、任務(wù)響應(yīng)的延遲、執(zhí)行時(shí)間等方面來進(jìn)行考慮,既需要讓云端的用戶請(qǐng)求服務(wù)與云服務(wù)中的資源匹配,又能夠合理高效地滿足云計(jì)算的資源。設(shè)定目標(biāo)函數(shù)為:

　　式中,Time(i)表示運(yùn)行任務(wù)i需要的時(shí)間,Delay(i)表示運(yùn)行任務(wù)i需要的延遲,Bandwith(i)表示運(yùn)行任務(wù)i的網(wǎng)絡(luò)帶寬，x+y+z=1。

　　2.4粒子群算法與云計(jì)算對(duì)應(yīng)關(guān)系

　　將云計(jì)算中的云端資源與改進(jìn)的粒子群中的粒子信息進(jìn)行對(duì)應(yīng),云計(jì)算中的資源選擇的過程就是改進(jìn)粒子群算法中的粒子淘汰的過程,公式(10)中約束條件對(duì)應(yīng)粒子算法中的選擇條件,資源調(diào)度中的最優(yōu)解即為改進(jìn)粒子群算法中的最優(yōu)解。

　　2.5算法步驟

　　算法步驟如下：

　　（1）以設(shè)計(jì)最優(yōu)的云計(jì)算中的資源調(diào)度為目標(biāo),設(shè)定云計(jì)算資源與粒子群中的粒子之間的對(duì)應(yīng)關(guān)系

　?。?）根據(jù)問題確定粒子群數(shù)目,設(shè)置慣性初始值、最大值和最小值、個(gè)體學(xué)習(xí)因子、群體群體學(xué)習(xí)因子、最大迭代次數(shù)、常數(shù)Λ和系數(shù)Γ、粒子初始化位置和速度；

　?。?）根據(jù)公式(3)選擇粒子的初始適應(yīng)值,淘汰表現(xiàn)不合格的因子；

　?。?）根據(jù)粒子群算法要求和公式(5)~(7)不斷更新粒子的個(gè)體最優(yōu)和群體最優(yōu),迭代次數(shù)加1；

　?。?）根據(jù)公式(9)判斷算法是否會(huì)進(jìn)行過早收斂,如果收斂則進(jìn)行處理,否則轉(zhuǎn)步驟（4）；

　?。?）判斷是否達(dá)到最大次數(shù),如果達(dá)到則轉(zhuǎn)步驟（9）；否則執(zhí)行下一步；

　?。?）判斷是否收斂,如果收斂則執(zhí)行下一步,否則執(zhí)行步驟（4）；

　?。?）確定群體最優(yōu)對(duì)應(yīng)的粒子信息;

　?。?）根據(jù)粒子信息確定最優(yōu)資源解；

　?。?0）算法結(jié)束。

3仿真實(shí)驗(yàn)

　　3.1搭建實(shí)驗(yàn)環(huán)境

　　本文實(shí)驗(yàn)選擇在操作系統(tǒng)為Windows 7,CPU為Inter Core T 6400,內(nèi)存為2 GB,硬盤為160 GB的臺(tái)式機(jī)上運(yùn)行。采用Cloudsim仿真平臺(tái)進(jìn)行實(shí)驗(yàn)。

　　3.2實(shí)驗(yàn)結(jié)果分析

　　為了進(jìn)一步說明本文算法相比與改進(jìn)前的粒子群算法的效率,將本文的算法與基本的粒子群算法從執(zhí)行云計(jì)算的資源失效、云端用戶完成時(shí)間和云計(jì)算環(huán)境下的能量消耗三個(gè)方面來進(jìn)行分析。

　　(1)資源失效

　　將云計(jì)算資源中的實(shí)際能力、存儲(chǔ)能力和通信能力作為評(píng)價(jià)資源淘汰的重要方面,設(shè)置慣性因子為2,個(gè)體學(xué)習(xí)因子為1.2,群體學(xué)習(xí)因子為2.2,最大迭代次數(shù)為500次,常數(shù)Λ和系數(shù)Γ分別為1.5和1，用戶任務(wù)為20,資源數(shù)目為10、30、50、70、90,進(jìn)行資源調(diào)度,選擇10次的淘汰資源的平均數(shù)作為任務(wù)效率的判別標(biāo)準(zhǔn),結(jié)果如表1和圖2所示。

　　從表1和圖2中可以發(fā)現(xiàn),基本的粒子群算法的平均淘汰曲線基本上處于水平狀,并沒有明顯的向上發(fā)展的趨勢(shì),而本文算法的平均資源淘汰曲線呈直線上升,這說明基本的粒子群算法沒有淘汰粒子,從而增加了算法在空間和時(shí)間上消耗,進(jìn)一步延遲了算法最優(yōu)解的產(chǎn)生。而本文算法通過淘汰狀態(tài)不佳的粒子,減少了算法規(guī)模,降低了迭代次數(shù),有利于云計(jì)算的資源調(diào)度。

　　(2)云端用戶完成時(shí)間

　　設(shè)置虛擬任務(wù)為200個(gè),使用本文算法與基本的粒子群算法進(jìn)行比較,從圖3中的曲線來看,本文算法的幅度大于基本的粒子群算法,這說明本文算法通過對(duì)自身參數(shù)的改進(jìn),使得算法的效率更高,從而導(dǎo)致曲線的幅度在開始階段比較大,隨著虛擬任務(wù)數(shù)目不斷增多,算法趨于穩(wěn)定。從結(jié)果來看,本文算法的任務(wù)完成時(shí)間明顯優(yōu)于粒子群算法。

　　(3)云用戶任務(wù)能量消耗

　　設(shè)置虛擬任務(wù)為200個(gè),使用本文算法與基本的粒子群算法進(jìn)行比較,從圖4中的曲線來看,本文算法在能量消耗方面明顯低于粒子群算法,這說明本文算法通過對(duì)自身過早收斂的改進(jìn)提高了算法的性能,隨著虛擬任務(wù)數(shù)目不斷增多,曲線趨于穩(wěn)定。這說明本文算法非常適合虛擬任務(wù)大的資源調(diào)度。

4結(jié)論

　　本文將粒子群算法運(yùn)用在資源調(diào)度中,并針對(duì)傳統(tǒng)的粒子群算法存在的問題進(jìn)行了改進(jìn),將改進(jìn)后的算法運(yùn)用在云計(jì)算的資源調(diào)度中,提高了資源分配效率,在仿真平臺(tái)中與粒子群算法進(jìn)行比較，取得了比較好的效果。

參考文獻(xiàn)

　?。?］ 李喬.云計(jì)算研究現(xiàn)狀綜述［J］.計(jì)算機(jī)科學(xué),2011,38(4):32-36.

　?。?］ Chen Xuan.Research of improved shuffled frog leaping algorithm in cloud computing resources［J］.International Jouranl of Grid and Distributed Computing,2016,9(3):24-28.

　?。?］ 聶清彬,蔡婷,王寧. 改進(jìn)的蟻群算法在云計(jì)算資源調(diào)度中的應(yīng)用［J］.計(jì)算機(jī)工程與設(shè)計(jì),2016,37(8):2016-2020.

　?。?］ 葉華喬,丁善婷.基于改進(jìn)的布谷鳥算法在云計(jì)算資源的研究［J］.計(jì)算機(jī)測(cè)量與控制,2014,22(12):4150-4154.

　?。?］ 蔣華,張樂乾,王鑫.基于多維評(píng)價(jià)模型及改進(jìn)蟻群優(yōu)化算法的云計(jì)算資源調(diào)度策略［J］.計(jì)算機(jī)測(cè)量與控制,2015,23(7):2559-2562.

　?。?］ 寧彬,谷瓊,吳釗.基于膜計(jì)算的蝙蝠算法在云計(jì)算資源調(diào)度的研究［J］.計(jì)算機(jī)應(yīng)用研究,2015,32(3):830-83.

　?。?］ 趙宏偉,李圣普.基于粒子群算法和RBF神經(jīng)網(wǎng)絡(luò)的云計(jì)算資源調(diào)度方法研究［J］.計(jì)算機(jī)科學(xué),2016,43(3):113-116.