史振華

　　(紹興職業技術學院,浙江 紹興 312000)

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

　　關鍵詞：粒子群算法;云計算;資源分配

　　中圖分類號：TP393文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.06.019

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

0引言

　　云計算技術不斷發展,現在已經成為了計算機界研究的一個熱點。相應地，云計算服務不斷發展壯大,其應用領域越來越廣泛。云計算是通過互聯網技術將海量的IT資源通過有償的方式提供給云端用戶,云計算服務商通過云計算數據中心對云環境中的資源進行統一的管理和分配,最大限度地保證云端負載均衡［1］。由于云計算中的資源是動態的,而云端用戶的需求是實時性和多樣性的,因此采用固定資源分配的方式無法滿足云端用戶的需求,云計算服務商提供的服務以資源調度方案最優,整體利益最大化為主要目標。云計算資源調度是一個多任務的NP問題,不同的學者從不同的角度進行了研究。文獻［2］提出了采用蛙跳結合神經網絡的算法來解決云計算資源分配問題；文獻［3］提出將改進的蟻群算法運用到云計算資源調度中,取得了比較好的效果；文獻［4］提出了采用改進的布谷鳥算法來進行資源分配,提高了資源的分配效率;文獻［5］提出將多維模型與蟻群算法進行相結合來進行云計算資源的分配,取得了比較好的效果；文獻［6］提出了生物中的膜計算與蝙蝠算法相結合來解決云計算中的資源分配；文獻［7］提出了采用粒子群算法與神經網絡相結合的方法分配云計算資源,取得了比較好的效果。

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

1云計算資源簡述

　　云計算中的資源調度關系到云計算的運行效率、能量消耗和時間花費等問題。云計算中的每一個云用戶是云環境中的一個節點,每一個節點既使用服務又提供服務,云用戶之間相互協作實現資源優化配置。因此資源調度算法就成為資源配置的關鍵,如何設計一個良好的云計算資源算法是十分必要的。云計算資源的調度過程如圖1所示。

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

　　目前,用于云計算資源調度的是啟發式的算法,這些算法包括粒子群算法、遺傳算法、蟻群算法和人工神經網絡算法等,這些算法都具有良好的尋求最優解的性能優點,但容易因自身的原因陷入局部而造成算法收斂。

　2改進的粒子算法在云計算中的應用

　　2.1基本的粒子群算法

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

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

　　Xkn=Xkn+Vkn(2)

　　式中,η為慣性參數,α和β分別是學習因子,α是調節粒子向個體最優位置靠近飛行,β是粒子向群體最優位置飛行,通常情況下,慣性系數η取值為1,λ和μ為相互獨立的隨機數,Vmax為設置的最大速度。從以上分析可以發現粒子群算法中的最優解是通過粒子之間的協作和相互競爭來獲得的,粒子在空間以一定的速度飛行,每個粒子的運動通過個體與群體來不斷地調整速度和運動方向,從而獲得最優解。

　　2.2粒子群算法的改進

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

　　2.2.1選擇粒子

　　粒子在進行算法初始化后,都有一個適應值,對于最大優化問題認定適應值大的表示該粒子為優,反之,對于最小優化問題則選擇適應度值最小的粒子為優。云計算中的資源調度目標是以花費最少資源,花費最少使用時間為代價來滿足用戶的需求，因此在選擇粒子的時候應該考慮適應值最小的粒子。本文的適應度函數為:

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

　　由于粒子算法在運行過程中必須對粒子的運動進行一定的約束,比如限定粒子的速度和運動的區域等條件,因此設定一個約束函數進行解決,約束函數如下:

　　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)

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

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

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

　　(3)根據實際情況對粒子進行淘汰,根據式(3)和式(4)的結果對不合格的粒子進行淘汰,通過設定一定的比例和閾值對其粒子進行篩選。

　　2.2.2參數調整

　　前文已經闡述了粒子群算法中的參數的影響對于粒子的性能是巨大的,由于慣性因子對于算法的優化性能非常直接,當慣性因子的值小的時候,可以加速算法的收斂,當慣性因子的值大的時候,可以跳出局部最優解,學習因子α影響著個體最優的搜索效率,群體學習因子β影響著整個群體的最優的搜索,因此,本文對這三個參數進行調整。

　　(1)對于慣性因子的調整:

　　式中,ηmax和ηmin分別為慣性因子的最大值和最小值,ηbest為當前狀態中的最優值,ηbest+ηmax－ηminηmax+ηmin為整體增量。

　　(2)對于個體學習因子的調整：

　　α=α+φN(6)

