基于蟻群算法的云計算自適應(yīng)任務(wù)調(diào)度研究

柴旭清 董永亮

摘 要：為了解決蟻群算法在解決云計算中大規(guī)模任務(wù)調(diào)度問題時收斂速度較慢且易陷入局部最優(yōu)解的缺陷，設(shè)計了一種基于蟻群算法的云計算自適應(yīng)任務(wù)調(diào)度算法，該算法在多態(tài)蟻群算法的基礎(chǔ)上加入了信息素自適應(yīng)更新調(diào)整機(jī)制，用來提高算法的收斂速度，有效地避免的局部最優(yōu)解的出現(xiàn)。實驗數(shù)據(jù)表明，在解決大規(guī)模任務(wù)調(diào)度問題時本文算法性能更好。

【關(guān)鍵詞】云計算 任務(wù)調(diào)度 蟻群算法 自適應(yīng)

1 自適應(yīng)任務(wù)調(diào)度算法

1.1 信息素初始化

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

1.1.1 偵查螞蟻

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

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

1.1.2 搜索螞蟻

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

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

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

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

1.2 信息素更新規(guī)則

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

1.2.1 局部更新

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

1.2.2 全局更新

信息素的全局更新是指在蟻群算法在進(jìn)行一次迭代后，對出現(xiàn)在迭代最優(yōu)解的螞蟻所經(jīng)的路徑上所有城市的信息素進(jìn)行更新，具體更新公式如下：

其中，MAT（z）表示在第z次迭代中搜索發(fā)現(xiàn)的最優(yōu)解的匹配距離。

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

2 性能測試

通過matlab對本文算法和傳統(tǒng)蟻群算法進(jìn)行仿真分析，在仿真過程中分別將等待調(diào)度的任務(wù)總數(shù)和服務(wù)器總數(shù)為Num=100，200，信息素啟發(fā)參數(shù)α和視界啟發(fā)參數(shù)β分別為α=1，β=2及α=5，β=10、信息素?fù)]發(fā)參數(shù)ρ=0.5、螞蟻總數(shù)M=2Num、調(diào)和常數(shù)Q=5及迭代次數(shù)N=100。仿真10次后求得的平均值的結(jié)果如圖1，2所示。

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

當(dāng)信息素啟發(fā)參數(shù)α和視界啟發(fā)參數(shù)β較小且任務(wù)總數(shù)小于100時，本文算法在收斂速度要優(yōu)于傳統(tǒng)蟻群算法，但在最優(yōu)解方面存在一定不足；當(dāng)任務(wù)總數(shù)大于100時，本文算法在收斂速度和最優(yōu)解方面均要明顯優(yōu)于傳統(tǒng)的蟻群算法。

當(dāng)信息素啟發(fā)參數(shù)α和視界啟發(fā)參數(shù)β較大時，兩類算法收斂速度都要明顯加快。當(dāng)任務(wù)總數(shù)較小時，本文算法和傳統(tǒng)算法互有優(yōu)劣，但當(dāng)任務(wù)總數(shù)大于100時，本文算法性能上優(yōu)勢明顯。

參考文獻(xiàn)

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

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

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

作者簡介

柴旭清（1982-），女，河南省南陽市人。碩士學(xué)位?，F(xiàn)為河南師范大學(xué)網(wǎng)絡(luò)中心工程師、CCF會員，主要從事計算機(jī)網(wǎng)絡(luò)，HPC，云計算等研究。

董永亮（1978-），男，河北省永年縣人。碩士學(xué)位?，F(xiàn)為河南師范大學(xué)新聯(lián)學(xué)院講師，主要從事計算機(jī)網(wǎng)絡(luò)。

作者單位

1.河南師范大學(xué)網(wǎng)絡(luò)中心 河南新鄉(xiāng)市 453007

2.河南師范大學(xué)新聯(lián)學(xué)院 河南省鄭州市 453000