改進魚群算法在云計算任務(wù)調(diào)度中的應(yīng)用

張曉麗

（西安航空學(xué)院 計算機學(xué)院，陜西 西安710077）

改進魚群算法在云計算任務(wù)調(diào)度中的應(yīng)用

張曉麗

（西安航空學(xué)院 計算機學(xué)院，陜西 西安710077）

云計算環(huán)境中的任務(wù)調(diào)度問題一直是云計算研究的重點，任務(wù)調(diào)度的目的尋找最優(yōu)的任務(wù)調(diào)度策略，以高效地完成計算任務(wù)。針對云計算環(huán)境下資源規(guī)模龐大、異構(gòu)性的特點，為了克服傳統(tǒng)調(diào)度算法存在的缺點，提出一種基于改進自適應(yīng)人工魚群算法的任務(wù)調(diào)度算法。該算法以任務(wù)總執(zhí)行時間作為目標函數(shù)，在迭代過程中動態(tài)自適應(yīng)的調(diào)整人工魚的視野和步長，同時對覓食行為進行改進，加快算法的收斂速度，避免算法陷入局部最優(yōu)，以此提高任務(wù)調(diào)度的性能。通過在CloudSim平臺進行仿真對比實驗，相較于其他智能尋優(yōu)算法，該算法在任務(wù)執(zhí)行時間和收斂速度上都有明顯的優(yōu)勢，是一種有效的任務(wù)調(diào)度算法。

云計算；任務(wù)調(diào)度；人工魚群算法；自適應(yīng)

云計算[1-2]作為一種新興的計算服務(wù)商業(yè)模式，集成了網(wǎng)格計算、分布式計算和并行計算等技術(shù)，自提出以來就成為一個熱點研究方向。云計算采用虛擬化技術(shù)，將大量通過網(wǎng)絡(luò)連接的計算資源存儲資源與軟件資源整合起來，構(gòu)成大規(guī)模的共享虛擬資源池，為用戶提供廉價的按需服務(wù)，同時將用戶提交的任務(wù)分配給計算機資源池進行合理調(diào)度。由于云計算中存在諸多形態(tài)不同的云端，且面對的計算資源種類眾多、提供服務(wù)效率不一、計算任務(wù)數(shù)量巨大，在“云”中如何將眾多任務(wù)進行合理調(diào)度滿足用戶對服務(wù)質(zhì)量的要求并且更有效利用云計算系統(tǒng)中的資源一直是一個核心關(guān)注熱點[2-3]。大量研究結(jié)果表明，云計算任務(wù)調(diào)度實際上是一個NP難題[4]，也是一個組合優(yōu)化問題。針對云計算的任務(wù)調(diào)度問題，國內(nèi)外學(xué)者對其進行了相應(yīng)的研究，提出了大量的云計算任務(wù)調(diào)度算法。例如最小最?。╩in-Min）[5]、Sufferage算法[6]和一些啟發(fā)式算法如基于蟻群的調(diào)度算法[7]、基于遺傳的調(diào)度算法[8]、基于粒子群的調(diào)度算法[9]、基于遺傳模擬退火算法的調(diào)度算法[10]等。但這些算法通常都存在收斂性能或搜索全局最優(yōu)解的能力較低，容易陷入局部最優(yōu)值，調(diào)度目標單一等問題。

文獻[11]提出的人工魚群算法作為人工智能領(lǐng)域的研究成果之一，采用自下而上的信息尋優(yōu)模式，具有較強的跳出局部極值點的能力，對搜索空間具有一定的自適應(yīng)能力，并具有魯棒性強，對初值的敏感性小，簡單易實現(xiàn)等諸多優(yōu)點，在求解大規(guī)模復(fù)雜優(yōu)化問題上取得了較好效果。因此，考慮上述現(xiàn)有調(diào)度算法存在的不足，文中針對云計算任務(wù)調(diào)度的特點，對云環(huán)境中資源的高效合理調(diào)度進行了研究，為了克服基本人工魚群算法在后期收斂速度慢和計算量大的缺陷，提出一種動態(tài)自適應(yīng)的人工魚群算法，并將該改進算法應(yīng)用于云計算任務(wù)調(diào)度問題研究，實驗證明該算法能有效減少云計算任務(wù)調(diào)度的總時間。

1 云計算任務(wù)調(diào)度模型

