基于粒子群優(yōu)化與蟻群優(yōu)化的云計算任務(wù)調(diào)度算法

《基于粒子群優(yōu)化與蟻群優(yōu)化的云計算任務(wù)調(diào)度算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、基于粒子群優(yōu)化與蟻群優(yōu)化的云計算任務(wù)調(diào)度算法基于粒子群優(yōu)化與蟻群優(yōu)化的云計算任務(wù)調(diào)度算法劉波濤,湖南文理學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院，湖南常德，415000；基金項(xiàng)目：湖南省教育廳高校科研項(xiàng)目（12C0822）?：在云計算環(huán)境中，存在非常多的用戶，因而系統(tǒng)處理存在非常大的任務(wù)量。為了實(shí)現(xiàn)系統(tǒng)能夠?qū)Ψ?wù)請求的高效執(zhí)行，云計算研究的重點(diǎn)問題就是任務(wù)調(diào)度問題。文章提出了一種基于粒子群優(yōu)化和蟻群優(yōu)化的任務(wù)調(diào)度算法，在CloudSim平臺進(jìn)行了仿真實(shí)驗(yàn)之后，發(fā)現(xiàn)這一算法的實(shí)時性和尋優(yōu)能力很好，是有效的調(diào)度算法。關(guān)鍵詞：粒子群優(yōu)化；蟻群優(yōu)化；云計

2、算；任務(wù)調(diào)度云計算發(fā)展融合了傳統(tǒng)計算機(jī)和X絡(luò)技術(shù)，是一種商業(yè)實(shí)現(xiàn)。基于互聯(lián)X的計算服務(wù)模式，針對一些共享可配置計算資源實(shí)現(xiàn)了方便、按需訪問；這些資源可借助非常小的管理代價或與服務(wù)提供者的交互被快速地準(zhǔn)備和實(shí)現(xiàn)按需使用[1]。目前用于求解云計算任務(wù)調(diào)度問題的算法有遺傳算法、粒子群優(yōu)化算法和蟻群算法。在前人研究的基礎(chǔ)上提出一種基于粒子群優(yōu)化與蟻群優(yōu)化的云計算任務(wù)調(diào)度算法。1云計算任務(wù)調(diào)度的設(shè)計粒子群優(yōu)化算法是1995年Kennedy和Eberhart提出的，是受啟發(fā)于鳥群覓食行為的的一種仿生優(yōu)化算法。因?yàn)樵撍惴ê唵巍⒁讓?shí)現(xiàn)且參數(shù)少，因

3、而可以實(shí)現(xiàn)良好的連續(xù)優(yōu)化和離散優(yōu)化效果。蟻群算法是上世紀(jì)90年代DorigoMacro等人提出的，受啟發(fā)于模擬螞蟻群體覓食行為，也是一種仿生優(yōu)化算法。這一算法將正反饋并行機(jī)制引進(jìn)來，魯棒性很強(qiáng)；分布式計算機(jī)制十分優(yōu)良；很容易能結(jié)合其他算法等，在一些復(fù)雜組合優(yōu)化問題的求解中被廣泛應(yīng)用。當(dāng)然這兩種算法也存在一些不足之處。本文與兩種算法的優(yōu)勢相結(jié)合，提出基于兩種算法的一種云計算任務(wù)調(diào)度算法。這一算法先是借助粒子群優(yōu)化算法的快速收斂性迅速生成初始解，接下來依據(jù)調(diào)度結(jié)果生成蟻群算法的初始信息素分布，最后是借助蟻群算法來將任務(wù)調(diào)度的最優(yōu)解求出

