高速收斂混沌粒子群算法的云計算任務(wù)調(diào)度

王秉

(河南交通職業(yè)技術(shù)學(xué)院 航運(yùn)海事系， 河南 鄭州 450000)

高速收斂混沌粒子群算法的云計算任務(wù)調(diào)度

王秉

(河南交通職業(yè)技術(shù)學(xué)院 航運(yùn)海事系， 河南 鄭州 450000)

針對傳統(tǒng)粒子群算法在處理云計算任務(wù)調(diào)度問題時，存在求解精度不高、容易陷入早熟收斂等缺陷，提出一種改進(jìn)的高速收斂混沌粒子群算法.首先，采用混沌序列對初始化過程進(jìn)行優(yōu)化；其次，利用適應(yīng)度方差對早熟現(xiàn)象進(jìn)行有效診斷，并對算法在負(fù)梯度方向進(jìn)行修正，使其跳出局部最優(yōu)，實(shí)現(xiàn)高速收斂.仿真實(shí)驗(yàn)表明:改進(jìn)后的粒子群算法能有效地避免早熟，收斂速度及求解精度都明顯提高，非常適合云計算任務(wù)調(diào)度.

云計算； 任務(wù)調(diào)度； 粒子群算法； 混沌.

云計算資源服務(wù)模式有效地實(shí)現(xiàn)了資源配置和按需訪問.由于云計算具有分布式計算的特性，每天都要處理海量信息，且處理過程要有很高的實(shí)時性.因此,在云計算環(huán)境下，進(jìn)行高效合理的任務(wù)調(diào)度，實(shí)現(xiàn)系統(tǒng)全局最優(yōu)，成為時下研究的熱點(diǎn)問題之一[1-2].與網(wǎng)格計算類似，云環(huán)境下的任務(wù)調(diào)度也屬于一個NP難解問題[3].用于網(wǎng)格計算的傳統(tǒng)任務(wù)調(diào)度算法，如Min-Min/Max[4],Sufferage[5]等也被用于解決云環(huán)境下的任務(wù)調(diào)度，但效果不佳.而一些具有啟發(fā)式性質(zhì)的智能算法，在處理該問題時顯示出較好的效果，如遺傳算法[6]、蟻群算法[7]、粒子群算法等[8].劉萬軍等[9]研究云計算服務(wù)集群資源調(diào)度和負(fù)載平衡優(yōu)化問題，在粒子群算法中，引入了動態(tài)多群體協(xié)作和變異粒子逆向飛行思想；蘇淑霞[10]對傳統(tǒng)粒子群算法進(jìn)行改進(jìn)，采用間接方式進(jìn)行初始化編碼，擴(kuò)展了求解的空間，但是解的精度不高；封良良等[11]采取間接編碼形式，同時對適應(yīng)度函數(shù)進(jìn)行了優(yōu)化；王波等[12]將粒子群算法與遺傳算法結(jié)合，引入變異、交叉等機(jī)制，提高了算法的全局搜索能力，但求解過程較復(fù)雜.盡管取得了一定的成果，但在解決云環(huán)境下的任務(wù)調(diào)度問題時，必須考慮信息量的龐大.因此，粒子群算法應(yīng)該具有足夠的解空間，高效的求解速度及有效克服早熟收斂的能力等，而這些問題在現(xiàn)有文獻(xiàn)中的研究還不夠深入.基于此，本文研究將粒子群算法用于解決云環(huán)境下的任務(wù)調(diào)度問題.

1 問題的描述

目前，應(yīng)用最廣泛的是谷歌公司提出的Map/Reduce編程模型.該模型將整個計算過程分為2個階段：映射(Map)和化簡(Reduce).一個大任務(wù)可以被分解成多個相互獨(dú)立的子任務(wù)，在不同資源節(jié)點(diǎn)上,通過并行的方式完成，匯總后給出執(zhí)行結(jié)果.因此，云環(huán)境下任務(wù)調(diào)度問題是將子任務(wù)合理的與資源進(jìn)行匹配，從而使完成任務(wù)的總代價最小.