云計算環(huán)境下的任務(wù)調(diào)度是以任務(wù)為基本單位，按照一定的任務(wù)調(diào)度策略，將相互獨立的多個任務(wù)以最合理的方案分配到可用的計算資源上，以使得任務(wù)的總執(zhí)行時間跨度最短同時能夠充分利用現(xiàn)有資源。因此云計算任務(wù)調(diào)度模型的優(yōu)劣直接影響任務(wù)的執(zhí)行效率，從而影響整個云的性能和用戶的滿意度。文中只考慮任務(wù)之間相互獨立的情況，并且假設(shè)每個任務(wù)在計算資源節(jié)點上的執(zhí)行時間是已知的。

根據(jù)云計算任務(wù)調(diào)度的特點，定義如下的數(shù)學(xué)參數(shù)模型：{T，R，TR，TS，ETC，MT}

1）T={t1，t2，…，tn}表示任務(wù)模型，包括 n個相互獨立的任務(wù)，其中ti表示第i個任務(wù)；

2）R={r1，r2，…，rm}表示資源模型，包括m個可用于執(zhí)行任務(wù)的高性能計算資源，其中m＜n，rj表示第j個計算資源；

3）TR=[tr]m×n表示任務(wù)和資源之間的映射關(guān)系，如果任務(wù)i調(diào)度給資源j執(zhí)行，則trji=i，否則trji=0；

4）TS=[ts]m×n表示任務(wù)開始時間矩陣，其中tsji表示任務(wù)ti調(diào)度給計算資源rj的開始時間，初始值設(shè)為0；

5）ETC=[etc]m×n表示預(yù)測執(zhí)行時間矩陣，etcji表示任務(wù)ti在資源rj上的預(yù)測執(zhí)行時間；

6）MT=[mt]m×n表示任務(wù)的預(yù)測完成時間，mtji則表示任務(wù)ti在資源rj上的預(yù)測完成時間，由以上參數(shù)可知，任務(wù)ti在資源rj上預(yù)測完成時間如式（1）:

由于計算資源是并行運行的，基于以上描述，云計算環(huán)境下的任務(wù)調(diào)度的主要目標是尋找最優(yōu)的調(diào)度策略以最小化計算任務(wù)在各個資源上的完成時間，使其得到最高的執(zhí)行效率，即min（mtji）。

2 改進自適應(yīng)魚群算法的任務(wù)調(diào)度

2.1 基本人工魚群算法

人工魚群算法[11-12]（Artificial Fish Swarm Algorithm，AFSA）是李曉磊等人于2002年基于模擬魚群行為提出的一種群體智能優(yōu)化算法。該算法在迭代的過程中主要通過人工魚的覓食、聚群和追尾行為實現(xiàn)自我更新，通過魚群中各個體之間的集體協(xié)作以達到全局尋優(yōu)的目的，該算法簡單易實現(xiàn)，能夠很好的解決組合優(yōu)化問題。

該算法的數(shù)學(xué)模型描述如下：

人工魚個體的狀態(tài) X=（x1，x2，…，xn），其中 xi（i= 1，2，…，n）為需要尋優(yōu)的變量；每個人工魚當前所在位置的食物濃度表示為f（X），即求解的目標函數(shù)值；人工魚個體之間的距離di，j=‖Xi-Xj‖；人工魚的視野范圍用Visual表示；移動的步長用Step表示；擁擠度因子用δ表示；人工魚每次覓食最大的試探次數(shù)用try_number表示。

2.2 改進的人工魚群算法

2.2.1 視野和步長的改進

分析基本魚群算法的數(shù)學(xué)模型可知，AFSA中的控制參數(shù)會直接或間接影響算法的求解質(zhì)量與速度。文獻[14]的研究結(jié)果表明，AFSA算法控制參數(shù)中的視野和步長對算法的收斂速度和求解精度都有較大影響。

視野參數(shù)確定人工魚的搜索范圍，在其固定不變的情況下，當人工魚個體逐漸逼近最優(yōu)解時，只有少量人工魚的狀態(tài)與最優(yōu)解不同，如果這時的人工魚依然以原始視野進行覓食行為顯然是盲目的，因此在這種情況下應(yīng)該使用較小的視野范圍進行深度搜索。如果視野范圍較小，則人工魚的局部搜索能力較強，但會導(dǎo)致算法收斂速度變慢，且計算量大，甚至陷入局部最優(yōu)；而視野范圍較大，則人工魚在前期收斂很快且全局搜索能力較強，但容易跳過最優(yōu)解。為了解決上訴問題，需要對基本的人工魚群算法進行改進，在算法運行前期，采用較大的視野，以增強算法的全局搜索能力和收斂速度，隨著算法的迭代進行，視野范圍逐漸減小，從而加強算法的局部搜索能力和提高搜索解的精度。但是，如果后期視野范圍太小則會影響最優(yōu)解的搜索。因此，改進的魚群算法在迭代過程中通過式（3）動態(tài)調(diào)整人工魚的視野，當人工魚的當前視野值減小到最小視野時，使用最小視野作為當前視野，從而有效地改善算法的性能。

