云環(huán)境下基于動態(tài)蟻群遺傳算法的調(diào)度方法研究

尚志會 ，張建偉 ，蔡增玉 ，馬琳琳

（1.鄭州輕工業(yè)學(xué)院 計算機(jī)與通信工程學(xué)院，鄭州 450002；2.鄭州輕工業(yè)學(xué)院 軟件學(xué)院，鄭州 450002）

當(dāng)前，云計算資源最常用的調(diào)度策略是按需分配，根據(jù)用戶需求對所申請資源進(jìn)行按需分配與管理[1]。云計算的發(fā)展日趨成熟，對性能要求也不斷提高，在當(dāng)前的背景下，性能的改善所面臨的問題也日趨增加。在云計算系統(tǒng)應(yīng)用中，云資源本身呈現(xiàn)動態(tài)變化，但如何進(jìn)行資源調(diào)度分配已經(jīng)成為云計算系統(tǒng)應(yīng)用的核心機(jī)制，這也是云計算資源調(diào)度中研究的關(guān)鍵問題。就目前而言，許多網(wǎng)格計算研究領(lǐng)域提出的都是靜態(tài)資源調(diào)度方法研究，許多靜態(tài)調(diào)度資源算法并不能很好地對云計算資源調(diào)度。并且隨著云規(guī)模的逐漸變大，云拓?fù)浣Y(jié)構(gòu)越來越復(fù)雜，云計算資源調(diào)度領(lǐng)域中如何通過改善動態(tài)尋址方法來提升云任務(wù)調(diào)度應(yīng)用也是研究領(lǐng)域中的一個重要問題。通過模擬蟻群算法能夠解決全局搜索最佳狀態(tài)，但任務(wù)資源調(diào)度效率并沒有很大的提高，為了解決最佳路徑尋址問題，提高資源調(diào)度系統(tǒng)尋址收斂性便可節(jié)約時間。

近年來，在虛擬云計算領(lǐng)域，云調(diào)度智能算法的使用受到高度關(guān)注。文獻(xiàn)[2]提出了間接編碼方式選取作業(yè)任務(wù)平均完成時間，通過建立適應(yīng)度函數(shù)和蟻群信息素分布生成的最優(yōu)解，解決蟻群算法中信息素缺乏而導(dǎo)致求解速度慢的問題；文獻(xiàn)[3]提出一種基于蟻群優(yōu)化的任務(wù)負(fù)載均衡調(diào)度算法，根據(jù)虛擬機(jī)中信息素?fù)]發(fā)因子來改進(jìn)信息素的更新規(guī)則，并通過WLB-ACO合理分配任務(wù)，使系統(tǒng)中任務(wù)集完成時間最短并且達(dá)到負(fù)載均衡狀態(tài)；文獻(xiàn)[4]提出了一種動態(tài)趨勢預(yù)測蟻群算法，主要是動態(tài)趨勢預(yù)測和蟻群算法相結(jié)合的一種實施過程，解決資源調(diào)度中資源占用率過多及響應(yīng)時間過長等問題，從而提高了數(shù)據(jù)中心的性能，加強(qiáng)響應(yīng)速度以及數(shù)據(jù)計算精確度；文獻(xiàn)[5]提出一種雙適應(yīng)度動態(tài)遺傳調(diào)度策略，該策略通過使用改進(jìn)種群迭代方法來改善云環(huán)境下資源調(diào)度系統(tǒng)的性能問題，使改進(jìn)后的遺傳算法在資源調(diào)度上具有有效性，從而在處理大規(guī)模數(shù)據(jù)集時能夠做出快速、有效的反應(yīng)。但以上研究方法策略并沒有解決本文提出的問題，所以為了解決云環(huán)境下動態(tài)資源調(diào)度問題，文章從全局尋址最佳路徑出發(fā)，找出一種關(guān)于資源調(diào)度路徑最佳、性能最優(yōu)、尋址時間最短的策略方法。

為了解決云環(huán)境下資源調(diào)度問題，上述參考文獻(xiàn)雖然都是從不同角度來解決動態(tài)資源調(diào)度問題，但上述策略方法沒有從尋址路徑出發(fā)找出最佳路徑解決資源調(diào)度問題。為了尋找最佳路徑來縮短尋址時間和提高系統(tǒng)性能，可以從研究資源動態(tài)調(diào)度問題入手，提出一種云環(huán)境下基于動態(tài)蟻群算法與遺傳算法相結(jié)合的調(diào)度方法研究策略。從而可以在資源動態(tài)調(diào)度問題進(jìn)行優(yōu)化求解，更加逼近現(xiàn)實問題。