　　式中,φ為群體增量系數,N為種群規模，φN為個體學習因子增量。

　　(3)對于群體學習因子的調整：

　　β=β+ψN(7)

　　式中,ψ為群體學習增量系數,N為種群規模,ψN為群體學習因子。

　　2.2.3算法過早收斂判斷

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

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

　　2.3建立云計算的數學模型

　　在云計算的資源調度過程中,需要從整個網絡的帶寬、任務響應的延遲、執行時間等方面來進行考慮,既需要讓云端的用戶請求服務與云服務中的資源匹配,又能夠合理高效地滿足云計算的資源。設定目標函數為:

　　式中,Time(i)表示運行任務i需要的時間,Delay(i)表示運行任務i需要的延遲,Bandwith(i)表示運行任務i的網絡帶寬，x+y+z=1。

　　2.4粒子群算法與云計算對應關系

　　將云計算中的云端資源與改進的粒子群中的粒子信息進行對應,云計算中的資源選擇的過程就是改進粒子群算法中的粒子淘汰的過程,公式(10)中約束條件對應粒子算法中的選擇條件,資源調度中的最優解即為改進粒子群算法中的最優解。

　　2.5算法步驟

　　算法步驟如下：

　?。?）以設計最優的云計算中的資源調度為目標,設定云計算資源與粒子群中的粒子之間的對應關系

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

　?。?）根據公式(3)選擇粒子的初始適應值,淘汰表現不合格的因子；

　　（4）根據粒子群算法要求和公式(5)~(7)不斷更新粒子的個體最優和群體最優,迭代次數加1；

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

　?。?）判斷是否達到最大次數,如果達到則轉步驟（9）；否則執行下一步；

　　（7）判斷是否收斂,如果收斂則執行下一步,否則執行步驟（4）；

　?。?）確定群體最優對應的粒子信息;

　?。?）根據粒子信息確定最優資源解；

　?。?0）算法結束。

3仿真實驗

　　3.1搭建實驗環境

　　本文實驗選擇在操作系統為Windows 7,CPU為Inter Core T 6400,內存為2 GB,硬盤為160 GB的臺式機上運行。采用Cloudsim仿真平臺進行實驗。

　　3.2實驗結果分析

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

　　(1)資源失效

　　將云計算資源中的實際能力、存儲能力和通信能力作為評價資源淘汰的重要方面,設置慣性因子為2,個體學習因子為1.2,群體學習因子為2.2,最大迭代次數為500次,常數Λ和系數Γ分別為1.5和1，用戶任務為20,資源數目為10、30、50、70、90,進行資源調度,選擇10次的淘汰資源的平均數作為任務效率的判別標準,結果如表1和圖2所示。

　　從表1和圖2中可以發現,基本的粒子群算法的平均淘汰曲線基本上處于水平狀,并沒有明顯的向上發展的趨勢,而本文算法的平均資源淘汰曲線呈直線上升,這說明基本的粒子群算法沒有淘汰粒子,從而增加了算法在空間和時間上消耗,進一步延遲了算法最優解的產生。而本文算法通過淘汰狀態不佳的粒子,減少了算法規模,降低了迭代次數,有利于云計算的資源調度。

　　(2)云端用戶完成時間

　　設置虛擬任務為200個,使用本文算法與基本的粒子群算法進行比較,從圖3中的曲線來看,本文算法的幅度大于基本的粒子群算法,這說明本文算法通過對自身參數的改進,使得算法的效率更高,從而導致曲線的幅度在開始階段比較大,隨著虛擬任務數目不斷增多,算法趨于穩定。從結果來看,本文算法的任務完成時間明顯優于粒子群算法。

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

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

4結論

　　本文將粒子群算法運用在資源調度中,并針對傳統的粒子群算法存在的問題進行了改進,將改進后的算法運用在云計算的資源調度中,提高了資源分配效率,在仿真平臺中與粒子群算法進行比較，取得了比較好的效果。

參考文獻

　?。?］ 李喬.云計算研究現狀綜述［J］.計算機科學,2011,38(4):32-36.

　　［2］ 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.

　　［3］ 聶清彬,蔡婷,王寧. 改進的蟻群算法在云計算資源調度中的應用［J］.計算機工程與設計,2016,37(8):2016-2020.

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

　?。?］ 蔣華,張樂乾,王鑫.基于多維評價模型及改進蟻群優化算法的云計算資源調度策略［J］.計算機測量與控制,2015,23(7):2559-2562.

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

　?。?］ 趙宏偉,李圣普.基于粒子群算法和RBF神經網絡的云計算資源調度方法研究［J］.計算機科學,2016,43(3):113-116.