基于改進的蝙蝠算法在云計算資源調度中的研究

李天朝，李蜀瑜

（陜西師范大學 計算機科學學院，陜西 西安 710062）

基于改進的蝙蝠算法在云計算資源調度中的研究

李天朝，李蜀瑜

（陜西師范大學 計算機科學學院，陜西 西安 710062）

本文對云計算中資源調度進行了深入的研究，針對云計算的資源調度模型，提出一種基于和聲算法和蝙蝠算法調度算法。在該求解方法中，通過改進蝙蝠的位置的平均響度，來減小的迭代次數。這一改進能夠提供易于調節的蝙蝠算法離散優化問題，提高算法的收斂速度，縮短算法的運行時間。實現了蝙蝠算法對優化問題的處理結果。通過仿真實驗表明，該算法是一種云計算環境下有效的任務調度算法。

元計算；蝙蝠算法；和聲算法；資源調度

云計算是一種商業模式和服務模式，是分布式計算、并行處理和網格計算等多種技術的拓展和延伸[1]。資源調度是云計算的核心問題，其效率直接影響整個云計算環境的工作性能，在云計算環境下，怎樣找到一個完善、高效的計算資源調度模型是至關重要的，它決定了云計算的性能，已經成為當前一個重要研究方向之一[2]。

文獻[3]中對云計算下的資源池模型做了介紹，分析了云計算調度資源流程和云計算環境下實體之間的關系。建立了一種云計算環境中資源調度算法，綜合考慮了云計算資源池中各種資源的綜合負載情況，采用人工加自動的虛擬機遷移技術實現云計算中物理服務器的負載均衡。文獻[4]使用了馬爾可夫鏈模型并提出一種控制算法，在特定的QoS約束條件下最大化每兩次虛擬機遷移的時間，從而決定哪些服務器是資源過載的。文獻[5]提出了一種基于克隆選擇算法的云集群資源調度方法。首先，定義了云環境下以最小化執行時間跨度和負載均衡因子的集群資源調度模型，然后設計了抗體的編碼方式，抗體與抗原之間的親和度函數、抗體之間的親和度函數、克隆算子、退火交叉算子和高斯變異算子，并定義了基于克隆選擇算法的云計算集群資源調度方法。文獻[6]提出了CL-PSO算法，是以綜合置信度最優解為目標函數，文化粒子群算法 （CulturalParticleSwarm Optimization，CPSO）是文化算法（CA）和PSO算法相結合的組合算法，較好地克服了標準PSO算法存在的缺陷，為云計算資源調度提供了一種新的研究方法。文獻[7]針對現行資源調度算法存在算法效率低等弊端，提出一種新的云計算資源調度模型（IABC），基于利用改進人工蜂群算法的云計算資源調度模型，改進了傳統資源調度算法的缺陷，大幅度消減了任務的完成的時間，并且提高了云計算資源利用率。文獻[8]使用一種更先進、更精確的方法來預測虛擬機的CPU使用情況。建立了每個虛擬機的數據模型，利用了一種分布式決策支持系統（rDSS）作為云計算應用來預測虛擬機的CPU使用率。

文中提出了一種改進的蝙蝠算法，通過改進蝙蝠的位置的平均響度，來減小的迭代次數。這一改進能夠提供易于調節的蝙蝠算法離散優化問題，提高算法的收斂速度，減少了算法的執行時間，實現了蝙蝠算法對優化問題的處理結果。

1 云計算資源調度模型

云計算資源調度是云計算技術的一個重要組成基礎，它的目標是研究用戶提交的任務分配計算節點、計算節點間進行動態擴展及在滿足用戶服務質量要求并且執行時間最短的前提下，虛擬機利用率最高，它的效能直接影響所有云計算環境的工作能效。在云計算資源調度中，就是盡可能的在短時間內完成任務最多，目標值調度時間最小，系統利用率最高。云計算資源調度模型如下：■

其中，xij表示任務i占用虛擬節點 j，1表示占用，0則表示未占用；tij表示任務i在虛擬節點j上使用的時間，cij表示任務i占用虛擬節點j上的費用，sij表示任務i占用虛擬節點j上的資源利用率，kij表示任務i占用虛擬節點j上的調度開銷。i表示虛擬節點的個數，j表示虛擬節點，T表示資源調度的目標函數值，要求達到min S。

2 蝙蝠算法

蝙蝠算法 （Bat Algorithm，BA）[9-11]是劍橋大學Xin-She Yang教授在2010年提出的一種啟發式群智能優化算法，它是利用蝙蝠回聲定位搜索捕食獵物模擬出的算法。蝙蝠算法是通過自然界中蝙蝠找尋食物的活動，通過使用回聲中的聲波定位去搜索它們的獵物，回聲中的聲波是由指定的脈沖速率和頻率獲得，通過迭代搜索得到最優解，并且在生成的最優解周圍進行局部搜索，直至找到最優解。蝙蝠算法作為一種新穎的群智優化算法，收斂速度快，參數少，模型簡單等優點，已經成功運用于多種問題中[12]。