1 動態(tài)蟻群遺傳算法編碼方式原理

首先，尋址問題也是組合優(yōu)化問題，組合優(yōu)化問題也是運籌學(xué)領(lǐng)域中一個關(guān)鍵性的分支，組合優(yōu)化問題形式簡單、易于理解，其算法與驗證平臺被廣泛研究與應(yīng)用[6-8]。TSP問題主要描述某一個旅行商人想要到達(dá)的城市有n座，要走完這n座城市并且每個城市只能到達(dá)1次，最后還要回到原來出發(fā)點城市，根據(jù)路徑的選擇目標(biāo)為要求得到的路徑路程是所有走一遍路徑路程的最小值[9-10]。

目前求解資源調(diào)度問題常用的編碼方法包括路徑編碼、對比編碼、實施編碼、二進(jìn)制編碼等[11]。文章采用動態(tài)蟻群算法與遺傳算法結(jié)合求解路徑選擇問題，蟻群遺傳算法（ACO_GA）求解路徑問題最常用的編碼方式為路徑編碼方法。使用該編碼方法，直接可以在抽象路徑問題上直接編碼，無須變換路徑圖，并且直接在算法調(diào)度遺傳算法時直接利用遺傳算法留下的任務(wù)即可，減少算法編碼工作量。路徑編碼是通過對任務(wù)訪問順序的一種排列編碼方式，是符合邏輯算法的，除非給定尋址路線，否則這種尋址編碼方式不具有唯一性。

假如一個調(diào)度任務(wù)與已經(jīng)放入編碼鏈中的任務(wù)之間存在調(diào)度路徑，則說明此任務(wù)為可編碼任務(wù)，否則不成立。所有可編碼任務(wù)集合稱為可編碼任務(wù)集，調(diào)度任務(wù)通過合法染色體算法進(jìn)行初始化。具體算法為

（1）初始化，對任務(wù)進(jìn)行編碼，形成編碼任務(wù)集；

（2）根據(jù)可編碼任務(wù)的編碼集生成可編碼集Line；

（3）隨機(jī)從 Line中找出一個任務(wù)放入編碼鏈并重新構(gòu)造編碼任務(wù)集；

（4）如果編碼集返回值為空則結(jié)束；否則返回（3）繼續(xù)重構(gòu)編碼集；

由理論分析可知，動態(tài)編碼ACO_GA流程如圖1所示。

圖1 動態(tài)編碼算法流程Fig.1 Process of dynamic coding algorithm

2 算法初始化及參數(shù)介紹

本動態(tài)ACO_GA框架主要根據(jù)最佳融合點之間的調(diào)度算法，通過使用蟻群算法中根據(jù)信息素求出的最佳解作為遺傳算法中的種子任務(wù)來優(yōu)化遺傳操作初始任務(wù)種群[12]。所以采用動態(tài)ACO_GA來解決云計算中調(diào)度路徑最佳路徑選擇問題是根據(jù)蟻群算法中螞蟻來提供初始解的任務(wù)。基本思想就是虛擬機(jī)環(huán)境下作業(yè)調(diào)度任務(wù)要走完所有路程，作業(yè)任務(wù)尋找最優(yōu)解的過程就是找出最優(yōu)路徑的遍歷過程。

作業(yè)調(diào)度初始化首先根據(jù)虛擬云環(huán)境下隨機(jī)調(diào)度作業(yè)任務(wù)[13-14]，然后根據(jù)判斷狀態(tài)專業(yè)概率從可編碼的作業(yè)任務(wù)去尋找下一個作業(yè)任務(wù)，直到遍歷完所有的作業(yè)任務(wù)節(jié)點。可編碼任務(wù)主要根據(jù)未選擇作業(yè)節(jié)點和已經(jīng)放入編碼鏈中的作業(yè)之間存在路徑，并且路徑根據(jù)尋址過程弧來進(jìn)行判斷。