其中，g為當前迭代次數(shù)，Gmax為最大迭代次數(shù)，visualmin為最小視野，visualg表示當前的視野。文中設(shè)定visualmin=1。

步長參數(shù)決定了算法的收斂速度和求解精度，步長越大則前期收斂速度越快，但有時會出現(xiàn)振蕩現(xiàn)象，難以準確逼近最優(yōu)值的情況；步長越小則收斂速度越慢，但求解精度越高。因此對于步長參數(shù)，本文使用式（4）隨視野范圍動態(tài)調(diào)整。

其中step0為步長設(shè)置的初始值，使用式（4）變步長在搜索初期可以得到較快的收斂速度，后期可以進行更加細致的搜索，從而提高搜索到最優(yōu)值的幾率。

另外，文獻[14]指出，擁擠度因子δ越小，覓食和隨機行為比較突出，從而人工魚擺脫局部極值的能力也就越強。因此，在迭代過程中，文中采用指數(shù)式的衰減策略計算擁擠度因子[15，17]：

其中，α為衰減因子，文中設(shè)置α=0.6。

2.2.2 覓食行為的改進

人工魚的覓食行為是算法收斂的基礎(chǔ)，在基本人工魚群算法中，覓食行為是一種盲目性搜索，沒有充分利用之前的搜索信息，因此不利于在視野范圍內(nèi)盡可能多地去尋找較優(yōu)解。改進的覓食行為是當人工魚個體沒有找到較優(yōu)狀態(tài)時，隨機選擇一個新的狀態(tài)，如果該狀態(tài)優(yōu)于當前位置，則直接跳躍到該位置，否則在試探次數(shù)內(nèi)再隨機選擇一狀態(tài)進行判斷，當其試探次數(shù)超過try_number，如果依然不滿足前進條件，則依據(jù)概率P（0≤P≤1）向之前搜索到的全局最優(yōu)解的方向移動一步，概率P為一個隨機數(shù)，文中設(shè)置P=0.5。

2.2.3 算法步驟

改進人工魚群算法的流程圖如圖1所示。

圖1 算法流程圖

由上述算法流程可以看出，在每一次迭代過程中，算法將會選擇魚群中的最優(yōu)解來更新公告板，最后得到的人工魚模型則是公告板記錄的最優(yōu)解，也就是任務(wù)調(diào)度的最終分配方案。

3 仿真試驗結(jié)果與分析

為了驗證和評價本文算法的正確性和可靠性，采用墨爾本大學(xué)開發(fā)的開源的云仿真平臺CloudSim[16]來進行仿真對比實驗，首先在相同的實驗環(huán)境和參數(shù)相同的情況下對比測試了本文算法和基本ASFS算法的收斂性，然后在任務(wù)數(shù)改變以及計算資源改變的環(huán)境下分別對本文算法、蟻群算法[7]、改進遺傳算法[8]和改進粒子群算法[9]的性能進行對比試驗。

1）算法的收斂性對比

模擬云計算資源數(shù)為10，調(diào)度任務(wù)數(shù)為100的仿真云環(huán)境，在此環(huán)境下，設(shè)置基本參數(shù)如表1所示，測試本文算法和基本AFSA算法的收斂性，得到收斂曲線如圖1所示。

表1 基本參數(shù)設(shè)置

圖2 算法收斂性比較

從圖2的收斂曲線圖看以看出，在基本參數(shù)設(shè)置相同的情況下，本文方法的收斂速度明顯優(yōu)于基本AFSA，并且比基本魚群算法優(yōu)先達到最優(yōu)方案。這主要是因為改進后的算法在迭代過程中，根據(jù)迭代的次數(shù)動態(tài)調(diào)整算法的視野范圍和步長，使其在前期保持較大的視野和步長，而后期使用較小的視野和步長。而基本魚群算法在整個迭代過程中使用固定的視野和步長，這就導(dǎo)致在后期收斂速度變慢，甚至可能陷入局部最優(yōu)。

