改進人工蜂群算法的云任務調度

任金霞，杜增正，王興康

(江西理工大學 電氣工程與自動化學院，江西 贛州 341000)

0 引言

云計算是融合發展了分布式計算、網格計算、虛擬化、網絡存儲等計算機和網絡技術的新興計算模型。云系統中有大量且多樣異構的資源、不同用戶的任務和服務請求。對于這種情況，如何合理地分配云系統中的資源，執行用戶的海量任務并滿足其服務請求，同時實現負載均衡、最佳時間等目標，是云計算領域研究的難點與熱點之一。

云計算環境下的任務調度[1-2]是一個非確定性多項式難(non-deterministic polynomial-hard，NP-Hard)組合優化問題。文獻[3]結合貪心算法和數據節點分配，減少了云任務的總完成時間。文獻[4]提出的Min-Max算法將大小任務同時進行調度，提高了負載均衡。但上述傳統算法有一定局限性，不能很好地滿足用戶的多樣需求。所以，近年國內外許多學者使用遺傳算法[5-7]、蟻群算法[8-9]、鳥群算法[10-11]、蝗蟲算法[12]和粒子群算法[13-14]等智能優化算法來解決云任務調度中的難題。文獻[15]提出了一種基于改進遺傳算法的云任務調度策略，對最小任務完成時間進行優化。文獻[16]提出了一種改進蟻群算法的云任務調度策略，減少了任務完成時間，降低了虛擬機資源利用率，均衡了負載。文獻[17] 提出的反向學習法和交叉操作的改進烏鴉搜索算法，降低了任務完成成本和完成時間。文獻[18]提出了微生物遺傳算法和改進粒子群算法融合的云計算任務調度算法，該算法減少了任務完成時間和成本，并且優化了虛擬機負載。

人工蜂群算法[19](artificial bee colony algorithm，ABC)仿照了蜂群覓食的行為，是一種易實現、參數少的群智能算法。本文提出了一種改進人工蜂群算法(improved artificial bee colony algorithm，IABC)，將算法全局最優解與蜜蜂鄰域搜索后的解進行概率交叉，增強算法對蜜源的開發能力且保持探索能力，加快算法收斂速度；觀察蜂的靈敏度，通過配合蜜源的信息素來選擇蜜源，增加種群多樣性以避免算法陷入局部最優。

1 云任務調度問題的描述

目前，云計算使用谷歌公司于1995年推出的Map/Reduce編程方式，其原理是將需要執行的問題分為Map和Reduce兩部分，用戶傳送的任務被Map程序拆分為若干小的子任務，通過云虛擬化技術，這些子任務按照一定的調度方式被調度給虛擬服務資源，Reduce程序整合計算結果，最后輸出。在這個過程中，各個云任務、虛擬機是相互獨立的，且云任務在虛擬資源中被并行執行，每個子任務只能被一臺虛擬機執行。

為了方便分析，云計算任務調度可抽象為m個子任務在n個虛擬機上執行(m>n)，調度目標為盡可能小的任務完成時間。T={t1,t2,t3，…,tm}為m個子任務集合，ti(i=1,2,3，…,m)為第i個子任務；VM={vm1,vm2,vm3，…,vmn}為n個虛擬機集合，vmj(j=1,2,3,…,n)為第j個虛擬機；則任務-虛擬機的分配關系用m×n矩陣TVM表示，如下式：

(1)

則任務在虛擬機上的執行時間用矩陣ETC表示，如下式：

(2)

其中：etcij為子任務ti在虛擬機vmj上的執行時間。

單個任務執行時間etcij可表示為：

(3)

其中：lengthi為子任務i的長度；mipsj為虛擬機j的處理性能。

將最小任務完成時間作為優化目標，任務完成時間是最后一個任務在虛擬機上的時間Makespan：

(4)

其中：sum(j)為分配到虛擬機vmj上總的任務數量。

2 改進人工蜂群算法的云任務調度

人工蜂群算法的蜜源表示任務調度中各種可能的調度方式，蜂群通過各種方法找尋蜜源即搜尋最優解的過程，根據適應度函數尋得的最優蜜源即最優解。在云任務調度中，最優蜜源即最佳任務分配方法。人工蜂群算法中有采蜜蜂、觀察蜂和偵查蜂3種蜜蜂群體。采蜜蜂和蜜源有一定關系，蜜源是采蜜蜂此刻正在獲取的食物，觀察蜂通過采蜜蜂傳遞的蜜源信息選擇蜜源進行開采，若采蜜蜂蜜源開采達到了開采限度但未更新位置，變為偵查蜂隨機搜索新的蜜源位置。

2.1 初始蜜源的產生