設(shè)有作業(yè)任務(wù) A、B、C、D、E、F、G， 某虛擬機(jī)要從作業(yè)節(jié)點C出發(fā)，則作業(yè)任務(wù)的下一步可編碼任務(wù)集為｛A，B，D，E，F(xiàn)，G｝，隨后的每一步都要在剩下的作業(yè)節(jié)點中根據(jù)概率專業(yè)公式計算得到要選擇的下一個作業(yè)節(jié)點。虛擬機(jī)的每一步選擇都要根據(jù)它本身tabu算法集合和調(diào)度問題本身所需要的集合。對任一個虛擬機(jī)N，設(shè)MN為將要訪問作業(yè)任務(wù)節(jié)點的集合，GN為下一步訪問任務(wù)的集合。初始化令 MN=｛A，B，C，D，E，F(xiàn)，G｝，GN=｛A，B，C，D，E，F(xiàn)，G｝。虛擬機(jī)N選擇一個節(jié)點m以后，該節(jié)點添加到tabu算法集合中，同時在MN刪除該節(jié)點，根據(jù)該節(jié)點與其他任務(wù)之間的弧來更新GN集合，則虛擬機(jī)在選擇下一個作業(yè)節(jié)點時要從GN集合中選擇，重復(fù)操作以上過程，直至MN為空為止。此時，虛擬機(jī)N的tabu算法集合中節(jié)點序列就是蟻群算法的一個解，設(shè)蟻群算法一個解為｛｝，則虛擬機(jī)調(diào)度作業(yè)任務(wù)走過的路徑如圖2所示。

圖2 虛擬機(jī)選擇路徑示意Fig.2 Schematic diagram of virtual machine path selection

蟻群算法中資源調(diào)度問題通過信息素反映虛擬機(jī)對路徑選擇的改進(jìn)程度[15-17]。資源調(diào)度尋址最優(yōu)路徑的過程即虛擬機(jī)尋找最短路徑的過程。假設(shè)有N臺虛擬機(jī)從作業(yè)節(jié)點A開始尋找最佳路徑，那么各臺虛擬機(jī)選擇下一個作業(yè)節(jié)點的依據(jù)有以下要求，首先通過τij（t）表示t時刻連接作業(yè)i與作業(yè)j之間路徑上殘留信息素濃度，ηij（t）表示由作業(yè)調(diào)度任務(wù) i轉(zhuǎn)移到作業(yè) j的啟發(fā)因子信息，ηij（t）=1/dij，該啟發(fā)因子信息由資源調(diào)度問題給出，dij為2個作業(yè)之間的路徑長度。

t時刻在作業(yè)i的虛擬機(jī)k選擇目標(biāo)作業(yè)節(jié)點j的概率為

式中：α為軌跡的啟發(fā)因子；β為期望啟發(fā)因子；allowedk為螞蟻k下一步允許選擇的城市。對于式（1），虛擬機(jī)每調(diào)度一次作業(yè)節(jié)點就會更新一次信息素。初始狀態(tài)時信息素設(shè)置為 Q［i］［j］=C，C 為常數(shù)，根據(jù)動態(tài)ACO_GA思想可知，通過分別使用蟻群算法的解和全局路徑最優(yōu)解，以及每次遺傳算法的最優(yōu)路徑解來更新信息素，如式（2）所示：

3 蟻群遺傳算法交叉混合策略操作

根據(jù)遺傳算法中染色體適應(yīng)值來確定對該個體選擇生存的幾率，由虛擬機(jī)個數(shù)設(shè)置主群體大小為N，染色體個體i的適應(yīng)值為fi，則所有染色體適應(yīng)值總和為∑fi，對于隨機(jī)數(shù)r來講，，…，n，說明染色體個體從 k 開始被選中，直到選出n個染色體個體。

選出染色體個體之后通過動態(tài)ACO_GA解決作業(yè)調(diào)度問題，需要采用路徑編碼方式，使染色體在進(jìn)行交叉操作后會產(chǎn)生一個調(diào)度問題完全圖，前提必須對作業(yè)調(diào)度訪問一次，如果染色體產(chǎn)生非法解個體時，則需要人工進(jìn)行調(diào)整操作。

