基于蟻群算法的云計算自適應任務調度研究

柴旭清 董永亮

摘 要：為了解決蟻群算法在解決云計算中大規模任務調度問題時收斂速度較慢且易陷入局部最優解的缺陷，設計了一種基于蟻群算法的云計算自適應任務調度算法，該算法在多態蟻群算法的基礎上加入了信息素自適應更新調整機制，用來提高算法的收斂速度，有效地避免的局部最優解的出現。實驗數據表明，在解決大規模任務調度問題時本文算法性能更好。

【關鍵詞】云計算 任務調度 蟻群算法 自適應

1 自適應任務調度算法

1.1 信息素初始化

將螞蟻分為兩類：偵查螞蟻和搜索螞蟻。前者以每個城市為活動中心，僅在城市附近進行局域搜索，并將結果用偵查素標記，對搜索螞蟻提供輔助作用；后者進行全局搜索，當到達一個新的城市后，根據該城市的周邊城市偵查素和前輩螞蟻釋放信息素來選擇下一個旅游城市，直到選出最佳路徑。

1.1.1 偵查螞蟻

由于在現實中可能會出現服務器j的剩余性能無法滿足任務i性能要求的情況，因此需要優化傳統的多態蟻群算法的偵查素生成方式，使城市i和城市j之間是非連通的，具體生成方式如下：

每個城市布置一只偵查螞蟻，并偵查剩余（m-1）個城市信息，將結果與先驗知識結合生成偵查素s[i][j]，標記路徑Lij上。

1.1.2 搜索螞蟻

搜索螞蟻負責全局搜索工作，在時刻t，城市i中的搜索螞蟻k通過路徑Lij轉移到城市j的概率計算如下：

allowedk是未被螞蟻k訪問的城市，即螞蟻k的禁忌表。

由公式（1）（2）可知，若存在服務器seri無法滿足任務tj的性能需求，則該節點上的偵查素s[i][j]=0，即在初始狀態下，城市i無法到達城市j，保證在蟻群算法的首次迭代中不會將任務tj分配到服務器seri上。

由公式（3）可知，當搜索螞蟻在到達一個新城市時，結合該城市偵查素將縮小下一城市的搜索規模，加快了收斂速度。

1.2 信息素更新規則

信息素更新分為信息素局部更新和信息素全局更新。

1.2.1 局部更新

局部更新是指單一螞蟻在一次迭代過程中選定下一個目標城市后，立即更新該城市的信息素，而不影響此次迭代過程中其他并行螞蟻及其后續螞蟻的路徑選擇，具體更新公式如下：

1.2.2 全局更新

信息素的全局更新是指在蟻群算法在進行一次迭代后，對出現在迭代最優解的螞蟻所經的路徑上所有城市的信息素進行更新，具體更新公式如下：

其中，MAT（z）表示在第z次迭代中搜索發現的最優解的匹配距離。

為保證不出現將任務tj調度到不滿足需求的服務器seri上，在每次迭代后需要對所有城市的信息素進行修正，公式如下：

2 性能測試

通過matlab對本文算法和傳統蟻群算法進行仿真分析，在仿真過程中分別將等待調度的任務總數和服務器總數為Num=100，200，信息素啟發參數α和視界啟發參數β分別為α=1，β=2及α=5，β=10、信息素揮發參數ρ=0.5、螞蟻總數M=2Num、調和常數Q=5及迭代次數N=100。仿真10次后求得的平均值的結果如圖1，2所示。

由實驗數據可以看出，在初次迭代后，本文算法搜索到的最優解要優于傳統蟻群算法，原因是傳統蟻群算法初始狀態下各路徑信息素相同，首次迭代中信息素對螞蟻的路徑選擇沒有幫助，而在本文算法中由于偵查素的存在，使得初始狀態下各條路徑上的信息素存在差異，對螞蟻路徑選擇產生影響，使其搜索到更優秀解的可能性增大。

當信息素啟發參數α和視界啟發參數β較小且任務總數小于100時，本文算法在收斂速度要優于傳統蟻群算法，但在最優解方面存在一定不足；當任務總數大于100時，本文算法在收斂速度和最優解方面均要明顯優于傳統的蟻群算法。

當信息素啟發參數α和視界啟發參數β較大時，兩類算法收斂速度都要明顯加快。當任務總數較小時，本文算法和傳統算法互有優劣，但當任務總數大于100時，本文算法性能上優勢明顯。

參考文獻

[1]劉文.一種定向式挖掘的連續域蟻群算法[J].計算機科學，2013，40（12）：292-294.

[2]張燕，顧才東.一種求解云計算資源優化的改進蝙蝠算法[J].科技通報，2014（11）.

[3]張春艷，劉清林，孟珂.基于蟻群優化算法的云計算任務分配[J].計算機應用， 2012，35（2）：1418-1420.

作者簡介

柴旭清（1982-），女，河南省南陽市人。碩士學位。現為河南師范大學網絡中心工程師、CCF會員，主要從事計算機網絡，HPC，云計算等研究。

董永亮（1978-），男，河北省永年縣人。碩士學位。現為河南師范大學新聯學院講師，主要從事計算機網絡。

作者單位

1.河南師范大學網絡中心 河南新鄉市 453007

2.河南師范大學新聯學院 河南省鄭州市 453000