2）計算資源相同，任務(wù)數(shù)改變時完成時間對比

針對云計算環(huán)境任務(wù)動態(tài)性的特點，分別模擬在10個計算資源、50個子任務(wù)以及10個計算資源、500個子任務(wù)兩種調(diào)度規(guī)模下，對算法的性能進行了對比。在相同的實驗環(huán)境下，取各算法多次運行的平均結(jié)果作為實驗的最終結(jié)果。本實驗的目的是為了測試在計算資源相同的情況下，任務(wù)數(shù)發(fā)生變化對調(diào)度結(jié)果性能的影響。4種調(diào)度算法的任務(wù)完成時間如圖3所示。

由圖3可知，在資源相同，任務(wù)數(shù)不同的調(diào)度規(guī)模下，當任務(wù)量較少時，3種算法均能獲得云計算任務(wù)調(diào)度性能較優(yōu)的方案，且快速收斂，性能上不存在太大的差異。但是隨著任務(wù)數(shù)的增加，任務(wù)之間的競爭相對激烈，3種算法的總?cè)蝿?wù)完成時間都在增加，從圖3中可以看出，使用本文算法在收斂速度和總?cè)蝿?wù)完成時間上優(yōu)于對比算法。這主要是由于本文算法在迭代過程中動態(tài)自適應(yīng)調(diào)整人工魚的搜索范圍和移動步長，獲得更高的資源利用率，提高任務(wù)調(diào)度的效率。對比結(jié)果表明，文中算法在迭代過程中動態(tài)自適應(yīng)調(diào)整人工魚的視野和步長，加快了收斂速度，有效避免了算法陷入局部最優(yōu)解，使其求解效率更高，在優(yōu)化性能上取得了相對較好的效果。

圖3 不同任務(wù)數(shù)時，任務(wù)總完成時間比較

3）計算資源數(shù)改變，任務(wù)數(shù)相同時完成時間對比

本實驗是為了測試在任務(wù)數(shù)不變情況下，計算資源數(shù)發(fā)生變化時對調(diào)度結(jié)果的影響。文中模擬了在任務(wù)數(shù)固定為1 000，計算資源數(shù)從10變化到50的環(huán)境下，分別測試了本文算法、蟻群算法、改進遺傳算法和改進粒子群算法的任務(wù)調(diào)度總完成時間，測試結(jié)果如圖4所示。

圖4 計算資源數(shù)改變，任務(wù)完成時間的比較

從圖4中可以看出，隨著計算資源數(shù)的增加，由于任務(wù)的完成時間都在逐步減小。這是因為隨著資源節(jié)點數(shù)的擴充，對任務(wù)來說可選擇的資源范圍逐漸變大，任務(wù)對資源的競爭相對減弱，任務(wù)可以選擇性能更高的節(jié)點進行調(diào)度，進而縮短任務(wù)完成時間，在相同情況下，使用文中算法的優(yōu)勢更明顯。由于本文算法在調(diào)度的過程中，結(jié)合計算資源的性能和分布情況為依據(jù)來進行任務(wù)調(diào)度，有效的保證了資源的充分利用，很大程度的提高了任務(wù)的完成時間。

由圖3和圖4的實驗結(jié)果可以看出，無論是在任務(wù)數(shù)增加還是資源節(jié)點增加的情況下，使用文中算法進行任務(wù)調(diào)度，相比同類算法得到的總?cè)蝿?wù)完成的時間都相對較小，并且能得到較好的收斂效果。

4 結(jié)束語

文中對云計算任務(wù)調(diào)度問題進行綜合分析，針對當前云計算任務(wù)調(diào)度算法存在收斂速度慢，資源利用率不足等缺陷，利用人工魚群算法收斂速度快，對初值要求低、易于實現(xiàn)、計算簡單等優(yōu)點，提出一種云計算環(huán)境下基于改進人工魚群算法，并使用改算法對云計算任務(wù)調(diào)度問題進行優(yōu)化。在算法中自適應(yīng)調(diào)整人工魚的視野、步長和擁擠度因子，同時對覓食行為進行改進。通過仿真對比實驗可知，在相同的環(huán)境下，文中算法的收斂性和調(diào)度性能略優(yōu)于同類算法，可以在云計算環(huán)境下實現(xiàn)較為理想的任務(wù)調(diào)度結(jié)果，有效地解決云計算環(huán)境下任務(wù)調(diào)度問題。