起初必須確定N維的搜索空間，蝙蝠的響度是A，頻率范圍為[fmin，fmax]，脈沖頻率為r，對應波長的范圍是[λmin，λmax]，指定第i只蝙蝠在t時刻的速度vti和位置lti的更新公式如下：

其中，fi表示蝙蝠頻率，β∈[0，1]它代表的隨機變量，服從均勻分布。x*表示通過每一次迭代得到的最佳位置。針對λf是一個增量，在本文中固定波長λ，而針對f進行調整，在進行部分搜索的期間，從現在的局部搜索中生成一個最優解，每只蝙蝠將隨機生成一個新的位置。

在以上公式中，假設α和κ取值在[0，1]。隨著蝙蝠的速度和響度的不斷更新，象征著蝙蝠可以繼續飛向最優解。

3 基于和聲搜索算法的蝙蝠算法的改進

對于基本蝙蝠算法種群中的每只蝙蝠在一個小范圍內搜索能力比較強，但是整個群體缺乏有效的變異機制因為該算法采用種群向當前最優個體學習的機制，一旦被某個局部極值吸引，由于沒有有效的變異機制，使得整個種群都可能陷入局部最優解。此外，蝙蝠算法也存在一些問題，例如后期收斂速度慢、難以擺脫局部最優，種群迅速聚集到超個體，全局搜索能力較差等。

3.1 和聲搜索算法

和聲搜索（Harmony Search，HS）算法[13]是 2001年韓國學者Z.W.Geem等人提出的一種新的智能優化算法，算法模擬了樂師們在音樂作曲中憑借自己的記憶，通過重復調整樂隊中各樂器的音調，最終能獲得一個優美的和聲狀態的過程。HS算法將樂器聲調的和聲類比于優化問題的解向量，評價即是各對應的目標函數值。算法引入兩個主要參數，即微調概率 （Pitch Adjusting Rate，PAR）和記憶庫取值概率（Harmony Memory Considering Rate，HMCR）[14]。

3.2 對蝙蝠算法的改進

蝙蝠算法有一個很好的搜索能力。但是，它需要通過大量的迭代才能產生產生這種令人滿意的結果。在這里，我們定義動態比例系數參數θ，它是限制步長的隨機漫步的本地搜索的一個因素，改進提出了這個算法。適當的調整，從計算時間來看該參數減小了的迭代次數。此外，這一改進能夠提供易于調節的蝙蝠算法離散優化問題。動態比例因子θ參數可以定義為：

這個公式定義了和聲搜索算法中寬帶參數之間的關系。取代了用公式（4），進一步演化的公式可以表述如下：

在上述的公式中，iter指代當前迭代過程。為了解決收斂實例，上述這種增強版的方程式還是會用上的。在連續優化問題中，θmax和θmin應該可以分別被取作1和0.001。同時在離散優化問題中，θmax和θmin可以分別被取作10和0.01。但是，這些數值通常在優化問題中的參數整定時才會被推薦使用；同時，在遇到一些參數和問題高度緊密聯系，但是這些問題又需要得到較好調整的情況下，這些數值也會被推薦使用。

3.3 蝙蝠個體的編碼方式

云計算資源調度即是對所有可能的調度序列進行搜索，最后找到一個最好調度的方案。在處理云計算資源調度運用蝙蝠算法算法時，需要對資源進行劃分和蝙蝠個體進行編碼。為了便于計算，提高蝙蝠算法的搜索效果，文中采用二進制方式編碼作為蝙蝠個體的蝙蝠方式，即蝙蝠個體對應每個任務的資源，每一個編碼后的蝙蝠個體實際上都與每一個資源相對應。

改進的蝙蝠算法在云計算資源調度的優化步驟：

1）初始化蝙蝠種群的位置x（i），速度v（i），脈沖發射速率r（i），脈沖響度A（i）和脈沖頻率f（i）；

2）初始化當前區域中的蝙蝠數量xi（i∈{1…n}）。

3）根據個體不同的適應值采用不同的頻率生成策略；

4）利用公式（2）~（4）計算蝙蝠飛行速度和空位方位；

5）評估新解，若滿足條件則更新位置和速度，同時利用公式（9）、公式（6）更新脈沖響度A（i）和發射速率r（i）；

6）判斷算法終止條件，若滿足搜素精度w或者達到搜素次數，則退出，并輸出最終結果，否則返回2）。

7）輸出最優極值和個體。

4 算法仿真

文中將云計算中的任務調度的個數模擬為蝙蝠的個數，將資源優化調度看成是蝙蝠個體搜索的過程，將滿足資源調度公式（1）模擬為蝙蝠所處的位置的優劣。文中算法采用CloudSim[15]平臺測試，CloudSim是由澳大利亞墨爾本大學和Gridbus共同推出的云計算仿真軟件平臺，實驗環境為Windows 7操作系統，硬件主要包括i7CPU和8G DRR3，設定參數虛擬任務為500個，虛擬節點為8個，設置迭代次數為500，并將本文算法與PSO、GA在云計算模型中進行對比。