文章所列舉的7個作業(yè)調(diào)度交叉調(diào)度后，每組會產(chǎn)生一個非法染色體解，需要人工調(diào)整，待調(diào)整2個變異點后會產(chǎn)生一個新的賦值完全圖。對變異的數(shù)值按照概率對換相應(yīng)位置，隨后產(chǎn)生對應(yīng)隨機(jī)數(shù)，2個變異點對應(yīng)的基因?qū)Q生成最終的作業(yè)調(diào)度最佳路徑尋址路線。

4 仿真實驗結(jié)果與分析

4.1 算法實現(xiàn)的平臺和參數(shù)設(shè)置

為了進(jìn)一步對云環(huán)境下ACO_GA進(jìn)行合理有效的驗證，文章通過在模擬云平臺CloudSim上對其進(jìn)行仿真實驗，比較原始蟻群算法與交叉算法調(diào)度策略在調(diào)度問題上的應(yīng)用。使用云平臺需要對其環(huán)境進(jìn)行配置，數(shù)據(jù)中心將會根據(jù)用戶所使用的調(diào)度策略提前把作業(yè)任務(wù)綁定到相應(yīng)的虛擬機(jī)，而后虛擬機(jī)依次開始執(zhí)行作業(yè)任務(wù)。

設(shè)一個虛擬云實驗室終端服務(wù)器50為例，即種群規(guī)模為50，標(biāo)準(zhǔn)遺傳算法交叉概率為0.8，變異概率為0.1，啟發(fā)因子 α=1.5，期望啟發(fā)因子β=1.8，任務(wù)數(shù)量m=45，信息素?fù)]發(fā)因子ρ=0.5，取迭代次數(shù)為10000代終止，在動態(tài)ACO_GA中取ζ=1。虛擬環(huán)境下ACO_GA改進(jìn)前最短距離權(quán)值和為497.4831，如圖3所示。

圖3 蟻群算法最佳調(diào)度路徑Fig.3 Optimal path of ACO scheduling

基于動態(tài)ACO_GA調(diào)度作業(yè)節(jié)點最佳路徑求解結(jié)果為不定解，但該算法所求解都優(yōu)于蟻群算法路徑調(diào)度最佳解。因此50臺虛擬機(jī)任一臺在虛擬云環(huán)境下調(diào)度作業(yè)節(jié)點都會隨機(jī)生成45個節(jié)點位置，舉例某一臺虛擬機(jī)調(diào)度作業(yè)節(jié)點位置如圖4所示。

遺傳算法在選取最佳種子節(jié)點后再不斷地迭代、不斷尋優(yōu)，最后在虛擬云環(huán)境下根據(jù)圖4作業(yè)節(jié)點位置所對應(yīng)的ACO_GA交叉調(diào)度策略最佳路徑加權(quán)路徑值和為457.7451。經(jīng)過遺傳算法得到的作業(yè)調(diào)度路徑一種可行解，隨機(jī)動態(tài)調(diào)度路徑如圖5所示。

圖4 隨機(jī)作業(yè)節(jié)點位置Fig.4 Situation of random assignment node

圖5 隨機(jī)動態(tài)路徑節(jié)點Fig.5 Diagram of stochastic dynamic node

蟻群算法尋址最優(yōu)路徑節(jié)點為遺傳算法種子節(jié)點，通過利用編碼方式對種子節(jié)點進(jìn)行迭代，迭代次數(shù)不斷增加預(yù)期達(dá)到一個收斂適應(yīng)度曲線。當(dāng)?shù)螖?shù)達(dá)到1200次以上已經(jīng)達(dá)到收斂解。ACO_GA適應(yīng)度收斂曲線如圖6所示。

圖6 ACO_GA收斂曲線Fig.6 Convergence curves of ACO_GA

4.2 實驗總結(jié)

由以上實驗結(jié)果可知，本文算法結(jié)合遺傳算法中路徑編碼方法，并繼承了蟻群算法通過信息素留下的最佳調(diào)度路徑種子節(jié)點。算法隨著迭代次數(shù)的不斷增多，其路徑收斂性不斷增強(qiáng)，調(diào)度路徑最優(yōu)化效果更加明顯，測試過程證明了算法的有效性。ACO_GA交叉調(diào)度策略在最佳路徑收斂、最短路徑尋址等方面優(yōu)勢較為明顯，進(jìn)一步驗證了虛擬云環(huán)境下該算法在資源調(diào)度問題上的有效性。

5 結(jié)語