云計算環(huán)境下，假設(shè)總?cè)蝿?wù)為N，將其拆分為n個相互獨(dú)立的子任務(wù)，而這些子任務(wù)需要在m個虛擬資源節(jié)點(diǎn)上執(zhí)行(m

那么,任務(wù)完成的總時間為

式(3)中： RT(r,i)為第i個子任務(wù)在第r個資源上的完成時間.任務(wù)調(diào)度的優(yōu)化目標(biāo)即為使SFT最小.

2 算法的設(shè)計

2.1 標(biāo)準(zhǔn)粒子群算法

首先，在解空間初始化生成一群粒子，每個粒子都代表優(yōu)化問題的一個潛在最優(yōu)解，并通過位置、速度和適應(yīng)度值表征每個粒子的特性.粒子在解空間中運(yùn)動，根據(jù)個體極值Pbest和群體極值Gbest的變化對位置和適應(yīng)度值進(jìn)行更新.同時，通過對比新粒子的適應(yīng)度值和Pbest,Gbest的適應(yīng)度值，再次更新Pbest和Gbest.速度和位置的更新公式分別為

式(4)～(5)中：ω為慣性權(quán)重；d=1,2,…,D；k為當(dāng)前迭代次數(shù)；vi,d為粒子的速度；參數(shù)c1和c2為0或正常數(shù)，代表速度的加權(quán)學(xué)習(xí)因子；r1和r2是隨機(jī)數(shù)，取值范圍為[0,1].

為了避免粒子在解空間中盲目進(jìn)行目標(biāo)搜尋，位置一般取值范圍為[-zmax,zmax]，速度一般取值范圍為[-vmax,vmax].

2.2 混沌初始化

標(biāo)準(zhǔn)粒子群及許多改進(jìn)算法在初始化過程中,基本都采用隨機(jī)方式.這種方式雖然實(shí)現(xiàn)簡單，但是初始化粒子的均衡度較差，多樣性不高.考慮到混沌序列具有良好的隨機(jī)性和遍歷性，可以在一定程度上按照自身規(guī)律不重復(fù)遍歷全部狀態(tài).因此，文中研究在粒子群算法的初始化過程中，采用混沌序列，從而有效提高粒子的分布均衡度和多樣性.

在混沌理論中，包括多種混沌映射，使用的為立方映射數(shù)學(xué)模型為

y(n+1)=4y(n)3-3y(n)， -1≤y(n)≤1,n=0,1,2,….

由式(6)可知：立方映射生成序列的取值范圍為(-1,1),在使用時,還需將其映射到粒子的搜索空間，映射公式為

式(7)中：yi(d)為第i個粒子的第d維；xi，d為其坐標(biāo)；maxd和mind為其上下限.

此外，為了進(jìn)一步提高立方映射的分布多樣性，在生成粒子的過程中嵌入位置信息，即要滿足

式(8)中：zi為某一個利用立方映射生成的粒子向量；ε為事先選定的閾值;cos(zi,zj)為粒子間的位置信息，cos(zi,zj)越大表示粒子越靠近.

2.3 早熟診斷和高速收斂策略

盡管混沌序列初始化加強(qiáng)了粒子的多樣性，但還是無法避免粒子群算法出現(xiàn)早熟現(xiàn)象.早熟是算法錯誤地將一個局部次優(yōu)解當(dāng)作真正的全局最優(yōu)解，而使算法停止搜索.因此，早熟的有效診斷十分重要.在發(fā)現(xiàn)早熟現(xiàn)象以后，如何使粒子跳出當(dāng)前搜索空間，重新進(jìn)行有效搜索值得研究.

借鑒呂振肅等[13]提出的適應(yīng)度方差策略診斷算法的早熟現(xiàn)象，定義種群規(guī)模為N，fi為第i個粒子的當(dāng)前適應(yīng)度值，fave為平均適應(yīng)度值，那么，可以得到一個歸一化定標(biāo)因子，即

在此基礎(chǔ)上，適應(yīng)度方差的計算公式為

從適應(yīng)度方差的定義可知：粒子在收斂過程中，σ2會逐漸變小直至為0，達(dá)到完全收斂的狀態(tài)，表征的是種群中粒子的收斂程度.因此，可以根據(jù)經(jīng)驗(yàn)事先設(shè)定一個閾值，當(dāng)σ2小于這個閾值時，即判斷為算法早熟.盡管如此，當(dāng)算法搜索到真正的全局最優(yōu)解時，也會出現(xiàn)該現(xiàn)象，為了避免沖突，算法在運(yùn)行過程中，還要驗(yàn)證當(dāng)前的最優(yōu)適應(yīng)度值fbest是否大于理論最優(yōu)適應(yīng)度值fd，若條件成立，則為早熟.

當(dāng)判斷算法出現(xiàn)早熟現(xiàn)象以后，需給算法添加一個擾動，使粒子跳出當(dāng)前的搜索空間.采用負(fù)梯度方向調(diào)整策略，使粒子快速進(jìn)入新的搜索空間，并且整個算法以較高速率收斂.負(fù)梯度調(diào)整公式為

-

2.4 算法的實(shí)現(xiàn)步驟

步驟1 初始化種群規(guī)模N，粒子搜索空間維度D，慣性權(quán)重ω0，加速因子c1和c2，迭代次數(shù)t=0，最大迭代次數(shù)為T.

步驟2 隨機(jī)生成一組粒子位置的初始向量z1=(z1,1，z1,2,…,z1,D),取值范圍(-1,1)，剩余N-1組粒子位置的初始向量按照式(6)產(chǎn)生.要注意滿足式(8)條件，并按照式(7)進(jìn)行映射.

步驟4 更新粒子速度、位置和慣性權(quán)重.

步驟5 按照式(10)計算適應(yīng)度方差σ2，如果σ2<γ且fbest>fd，按照式(11)進(jìn)行調(diào)整.

步驟6t=t+1，如果t

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

為了驗(yàn)證文中所提算法的性能，在Cloudsim云平臺實(shí)現(xiàn)算法的仿真分析，并與標(biāo)準(zhǔn)粒子群算法和文獻(xiàn)[11]提出的改進(jìn)粒子群算法進(jìn)行比較.

設(shè)置算法的參數(shù)為：種群規(guī)模100，慣性因子ω=0.9，加速因子c1=c2=2，最大迭代次數(shù)200.完成一組固定任務(wù)和資源數(shù)量的調(diào)度對比試驗(yàn)，共包括2種情況：1) 50個任務(wù)，5個資源；2) 500個任務(wù)，5個資源.2種情況下的任務(wù)性質(zhì)和資源能力完全相同，所有任務(wù)的長度范圍為[400 MI，1 000 MI]，5個資源的處理能力分別為{400 MIPs，600 MIPs，800 MIPs，1 000 MIPs，1 200 MIPs}.每種算法在相同條件下各運(yùn)行10次，取平均值作為最終的結(jié)果，如圖1所示.圖1中：n為迭代次數(shù)，t為總?cè)蝿?wù)完成時間.