圖1 3種資源負載算法任務完成時間比較

圖2 3種資源負載算法能量消耗時間比較

從圖1~3中可以看出，該算法在本文中的任務完成時間一開始差別不太明顯。然而，隨伴著任務數量的增加，所花費的時間比其他算法，在能量消耗方面明顯減少，伴隨著任務數量的不斷增多，差異明顯。在3種算法的資源開銷方面，文中算法的時間開銷優于其他的兩種算法，并在一定程度上節省了資源分配的時間。

圖3 3種資源負載算法開銷時間比較

5 結束語

云計算環境資源分配是云計算效率的關鍵，文中是基于云計算環境下的資源分配研究，針對當前云計算資源調度算法存在收斂速度慢，資源利用率不足等缺陷，利用蝙蝠算法控制參數少、易于實現、計算簡單等優點，提出了一種基于和聲搜素算法的蝙蝠算法的云計算資源調度模型．仿真結果表明，相對于遺傳算法和粒子群算法，文中算法不僅找到了理想的云計算資調度方案，任務完成時間急劇減少，而且克服了當前云計算資源調度算法存在的不足，提高了云計算資源利用率，在現代大規模云計算中有著廣泛的應用前景。

[1]林偉偉，齊德昱.云計算資源調度研究綜述[J].計算機科學，2012（10）:1-6.

[2]薛玉.云計算環境下的資源調度優化模型研究[J].計算機仿真，2013（5）:362-365.

[3]劉賽，李緒蓉，萬麟瑞，等.云環境下資源調度模型研究[J].計算機工程與科學，2013（3）:48-51.

[4]Beloglazov A，Buyya R.Managing overloaded hosts for dynamic consolidation of virtual machines in cloud data centers underquality ofservice constraints[J].IEEE Transactions on Parallel& Distributed Systems，2013，24（7）:1366-1379.

[5]朱利華，李春華，吳寬仁.基于改進克隆選擇算法的云計算集群資源調度[J].科學技術與工程，2013（13）:3642-3646.

[6]羅丹.云計算資源調度算法仿真[J].計算機仿真，2013（7）:280-283.

[7]孟令璽，李洪亮.基于CA-PSO算法的云計算資源調度策略[J].計算機仿真，2013（10）:406-410.

[8]Li-Hua G，Liying S，Sotaro C.Provisioning of requests for virtual machine sets with placement constraints in IaaS clouds[C].Integrated Network Management（IM 2013），2013 IFIP/IEEE International Symposium on.IEEE，2013:499-505.

[9]Yang X S.A new metaheuristic bat-Inspired algorithm[J].Science，2010（284）:65-74.

[10]Mirjalili S，Mirjalili S M，Yang X S.Binary bat algorithm[J].Neural Computing&Applications，2014，25（3-4）:663-681.

[11]Gandomi A H，Yang X S，Alavi A H，et al.Bat algorithm for constrained optimization tasks[J]. Neural Computing&Applications，2013，22（6）: 1239-1255.

[12]屈遲文，傅彥銘，侯勇順.融合入侵雜草算子的蝙蝠算法[J].計算機應用與軟件，2015（4）:243-246.

[13]Zong W G，Kim J H，Loganathan G V.A new heuristic optimization algorithm:harmony search. [J].Simulation Transactions of the Society for Modeling&Simulation International，2001，76（2）:60-68.

[14]雍龍泉.一種全局和聲搜索算法求解絕對值方程[J].計算機應用研究，2013，30（11）:3276-3279.

[15]Calheiros R N，Ranjan R，De Rose C A F，et al. Cloudsim:A novel framework for modeling and simulation of cloud computing infrastructures and services[R].Technical report，Grids-TR-2009-1，Grid computing and distributed system laboratory，The University of Melbourne，Australia，2009.

Resource scheduling in cloud computing based on improved bat algorithm

LI Tian-chao，LI Shu-yu
（College of Computer Science，Shaanxi Normal University，Xi’an 710062，China）

In this paper，after in-depth research cloud computing task scheduling strategy in cloud computing environments，for cloud computing resource scheduling model，we propose a scheduling algorithm harmony algorithms and bat algorithm.In the solving process，by improving the average loudness bat position，to reduce the number of iterations.This improvement can be easily adjusted to provide discrete optimization problems bat algorithm to improve the convergence speed，shorten the running time of the algorithm.Realized bat algorithm optimization problem processing results.Simulation results show that the algorithm is effective scheduling algorithm in a cloud computing environment.

cloud computing；resource scheduling；bat algorithm；harmony algorithms

TN99

：A

：1674－6236（2017）01-0043-04

2016-01-14稿件編號：201601097

李天朝（1982—），男，陜西大荔人，碩士研究生。研究方向：云計算。