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

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

當前，云計算資源最常用的調(diào)度策略是按需分配，根據(jù)用戶需求對所申請資源進行按需分配與管理[1]。云計算的發(fā)展日趨成熟，對性能要求也不斷提高，在當前的背景下，性能的改善所面臨的問題也日趨增加。在云計算系統(tǒng)應(yīng)用中，云資源本身呈現(xiàn)動態(tài)變化，但如何進行資源調(diào)度分配已經(jīng)成為云計算系統(tǒng)應(yīng)用的核心機制，這也是云計算資源調(diào)度中研究的關(guān)鍵問題。就目前而言，許多網(wǎng)格計算研究領(lǐng)域提出的都是靜態(tài)資源調(diào)度方法研究，許多靜態(tài)調(diào)度資源算法并不能很好地對云計算資源調(diào)度。并且隨著云規(guī)模的逐漸變大，云拓撲結(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)注。文獻[2]提出了間接編碼方式選取作業(yè)任務(wù)平均完成時間，通過建立適應(yīng)度函數(shù)和蟻群信息素分布生成的最優(yōu)解，解決蟻群算法中信息素缺乏而導(dǎo)致求解速度慢的問題；文獻[3]提出一種基于蟻群優(yōu)化的任務(wù)負載均衡調(diào)度算法，根據(jù)虛擬機中信息素揮發(fā)因子來改進信息素的更新規(guī)則，并通過WLB-ACO合理分配任務(wù)，使系統(tǒng)中任務(wù)集完成時間最短并且達到負載均衡狀態(tài)；文獻[4]提出了一種動態(tài)趨勢預(yù)測蟻群算法，主要是動態(tài)趨勢預(yù)測和蟻群算法相結(jié)合的一種實施過程，解決資源調(diào)度中資源占用率過多及響應(yīng)時間過長等問題，從而提高了數(shù)據(jù)中心的性能，加強響應(yīng)速度以及數(shù)據(jù)計算精確度；文獻[5]提出一種雙適應(yīng)度動態(tài)遺傳調(diào)度策略，該策略通過使用改進種群迭代方法來改善云環(huán)境下資源調(diào)度系統(tǒng)的性能問題，使改進后的遺傳算法在資源調(diào)度上具有有效性，從而在處理大規(guī)模數(shù)據(jù)集時能夠做出快速、有效的反應(yīng)。但以上研究方法策略并沒有解決本文提出的問題，所以為了解決云環(huán)境下動態(tài)資源調(diào)度問題，文章從全局尋址最佳路徑出發(fā)，找出一種關(guān)于資源調(diào)度路徑最佳、性能最優(yōu)、尋址時間最短的策略方法。

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

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

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

目前求解資源調(diào)度問題常用的編碼方法包括路徑編碼、對比編碼、實施編碼、二進制編碼等[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ù)通過合法染色體算法進行初始化。具體算法為

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

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

（3）隨機從 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ù)?；舅枷刖褪翘摂M機環(huán)境下作業(yè)調(diào)度任務(wù)要走完所有路程，作業(yè)任務(wù)尋找最優(yōu)解的過程就是找出最優(yōu)路徑的遍歷過程。

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

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

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

蟻群算法中資源調(diào)度問題通過信息素反映虛擬機對路徑選擇的改進程度[15-17]。資源調(diào)度尋址最優(yōu)路徑的過程即虛擬機尋找最短路徑的過程。假設(shè)有N臺虛擬機從作業(yè)節(jié)點A開始尋找最佳路徑，那么各臺虛擬機選擇下一個作業(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的虛擬機k選擇目標作業(yè)節(jié)點j的概率為

式中：α為軌跡的啟發(fā)因子；β為期望啟發(fā)因子；allowedk為螞蟻k下一步允許選擇的城市。對于式（1），虛擬機每調(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)值來確定對該個體選擇生存的幾率，由虛擬機個數(shù)設(shè)置主群體大小為N，染色體個體i的適應(yīng)值為fi，則所有染色體適應(yīng)值總和為∑fi，對于隨機數(shù)r來講，，…，n，說明染色體個體從 k 開始被選中，直到選出n個染色體個體。

選出染色體個體之后通過動態(tài)ACO_GA解決作業(yè)調(diào)度問題，需要采用路徑編碼方式，使染色體在進行交叉操作后會產(chǎn)生一個調(diào)度問題完全圖，前提必須對作業(yè)調(diào)度訪問一次，如果染色體產(chǎ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)隨機數(shù)，2個變異點對應(yīng)的基因?qū)Q生成最終的作業(yè)調(diào)度最佳路徑尋址路線。

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

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

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

設(shè)一個虛擬云實驗室終端服務(wù)器50為例，即種群規(guī)模為50，標準遺傳算法交叉概率為0.8，變異概率為0.1，啟發(fā)因子 α=1.5，期望啟發(fā)因子β=1.8，任務(wù)數(shù)量m=45，信息素揮發(fā)因子ρ=0.5，取迭代次數(shù)為10000代終止，在動態(tài)ACO_GA中取ζ=1。虛擬環(huán)境下ACO_GA改進前最短距離權(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臺虛擬機任一臺在虛擬云環(huán)境下調(diào)度作業(yè)節(jié)點都會隨機生成45個節(jié)點位置，舉例某一臺虛擬機調(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)度路徑一種可行解，隨機動態(tài)調(diào)度路徑如圖5所示。

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

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

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

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

4.2 實驗總結(jié)

由以上實驗結(jié)果可知，本文算法結(jié)合遺傳算法中路徑編碼方法，并繼承了蟻群算法通過信息素留下的最佳調(diào)度路徑種子節(jié)點。算法隨著迭代次數(shù)的不斷增多，其路徑收斂性不斷增強，調(diào)度路徑最優(yōu)化效果更加明顯，測試過程證明了算法的有效性。ACO_GA交叉調(diào)度策略在最佳路徑收斂、最短路徑尋址等方面優(yōu)勢較為明顯，進一步驗證了虛擬云環(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)度效率，具有較好的使用價值。但本文模擬云平臺上虛擬機數(shù)量有限，通常為一個教學(xué)實驗室服務(wù)器數(shù)量，而現(xiàn)今虛擬機群下要想達到最佳調(diào)度路徑收斂、路徑最短，在考慮虛擬機群規(guī)模擴大的同時還要考慮硬件設(shè)備，以及對虛擬機的快速部署等問題。由此可知動態(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].計算機工程與應(yīng)用，2014，50（6）：51-55.

[3]趙夢，李蜀瑜.云計算環(huán)境下基于蟻群優(yōu)化的任務(wù)負載均衡調(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].計算機工程與應(yīng)用，2015，51（6）：84-88.

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

[7]劉峰，畢利，楊軍.一種用于云計算資源調(diào)度的改進遺傳算法[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].計算機工程與設(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].計算機科學(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.