4、來。2．1粒子群算法云計算任務(wù)調(diào)度問題是離散問題，而粒子群優(yōu)化算法對于連續(xù)優(yōu)化問題的解決比較適用。在離散版的粒子群算法中，將粒子位置向量每一位值取0或1，粒子速度不是對連續(xù)空間中粒子飛行的速度的表示，而且表示計算粒子位置向量取值為0或1的概率。2．2蟻群算法以云計算任務(wù)調(diào)度的任務(wù)與資源分配關(guān)系矩陣X為參照，定義{xij}m×n為節(jié)點(diǎn)集，組成一個無向完全圖G(V，E)。通過蟻群算法從集合{xij}m×n中選出一組節(jié)點(diǎn){xy11，xy22，…，xyjj，…，xynn}，yj∈{1，2，…，m}，從而實(shí)現(xiàn)最小的Cmax值。2．3算法流程

5、在粒子群優(yōu)化和蟻群優(yōu)化基礎(chǔ)上提出的云計算任務(wù)調(diào)度算法，其基本步驟是這樣的:?Step1對云計算任務(wù)調(diào)度目標(biāo)函數(shù)進(jìn)行定義。Step2針對該調(diào)度算法，進(jìn)行相關(guān)參數(shù)和算法結(jié)束條件的設(shè)定。Step3隨即初始化粒子群的位置和速度。Step4對每個粒子的適應(yīng)值進(jìn)行計算，將粒子個體最優(yōu)位置和群體最優(yōu)位置找出來。Step5按照式(6)、式(7)來更新粒子速度和位置。Step6沒有動作。Step7若是已達(dá)設(shè)定迭代次數(shù)，將云計算任務(wù)調(diào)度的初始調(diào)度結(jié)果輸出，并轉(zhuǎn)到Step8。要不然就跳轉(zhuǎn)至Step4。.17.Step8按照粒子群算法得出的初始調(diào)度結(jié)果來

6、初始化蟻群算法的信息素進(jìn)。Step9隨機(jī)放置若干只螞蟻到節(jié)點(diǎn)上并搜索。Step10每只螞蟻按照式(8)進(jìn)行下一節(jié)點(diǎn)的選擇，并按照式(10)、式(11)對局部信息素進(jìn)行更新，將調(diào)度列表中加入所選節(jié)點(diǎn)。Step11完成全部任務(wù)調(diào)度后，按照任務(wù)調(diào)度列表對調(diào)度結(jié)果的適應(yīng)值進(jìn)行計算，同時按照式(12)、式(13)對全局信息素進(jìn)行更新。2實(shí)驗(yàn)與分析CloudSim是澳大利亞RajkumarBuyya博士領(lǐng)導(dǎo)團(tuán)隊開發(fā)出來的一個云計算仿真平臺。其主要是對云環(huán)境進(jìn)行模擬，針對不同的調(diào)度策略做性能測試。本文也是采用CloudSim平臺來進(jìn)行云環(huán)境的模

7、擬，對任務(wù)調(diào)度算法進(jìn)行模擬仿真。為了對本文調(diào)度算法的性能進(jìn)行有效檢驗(yàn)，分別于5個虛擬計算資源、50個子任務(wù)和5個虛擬計算資源、500個子任務(wù)兩種調(diào)度規(guī)模下，分別進(jìn)行對比實(shí)驗(yàn)，包括粒子群優(yōu)化算法(PSO)、蟻群算法(ACO)和本文算法(PSO-ACO)[2]。在實(shí)驗(yàn)中，各虛擬計算資源的處理能力是{400MIPs，600MIPs，800MIPs，1000MIPs，1200MIPs}；子任務(wù)長度范圍是[400MI，1000MI］[3]。分別對算法的參數(shù)進(jìn)行設(shè)置:本文算法的粒子群算法部分，群體規(guī)模size=100，c1=c2=2，迭代次數(shù)

8、為40，蟻群算法部分，群體規(guī)模size=100，α=1，β=1，ρ=0．2，迭代次數(shù)為160。粒子群算法、蟻群算法的參數(shù)與以上分別對應(yīng)相同，迭代次數(shù)是200。對各算法進(jìn)行了20次重復(fù)運(yùn)行。最終的實(shí)驗(yàn)結(jié)果見圖1和圖2。?圖1總?cè)蝿?wù)完成時間曲線(5個資