本文提出一種云環(huán)境下基于動態(tài)蟻群遺傳算法交叉調(diào)度策略方法。通過對比原始動態(tài)遺傳算法與動態(tài)蟻群算法和遺傳算法相結(jié)合的算法發(fā)現(xiàn)，混合算法交叉調(diào)度策略與其他策略相比在調(diào)度路徑收斂性與尋址最短路徑問題上效果較為明顯，將動態(tài)蟻群算法尋址最佳調(diào)度路徑節(jié)點作為遺傳算法的種子節(jié)點的同時，利用路徑編碼方式對其求解。通過2種算法所求最佳路徑權(quán)值和對比發(fā)現(xiàn)，混合交叉算法可以顯著提高云環(huán)境下資源調(diào)度效率，具有較好的使用價值。但本文模擬云平臺上虛擬機(jī)數(shù)量有限，通常為一個教學(xué)實驗室服務(wù)器數(shù)量，而現(xiàn)今虛擬機(jī)群下要想達(dá)到最佳調(diào)度路徑收斂、路徑最短，在考慮虛擬機(jī)群規(guī)模擴(kuò)大的同時還要考慮硬件設(shè)備，以及對虛擬機(jī)的快速部署等問題。由此可知動態(tài)蟻群遺傳算法在虛擬云環(huán)境下調(diào)度問題研究還處于初級階段，還有很多問題有待研究與解決。

[1]Dorigo M，Blum C.Ant colony optimization theory：A survey[J].International Journal of Productivity& Performance Management，2010，59（2）：811-828.

[2]張雨，李芳，周濤.云計算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[J].計算機(jī)工程與應(yīng)用，2014，50（6）：51-55.

[3]趙夢，李蜀瑜.云計算環(huán)境下基于蟻群優(yōu)化的任務(wù)負(fù)載均衡調(diào)度算法[J].電子設(shè)計工程，2016，24（8）：30-33.

[4]嵇可可.基于動態(tài)趨勢預(yù)測蟻群算法的云計算資源調(diào)度優(yōu)化研究[J].科技通報，2016，32（1）：187-190.

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

[6]張寧.基于自適應(yīng)蟻群算法的云計算任務(wù)調(diào)度研究[D].大連理工大學(xué)，2015.

[7]劉峰，畢利，楊軍.一種用于云計算資源調(diào)度的改進(jìn)遺傳算法[J].計算機(jī)測量與控制，2016（5）：202-206.

[8]Ullman J D.NP-complete scheduling problems[J].Journal of Computer&System Sciences，1975，10（3）：384-393.

[9]Li K，Xu G，Zhao G，et al.Cloud task scheduling based on load balancing ant colony optimization[C]//Chinagrid Conference，Dalian，201：3-9.

[10]鐘瀟柔.基于動態(tài)遺傳算法的云計算任務(wù)節(jié)能調(diào)度策略研究[D].哈爾濱工業(yè)大學(xué)，2015.

[11]李悅喬，康立山，李程俊.求解TSP問題的實數(shù)編碼演化算法[J].計算機(jī)工程與設(shè)計，2007，28（19）：4592-4594.

[12]梁旭，黃明，寧濤，等.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京：電子工業(yè)出版社，2014：110-114.

[13]趙宏偉，李圣普.基于粒子群算法和RBF神經(jīng)網(wǎng)絡(luò)的云計算資源調(diào)度方法研究[J].計算機(jī)科學(xué)，2016，43（3）：113-117.

[14]Zhang J W，Shang Z H，Yuan C，et al.Research and progress on virtual cloud laboratory[C]//2016 International Conference on Electronic，Information and Computer Engineering，Hongkong，2016：1-6.

[15]Karaboga D，Gorkemli B，Ozturk C，et al.A comprehensive survey：artificial bee colony （ABC）algorithm and applications[J].Artificial Intelligence Review，2014，42（1）：21-57.

[16]Li D，Meng X，Li M，et al.An ACO-based intercell scheduling approach for job shop cells with multiple single processing machines and one batch processing machine[J].Journal of Intelligent Manufacturing，2014，27（2）：1-14.

[17]Fouad A，Boukhetala D，Boudjema F，et al.A novel global harmony search method based on ant colony optimisation algorithm[J].Journal of Experimental&Theoretical Artificial Intelligence，2015，28（1）：215-238.