初始階段，蜂群沒有先驗知識，此時全部蜜源為偵查蜂，算法任意產生N個初始偵查蜂，同時N代表采蜜蜂數目，也是初始化蜜源的數量。第i個蜜源的位置是Xi=(xi1,xi2,xi3,…,xiD)(i=1,2,3,…,N)，這里D為優化問題的維度。在云任務調度中，假設云任務個數為m，虛擬機個數為n，則蜜源的維度D等于云任務的個數m，蜜源維度的編號為云任務ID，蜜源某個維度的值為云計算虛擬機ID，代表一個云任務需映射到一個虛擬機，由此，蜜源(可行解)便可以表示云任務和虛擬機的映射關系。人工蜂群算法中隨機產生初始可行解的公式是：

xij=xminj+rand(0,1)(xmaxj-xminj)，

(5)

其中：xij為蜜源位置；j∈{1,2,3,…,D}，為D維解向量的分量；xmaxj和xminj分別為維度的最大值和最小值；rand(0,1)為0到1之間的隨機數。

2.2 搜索策略的改進

在人工蜂群算法中，觀察蜂通過采蜜蜂分享的蜜源信息選擇蜜源進行開采，蜜源的適應度值越大，被選擇的概率越高，該蜜源進行鄰域搜索的觀察蜂數目就越多，會使算法具有較強的鄰域搜索能力。采蜜蜂階段和觀察蜂階段用式(6)進行鄰域搜索，算法會在探索方面強而在開發方面弱。為了彌補開發方面的缺陷，文獻[20]從粒子群算法中得到啟發，提出全局最優人工蜂群算法來提高人工蜂群算法的開發能力，算法搜索階段為式(7)。

vij=xij+α(xij-xkj),i≠k，

(6)

其中：xij為蜜源位置；vij為鄰域內搜索得到新蜜源的位置；i,k∈{1,2,3,…,N}，j∈{1,2,3,…,D}；α為[-1，1]上的隨機數。

(7)

由于式(7)的第3項平衡算法探索與開發能力時會一定程度降低算法全局搜索能力，提出一種結合全局最優引導的蜂群算法和交叉操作的改進策略。將采蜜蜂鄰域搜索后的解與全局最優解進行交叉操作，對蜜源位置的每一維度隨機產生一個數rand，rand在0到1之間均勻分布，如果rand

(8)

這種簡單地與全局最優值交叉雖然會使算法開發能力提升很多，但不利于人工蜂群算法的探索，需要兼顧算法的搜索能力，防止算法早熟，建立如下公式：

(9)

2.3 選擇策略的改進

在人工蜂群算法中，按照輪盤賭策略，觀察蜂會選擇適應度更好的蜜源，較差蜜源將被放棄，這會降低種群的多樣性且影響算法尋優能力，使算法早熟而陷入局部最優。自由搜索算法中有靈敏度的概念，通過與蜜源的信息素配合選擇區域，可擴大選擇蜜源的范圍。搜索區域的信息素配合其靈敏度，使算法具有導向性。通過這種選擇方式，任何適應度的蜜源都可能被選到，種群多樣性更豐富，可防止算法陷入局部最優，且優秀的蜜源被選擇的概率更大，保證了觀察蜂選擇蜜源的方向。

該方法為：計算N個蜜源的適應度值f(X)并找出最大和最小適應度值，計算第i個蜜源的信息素O(i)，之后隨機生成第i個觀察蜂的靈敏度S(i)～U(0,1)，若第i個觀察蜂的靈敏度S(i)≤O(i)，則進行鄰域搜索，選擇更優的蜜源；若S(i)≥O(i)，則蜜源位置不變。蜜源信息素計算公式如下：

(10)

其中：fi為第i個蜜源的適應度函數值；fmin為最小適應度值；fmax為最大適應度值；O(i)為第i個蜜源的信息素。

2.4 改進人工蜂群算法的任務調度流程

IABC算法流程如圖1所示。

圖1 IABC算法流程圖

本文算法步驟如下：

在項目水資源論證階段，對項目區實行嚴格的水資源論證審批制度，項目規模和布局以取水總量控制指標為指導，項目取水不得突破國家下達的地表水和地下水取水總量控制指標，對于已達到或超過控制指標的地區，不得新增取水，對于接近控制指標的地區，限制新增取水。地下水超采區內不得新增取用地下水，生態脆弱區限制地下水開采，防止出現生態環境問題。

步驟1 初始化參數，設置人工蜂群算法最大迭代次數，蜜源停留最大搜索次數和蜜蜂種群數，其中采蜜蜂和觀察蜂各一半。

步驟2 初始化種群，按照式(5)隨機產生初始解，將云任務隨機分配給虛擬機。

步驟3 采蜜蜂對蜜源鄰域搜索產生新位置，將算法全局最優解與蜜蜂鄰域搜索后的解進行概率交叉得到新解，依據貪婪準則對原解和新解進行比較，選出任務調度中任務完成時間少的蜜源。