由圖1可知：由于文中算法與文獻(xiàn)[11]算法在標(biāo)準(zhǔn)粒子群算法的初始化階段都進(jìn)行了優(yōu)化，因此,算法迭代前期，任務(wù)調(diào)度的時間基本相同，但都優(yōu)于標(biāo)準(zhǔn)粒子群算法；隨著算法迭代的深入，標(biāo)準(zhǔn)粒子群算法和文獻(xiàn)[11]算法沒有早熟的診斷和跳出機(jī)制.因此，找到的都不是最優(yōu)解，任務(wù)調(diào)度的時間也要明顯多于文中算法，尤其是在情況1時，文獻(xiàn)[11]算法的后期結(jié)果與標(biāo)準(zhǔn)粒子群算法接近，可見早熟對于粒子群算法影響較大，而文中算法卻始終保持一個較好的進(jìn)化過程，性能明顯更好.

考察在資源數(shù)量一致且任務(wù)量不同的情況下，3種算法的性能.設(shè)置資源個數(shù)為5，任務(wù)量從0依次遞增到500(每隔50遞增).算法參數(shù)與上述相同，結(jié)果如圖2所示.圖2中：t表示任務(wù)完成時間；Nr表示任務(wù)數(shù).

(a) 情況1 (b) 情況2

由圖2可知：當(dāng)資源數(shù)量固定時，隨著任務(wù)數(shù)量的增加，調(diào)度時間也逐漸增加；但是標(biāo)準(zhǔn)粒子群算法與文獻(xiàn)[11]算法的調(diào)度用時明顯高于文中算法，尤其是任務(wù)數(shù)量達(dá)到150以后，差距更為顯著；隨著任務(wù)數(shù)量的進(jìn)一步遞增，文中算法的優(yōu)勢更加明顯.

比較任務(wù)量固定、資源數(shù)量不同時，3種算法的性能，主要考察資源負(fù)載均衡度，結(jié)果如圖3所示.圖3中：η為資源負(fù)載均衡度；Nd為資源節(jié)點(diǎn)數(shù)量.根據(jù)以往的研究[14]，資源負(fù)載均衡度越接近1，說明資源的利用率越高，算法的調(diào)度越理想.

由圖3可知：文中算法具有更好的系統(tǒng)負(fù)載均衡度，平均值為0.847，比較接近1，說明該算法對資源的利用率較高.而文獻(xiàn)[11]算法和標(biāo)準(zhǔn)粒子群算法的資源負(fù)載均衡度分別只有0.6和0.5左右，相對較低，反映出資源負(fù)載具有較高的不平衡度.

圖2 不同任務(wù)量情況下的調(diào)度結(jié)果 圖3 3種算法的資源負(fù)載均衡度比較

綜合上述實(shí)驗(yàn)結(jié)果，提出的高速收斂混沌粒子群算法的性能更優(yōu)，更適合解決云計算環(huán)境下的資源調(diào)度問題.

4 結(jié)束語

