改進(jìn)人工蜂群算法的云任務(wù)調(diào)度

任金霞，杜增正，王興康

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

0 引言

云計算是融合發(fā)展了分布式計算、網(wǎng)格計算、虛擬化、網(wǎng)絡(luò)存儲等計算機(jī)和網(wǎng)絡(luò)技術(shù)的新興計算模型。云系統(tǒng)中有大量且多樣異構(gòu)的資源、不同用戶的任務(wù)和服務(wù)請求。對于這種情況，如何合理地分配云系統(tǒng)中的資源，執(zhí)行用戶的海量任務(wù)并滿足其服務(wù)請求，同時實現(xiàn)負(fù)載均衡、最佳時間等目標(biāo)，是云計算領(lǐng)域研究的難點與熱點之一。

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

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

1 云任務(wù)調(diào)度問題的描述

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

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

(1)

則任務(wù)在虛擬機(jī)上的執(zhí)行時間用矩陣ETC表示，如下式：

(2)

其中：etcij為子任務(wù)ti在虛擬機(jī)vmj上的執(zhí)行時間。

單個任務(wù)執(zhí)行時間etcij可表示為：

(3)

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

將最小任務(wù)完成時間作為優(yōu)化目標(biāo)，任務(wù)完成時間是最后一個任務(wù)在虛擬機(jī)上的時間Makespan：

(4)

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

2 改進(jìn)人工蜂群算法的云任務(wù)調(diào)度

人工蜂群算法的蜜源表示任務(wù)調(diào)度中各種可能的調(diào)度方式，蜂群通過各種方法找尋蜜源即搜尋最優(yōu)解的過程，根據(jù)適應(yīng)度函數(shù)尋得的最優(yōu)蜜源即最優(yōu)解。在云任務(wù)調(diào)度中，最優(yōu)蜜源即最佳任務(wù)分配方法。人工蜂群算法中有采蜜蜂、觀察蜂和偵查蜂3種蜜蜂群體。采蜜蜂和蜜源有一定關(guān)系，蜜源是采蜜蜂此刻正在獲取的食物，觀察蜂通過采蜜蜂傳遞的蜜源信息選擇蜜源進(jìn)行開采，若采蜜蜂蜜源開采達(dá)到了開采限度但未更新位置，變?yōu)閭刹榉潆S機(jī)搜索新的蜜源位置。

2.1 初始蜜源的產(chǎn)生

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

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

(5)

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

2.2 搜索策略的改進(jìn)

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

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

(6)

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

(7)

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

(8)

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

(9)

2.3 選擇策略的改進(jìn)

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

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

(10)

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

2.4 改進(jìn)人工蜂群算法的任務(wù)調(diào)度流程

IABC算法流程如圖1所示。

圖1 IABC算法流程圖

本文算法步驟如下：

在項目水資源論證階段，對項目區(qū)實行嚴(yán)格的水資源論證審批制度，項目規(guī)模和布局以取水總量控制指標(biāo)為指導(dǎo)，項目取水不得突破國家下達(dá)的地表水和地下水取水總量控制指標(biāo)，對于已達(dá)到或超過控制指標(biāo)的地區(qū)，不得新增取水，對于接近控制指標(biāo)的地區(qū)，限制新增取水。地下水超采區(qū)內(nèi)不得新增取用地下水，生態(tài)脆弱區(qū)限制地下水開采，防止出現(xiàn)生態(tài)環(huán)境問題。

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

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

步驟3 采蜜蜂對蜜源鄰域搜索產(chǎn)生新位置，將算法全局最優(yōu)解與蜜蜂鄰域搜索后的解進(jìn)行概率交叉得到新解，依據(jù)貪婪準(zhǔn)則對原解和新解進(jìn)行比較，選出任務(wù)調(diào)度中任務(wù)完成時間少的蜜源。

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

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

步驟6 若蜜源達(dá)到開采限度，采蜜蜂轉(zhuǎn)化為偵察蜂，產(chǎn)生新的蜜源。

步驟7 若達(dá)到算法終止迭代次數(shù)，則返回當(dāng)前所有蜂群找到的最優(yōu)解和最少任務(wù)調(diào)度完成時間，算法結(jié)束。

3 仿真結(jié)果與分析

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

圖2 算法收斂性對比

測試算法在收斂速度上的優(yōu)劣。在200個云任務(wù)和10個虛擬機(jī)的調(diào)度規(guī)模下，通過算法迭代次數(shù)與任務(wù)完成時間的關(guān)系，對IABC和ABC的收斂速度進(jìn)行比較分析，算法中采蜜蜂和觀察蜂規(guī)模各為200。多次實驗取平均值，實驗結(jié)果如圖2所示。

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

測試算法在云任務(wù)完成時間上的優(yōu)劣。設(shè)置虛擬機(jī)數(shù)量為10，云任務(wù)數(shù)量分別為40、80、120、160和200的情況下，比較IABC、ABC和ACO這3種算法在云任務(wù)調(diào)度中的任務(wù)完成時間并進(jìn)行分析，實驗結(jié)果如圖3所示。

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

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

(11)

其中：AL是虛擬機(jī)的平均負(fù)載，為虛擬機(jī)平均任務(wù)完成時間；Timej為虛擬機(jī)vmj的負(fù)載，即虛擬機(jī)vmj上任務(wù)完成時間;n為虛擬機(jī)數(shù)量。

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

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

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

4 結(jié)束語

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