步驟4 觀察蜂獲取采蜜蜂搖擺舞傳遞的蜜源信息，計算蜜源信息素，根據靈敏度和蜜源的信息素的關系選擇蜜源。

步驟5 觀察蜂變成采蜜蜂鄰域搜索當前的解，并將全局最優解與其概率交叉得到另一解，按貪婪策略選擇新的解。

步驟6 若蜜源達到開采限度，采蜜蜂轉化為偵察蜂，產生新的蜜源。

步驟7 若達到算法終止迭代次數，則返回當前所有蜂群找到的最優解和最少任務調度完成時間，算法結束。

3 仿真結果與分析

CloudSim[21]是澳大利亞墨爾本大學網格實驗室和Gridbus項目聯合研發的云計算仿真平臺，它主要模擬云環境，對不同服務模型的調度策略進行測試。為測試本文算法在云計算任務調度中的效果，在Intel i5處理器、12 GB內存、Windows 10操作系統下，使用CloudSim平臺進行測試。對本文改進算法(IABC)、人工蜂群算法(ABC)和蟻群算法(ant colony optimization，ACO)在云計算任務調度的收斂速度、任務完成時間和負載不均衡度3個方面進行比較分析。

圖2 算法收斂性對比

測試算法在收斂速度上的優劣。在200個云任務和10個虛擬機的調度規模下，通過算法迭代次數與任務完成時間的關系，對IABC和ABC的收斂速度進行比較分析，算法中采蜜蜂和觀察蜂規模各為200。多次實驗取平均值，實驗結果如圖2所示。

從圖2中可以看出：IABC的收斂效果比ABC好，IABC和ABC在前100次迭代收斂速度都很快，且IABC比ABC的收斂速度更快。主要是因為交叉操作和全局機制引入到人工蜂群算法中，概率交叉全局最優解與采蜜蜂鄰域搜索后的解，會增強算法對蜜源的開發能力和算法的方向性，算法在最優解附近的開發能力也得以提升，且加快了算法的收斂速度。IABC在迭代250次后逐漸趨于平穩，且任務完成時間比ABC少。

測試算法在云任務完成時間上的優劣。設置虛擬機數量為10，云任務數量分別為40、80、120、160和200的情況下，比較IABC、ABC和ACO這3種算法在云任務調度中的任務完成時間并進行分析，實驗結果如圖3所示。

從圖3中可以看出：IABC比另外兩種算法所需的任務完成時間更短，優化效果更好。隨著云任務數量的增加，任務完成時間也在增加。當任務數為40時，IABC的任務完成時間比ABC、ACO分別少8 s和20 s，任務數逐漸增多，各算法任務完成時間差增大，當任務數到200時，IABC的任務完成時間比ABC、ACO分別少24 s和35 s，減少了3.7%和5.3%。這是因為IABC算法中全局最優解與蜜蜂鄰域搜索后的解進行概率交叉，增強了算法對蜜源的開發能力且保持探索能力，改進的選擇策略可以增強種群的多樣性，避免算法過早早熟而陷入局部最優。IABC在局部搜索和全局搜索方面都發揮作用，在規模較大的云計算任務調度上效果更明顯。

測試算法的負載不均衡度(degree of imbalance，DI)，DI可以衡量虛擬機之間的不平衡程度。本文使用標準差來表示不均衡度DI，DI值越小，各虛擬機之間的負載量越接近，負載均衡度越好，調度策略就越合理。DI[22]表示為：

(11)

其中：AL是虛擬機的平均負載，為虛擬機平均任務完成時間；Timej為虛擬機vmj的負載，即虛擬機vmj上任務完成時間;n為虛擬機數量。

云任務數為40、80、120、160和200的情況下，比較分析IABC、ABC、ACO這3種算法的負載不均衡度DI，如圖4所示。

圖3 任務完成時間對比 圖4 算法的DI值對比

從圖4中可以看出：隨著任務數量的增加，3種算法的DI值也在增加，且IABC的DI值比ABC和ACO的DI值小，表明在任務調度中，任務完成時間短的情況下，IABC比ABC和ACO負載不均衡度低，可實現更好的負載均衡，各虛擬機之間負載量更接近。

4 結束語

對人工蜂群算法進行改進，用于云計算任務調度中，以最小任務完成時間為目標。把全局最優機制和交叉操作運用到人工蜂群算法中，增強蜂群開發能力的同時保證蜂群向周圍搜索的能力，加快算法收斂速度。在觀察蜂選擇策略中，引入靈敏度的概念，增加了種群多樣性，避免算法陷入局部最優。IABC在收斂速度、任務完成時間和負載均衡方面的表現較為優越。