云環境下基于動態蟻群遺傳算法的調度方法研究

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

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

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

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

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

1 動態蟻群遺傳算法編碼方式原理

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

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

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

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

（2）根據可編碼任務的編碼集生成可編碼集Line；

（3）隨機從 Line中找出一個任務放入編碼鏈并重新構造編碼任務集；

（4）如果編碼集返回值為空則結束；否則返回（3）繼續重構編碼集；

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

圖1 動態編碼算法流程Fig.1 Process of dynamic coding algorithm

2 算法初始化及參數介紹

本動態ACO_GA框架主要根據最佳融合點之間的調度算法，通過使用蟻群算法中根據信息素求出的最佳解作為遺傳算法中的種子任務來優化遺傳操作初始任務種群[12]。所以采用動態ACO_GA來解決云計算中調度路徑最佳路徑選擇問題是根據蟻群算法中螞蟻來提供初始解的任務?；舅枷刖褪翘摂M機環境下作業調度任務要走完所有路程，作業任務尋找最優解的過程就是找出最優路徑的遍歷過程。

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

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

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

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

t時刻在作業i的虛擬機k選擇目標作業節點j的概率為

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

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

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

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

文章所列舉的7個作業調度交叉調度后，每組會產生一個非法染色體解，需要人工調整，待調整2個變異點后會產生一個新的賦值完全圖。對變異的數值按照概率對換相應位置，隨后產生對應隨機數，2個變異點對應的基因對換生成最終的作業調度最佳路徑尋址路線。

4 仿真實驗結果與分析

4.1 算法實現的平臺和參數設置

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

設一個虛擬云實驗室終端服務器50為例，即種群規模為50，標準遺傳算法交叉概率為0.8，變異概率為0.1，啟發因子 α=1.5，期望啟發因子β=1.8，任務數量m=45，信息素揮發因子ρ=0.5，取迭代次數為10000代終止，在動態ACO_GA中取ζ=1。虛擬環境下ACO_GA改進前最短距離權值和為497.4831，如圖3所示。

圖3 蟻群算法最佳調度路徑Fig.3 Optimal path of ACO scheduling

基于動態ACO_GA調度作業節點最佳路徑求解結果為不定解，但該算法所求解都優于蟻群算法路徑調度最佳解。因此50臺虛擬機任一臺在虛擬云環境下調度作業節點都會隨機生成45個節點位置，舉例某一臺虛擬機調度作業節點位置如圖4所示。

遺傳算法在選取最佳種子節點后再不斷地迭代、不斷尋優，最后在虛擬云環境下根據圖4作業節點位置所對應的ACO_GA交叉調度策略最佳路徑加權路徑值和為457.7451。經過遺傳算法得到的作業調度路徑一種可行解，隨機動態調度路徑如圖5所示。

圖4 隨機作業節點位置Fig.4 Situation of random assignment node

圖5 隨機動態路徑節點Fig.5 Diagram of stochastic dynamic node

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

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

4.2 實驗總結

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

5 結語

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

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

[2]張雨，李芳，周濤.云計算環境下基于遺傳蟻群算法的任務調度研究[J].計算機工程與應用，2014，50（6）：51-55.

[3]趙夢，李蜀瑜.云計算環境下基于蟻群優化的任務負載均衡調度算法[J].電子設計工程，2016，24（8）：30-33.

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

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

[6]張寧.基于自適應蟻群算法的云計算任務調度研究[D].大連理工大學，2015.

[7]劉峰，畢利，楊軍.一種用于云計算資源調度的改進遺傳算法[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]鐘瀟柔.基于動態遺傳算法的云計算任務節能調度策略研究[D].哈爾濱工業大學，2015.

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

[12]梁旭，黃明，寧濤，等.現代智能優化混合算法及其應用[M].北京：電子工業出版社，2014：110-114.

[13]趙宏偉，李圣普.基于粒子群算法和RBF神經網絡的云計算資源調度方法研究[J].計算機科學，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.