[1]Foster I，Zhao Yong，Raicu I，et al.Cloud Computing and Grid Computing 360-degree Compared [C]//Proc.of Grid Computing Environments Workshop.Washington D.C.，USA:IEEE Computer Society，2008:1-10.

[2]Armbrust M，F(xiàn)ox A，Griffith R，et al.Above the Clouds:A Berkeley View of Cloud Computing [EB/OL].[2009-11-21].http://www.eecs.berkeley. edu/Pubs/TechRpts/2009/EECS-2009-28.pdf.

[3]李喬，鄭嘯.云計算研究現(xiàn)狀綜述[J].計算機科學(xué)，2011，38（4）:32-37

[4]Arfeen M A，Pawlikowski K，Willig A.A Framework for Resource Allocation Strategies in Cloud Computing Environment[J].Computer Software and ApplicationsConferenceWorkshops（COMPSACW），2011 IEEE 35th Annual，2011:261-266．

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

[6]Buyya R.Economic-based Distributed Resource Managementand Scheduling for Grid Computing[D]. Melbourne，Australia:Monash University，2002.

[7]魏赟，陳元元.基于改進蟻群算法的云計算任務(wù)調(diào)度模型[J].計算機工程，2015，41（2）:12-16.

[8]李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算法 [J].計算機應(yīng)用，2011，31（1）: 184-186.

[9]封良良，張?zhí)?，賈振紅，等.云計算環(huán)境下基于改進粒子群的任務(wù)調(diào)度算法[J].計算機工程，2013，39（5）：183-186.

[10]Gan Guoning，Huang Tinglei，Gao Shuai.Genetic Simulated Annealing Algorithm for Task Scheduling Based on Cloud Computing Environment[C]// Proc.of International Conference on Intelligent Computing and Integrated Systems.Guilin，China: [s.n.]，2010.

[11]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式:魚群算法[J].系統(tǒng)工程理論與實踐，2002，22（11）:32-38.

[12]李小磊.一種新型的智能優(yōu)化方法——人工魚群算法[D].杭州:浙江大學(xué)，2003.

[13]DEAN J，GH EMAWAT S.MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Symposium on Operating System Design and Implementation.New York:ACM，2004:137-150.

[14]王聯(lián)國，施秋紅.人工魚群算法的參數(shù)分析[J].計算機工程，2010，36（24）：169-171.

[15]何靜媛，鄒東升，何中市.RNA二級結(jié)構(gòu)預(yù)測的自適應(yīng)魚群算法模型[J].系統(tǒng)仿真學(xué)報，2010，22（6）: 1370-1374.

[16]Calheiros R N，Ranjan R，Beloglazov A，et al. CloudSim:a toolkit for modeling and simula-tion of cloud computing environments and evaluation of resource provisioning algorithms [J].Software: Practice and Experience，2011，41（1）:23-50.

[17]李孝宇，李濤，李鵬，等.基于自適應(yīng)人工魚群算法的大型光伏電站燃氣輪機組的優(yōu)化配置 [J].陜西電力，2013（8）：15-20.

Application of improved Artificial Fish Swarm Algorithm in cloud computing task schedule

ZHANG Xiao-li
（School of Computer，Xi'an Aerotechnical University，Xi'an 710077，China）

Tasks scheduling is an important issue to be resolved in cloud computing research.The purpose of task scheduling is to find the best optimal scheduling scheme to compute tasks efficiently. Focusing on the characteristics of resources under large scale heterogeneous in cloud computing environment，and to overcome the shortcut of the existing task scheduling algorithm，a task scheduling algorithm based on improved self-adaptive artificial fish swarm algorithm was proposed.The algorithm used the task execution time as objective function，adjusted artificial fish vision and step dynamically in iterative procedure，and improved prey behavior，to speed up the convergence rate，reduce the probability of local optimum，and improve the performance of task scheduling.Through the simulation experiment on CloudSim platform， the algorithm has obvious advantages in the task execution time and convergence speed compared to other intelligent optimization algorithms， it is an efficient task scheduling algorithm.

cloud computing；task schedule；Artificial Fish Swarm Algorithm（AFSA）；self-adaptive

TN919

：A

：1674－6236（2017）06-0014-05

2016-04-05稿件編號：201604038

陜西省網(wǎng)絡(luò)計算與安全技術(shù)重點實驗室項目（15JS078）；西安市科技計劃資助項目（CXY1518（1））

張曉麗（1980—），女，重慶人，碩士，講師。研究方向：Web服務(wù)、分布式計算。