對云計算環(huán)境下的任務(wù)調(diào)度問題進(jìn)行深入研究,提出一種基于高速收斂混沌粒子群的任務(wù)調(diào)度算法.簡要分析了云環(huán)境下的計算模型，并針對標(biāo)準(zhǔn)粒子群算法的缺陷提出了改進(jìn)措施.采用混沌映射優(yōu)化初始化過程，同時給出了算法早熟的診斷方法和高速收斂策略.仿真實(shí)驗(yàn)的結(jié)果表明:所提算法具有較好的性能，收斂速度快，求解的精度更高，非常適合解決云計算環(huán)境下的資源調(diào)度問題.在下一步的工作中，還將研究同時考慮計算成本、節(jié)能等因素的云計算調(diào)度問題.

[1] GUO Lizheng,ZHAO Shuguang,SHEN Shigen,et al.Task scheduling optimization in cloud computing based on heuristic algorithm[J].Journal of Networks,2012,7(3):547-553.

[2] 王燕瓊,李國剛.下行多小區(qū)MIMO系統(tǒng)協(xié)作多點(diǎn)傳輸聯(lián)合調(diào)度機(jī)制[J].華僑大學(xué)學(xué)報(自然科學(xué)版),2012,33(3):260-264.

[3] ARMBRUST M,FOX A,GRIFFITH R,et al.A view of cloud computing[J].Communications of the ACM,2010,53(4):50-58.

[4] 王觀玉.網(wǎng)格計算中任務(wù)調(diào)度算法的研究和改進(jìn)[J].計算機(jī)工程與科學(xué),2011,33(10):186-190.

[5] 胡志剛,陳俊.網(wǎng)格工作流中一種擴(kuò)展的QD-Sufferage調(diào)度算法[J].計算機(jī)應(yīng)用研究,2008,25(5):1504-1506.

[6] 朱宗斌,杜中軍.基于改進(jìn)GA的云計算任務(wù)調(diào)度算法[J].計算機(jī)工程與應(yīng)用,2013,49(5):77-80.

[7] LI Jianfeng,PENG Jian,CAO Xiaoyang,et al.A task scheduling algorithm based on improved ant colony optimization in cloud computing environment[J].Energy Procedia,2011,6(13):6833-6840.

[8] 郭力爭,耿永軍,姜長源,等.云計算環(huán)境下基于粒子群算法的多目標(biāo)優(yōu)化[J].計算機(jī)工程與設(shè)計,2013,34(7):2358-2362.

[9] 劉萬軍,張孟華,郭文越.基于MPSO算法的云計算資源調(diào)度策略[J].計算機(jī)工程,2011,37(11):43-44.

[10] 蘇淑霞.粒子群算法在云計算任務(wù)調(diào)度中的應(yīng)用[J].南京師大學(xué)報(自然科學(xué)版),2014,37(4):145-149.

[11] 封良良,張?zhí)?賈振紅，等.云計算環(huán)境下基于粒子群的任務(wù)調(diào)度算法研究[J].計算機(jī)工程,2013,39(5):183-186.

[12] 王波,張曉磊.基于粒子群遺傳算法的云計算任務(wù)調(diào)度研究[J].計算機(jī)工程與應(yīng)用,2015,51(6):84-88.

[13] 呂振肅,侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法[J].電子學(xué)報,2004,32(3):416-420.

[14] lSARD M,PRABHAKARAN V,CURRCY J,et al.Quincy: Fair scheduling for distributed computing clusters[C]∥Proceedings of on Operating Systems Principles.New York:ACM,2009:261-276.

(責(zé)任編輯： 黃曉楠 英文審校： 吳逢鐵)

Cloud Computing Task Scheduling of High-Speed Convergence of Chaotic Particle Swarm Optimization

WANG Bing

(Department of Maritime, Henan Vocational and Technical College of Communications， Zhengzhou 450005, China)

In this paper, we proposed an advanced high speed of convergence chaotic particle swarm algorithm to adjust the common problems of traditional particle swarm algorithm such as low accuracy and easily trapped in premature convergence during the cloud computing task scheduling. Firstly, the initial process was optimzed by chaotic sequence. Then, the effective diagnosis of premature phenomenon was determined by fitness variance. The algorithm correction was performed by negative gradient direction, which could jump out the local optimum and achieve high speed of convergence.Simulation experiments show that the improved particle swarm algorithm can effectively avoid premature, enhance convergence speed and solution accuracy, which is suitable for cloud computing task scheduling.

cloud computing; task scheduling; particle swarm optimization algorithm; chaotic

1000-5013(2015)06-0650-05

10.11830/ISSN.1000-5013.2015.06.0650

2015-10-08

王秉(1965-)，男，副教授，主要從事計算機(jī)圖形圖像的研究.E-mail:wbjtxy@163.com.

國家自然科學(xué)基金資助項(xiàng)目(201411326136)； 河南省科技廳項(xiàng)目(2013132300410337)

TP 393

A