孟慶巖， 王晶晶

(煙臺黃金職業(yè)學(xué)院 1.信息工程系; 2.機電工程系， 山東 煙臺 265401)

0 引言

云計算是一種新興的計算模式，根據(jù)按需付費策略，用戶可以從共享資源池中獲得所需資源[1]。云計算的優(yōu)勢主要來自虛擬化技術(shù)，即通過虛擬機(VM)工具分配資源。云計算有許多優(yōu)點，如可擴展性、彈性、廉價、無需預(yù)先投資和按需自助服務(wù)訪問、靈活性等。云服務(wù)提供商提供的計算資源通過任務(wù)調(diào)度算法分配給最終用戶，其目標是將資源優(yōu)化分配給廣大用戶，同時實現(xiàn)負載平衡。

云計算是一門新興的技術(shù)，因此在云計算中任務(wù)調(diào)度領(lǐng)域有著廣泛的研究。任務(wù)調(diào)度問題近年來涌現(xiàn)了許多啟發(fā)式算法，本文提出了一種混合螢火蟲遺傳啟發(fā)式算法來優(yōu)化云計算中的資源分配和任務(wù)調(diào)度。

遺傳算法屬于進化算法的一類，受到自然選擇過程和進化論的啟發(fā)。遺傳算法的主要優(yōu)點包括：它能夠處理嘈雜或隨機的目標函數(shù)、全局搜索能力、對解決方案集或染色體進行不同類型編碼的能力等。對于具有多個局部最優(yōu)值的問題，遺傳算法是首選的。

螢火蟲算法受到文件行為的影響，算法的優(yōu)勢在于其自動細分問題的能力和處理方式的約束能力[2]。這兩個優(yōu)點結(jié)合在一起，使搜索空間的探索和開發(fā)非常平衡，從而產(chǎn)生了最佳結(jié)果。

因此，遺傳算法和螢火蟲算法都被單獨證明是功能強大的元啟發(fā)式算法，并且它們的混合算法的集成優(yōu)勢更加顯著。本文利用以上優(yōu)點，提出了一種混合螢火蟲遺傳算法，其目標是優(yōu)化分配資源，最大程度地減少云環(huán)境中任務(wù)的總執(zhí)行時間。

1 算法比較

在云計算中使用可分割負載調(diào)度應(yīng)用程序，目的是減少任務(wù)的執(zhí)行時間[3]。例如實時應(yīng)用程序使用亞馬遜Web服務(wù)環(huán)境進行了測試，在該服務(wù)上調(diào)度和部署數(shù)據(jù)管理模型。與傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)相比，數(shù)據(jù)分析任務(wù)、決策支持系統(tǒng)和數(shù)據(jù)集市等各種任務(wù)在云環(huán)境中表現(xiàn)更好。云計算系統(tǒng)建模算法的仿真工具包使用CloudSim仿真軟件[4]。該工具包支持數(shù)據(jù)中心、虛擬機和資源配置策略等建模實體。同時，使用邊界多端口條件下可分任務(wù)調(diào)度的帶寬感知任務(wù)調(diào)度(BATS)算法[5]。

針對CloudSim模擬器對算法進行評估，并將BATS算法與基于公平的任務(wù)調(diào)度算法進行比較，發(fā)現(xiàn)BATS具有更好的性能。另外基于小倉位值規(guī)則粒子群優(yōu)化算法(PSO)用于云計算環(huán)境下的任務(wù)調(diào)度[6-7]。比較PSO算法與嵌入了交叉和變異算子的PSO算法，我們會發(fā)現(xiàn)PSO算法比其他兩個算法收斂更快?；诮刂蛊诤皖A(yù)算分布的成本-時間優(yōu)化(DBD-CTO)調(diào)度算法，具有實現(xiàn)最小執(zhí)行成本和管理期限的雙重目標[8]。一種基于蟻群優(yōu)化算法(ACO-LB)的負載均衡算法來解決云計算中虛擬機的負載不平衡問題，能夠適應(yīng)動態(tài)云計算環(huán)境，以縮短任務(wù)完成時間為目標。利用CloudSim工具對ACO-LB算法進行了仿真，形成一種改進的遺傳算法用于任務(wù)調(diào)度，證明本文所提出的算法比單獨使用三種啟發(fā)式算法產(chǎn)生更好的結(jié)果[9-11]。

對各種算法的調(diào)查表明，元啟發(fā)式算法最適合用于調(diào)度相關(guān)的優(yōu)化問題。該調(diào)查有助于為提出混合螢火蟲遺傳算法解決任務(wù)調(diào)度問題提供堅實的支持背景。

2 混合螢火蟲遺傳算法

該算法是優(yōu)化的螢火蟲算法和遺傳算法的混合算法?；旌系哪繕耸峭ㄟ^將算法的組織分為兩個階段來實現(xiàn)，第一階段通過螢火蟲優(yōu)化算法完成，第二階段通過遺傳算法完成，如圖1所示。

圖1 螢火蟲遺傳算法體系結(jié)構(gòu)

第一個階段是將任務(wù)映射到一個螢火蟲種群，然后根據(jù)啟發(fā)式邏輯對結(jié)果進行優(yōu)化放置，得到一組基本結(jié)果。任務(wù)的放置取決于目標函數(shù)，目標函數(shù)旨在降低任務(wù)的執(zhí)行成本。第二階段從螢火蟲中選取最終結(jié)果，并將這些結(jié)果初始化為遺傳算法的染色體基本群體。由于基本結(jié)果已經(jīng)通過精確算法進行了微調(diào)，因此遺傳算法僅尋找執(zhí)行精確算法后剩下的最高級最優(yōu)解。因此，螢火蟲優(yōu)化和遺傳算法的混合算法比單獨使用的每種算法都能產(chǎn)生更好的結(jié)果。

2.1 螢火蟲算法方法

螢火蟲算法的理想化規(guī)則表現(xiàn)在3個方面。首先螢火蟲屬于雌雄同體物種，一個螢火蟲可以吸引到所有其他的螢火蟲[12]。其次，吸引力與它們的亮度成正比，對于任何兩個螢火蟲，不那么明亮的螢火蟲被吸引；同時，吸引力隨著螢火蟲之間距離的增加而降低。最后，如果某個瞬間沒有比它自己更亮的螢火蟲，它會隨機移動或者不移動位置。

優(yōu)化問題的解決方案或搜索空間具有無限的候選解決方案，在候選搜索空間中解決方案的編碼使結(jié)果可視化并有助于進一步的探索。云計算場景中的資源是虛擬機(VM)，并且每個虛擬機都通過其ID或編號來標識。名為Ti的大小為m(子任務(wù)總數(shù))的向量表示搜索空間，其中每個索引i的值給出分配給第i個任務(wù)的資源號，表示樣本候選編碼解決方案。螢火蟲算法和遺傳算法都使用相同的編碼策略，因此每個完整文件的長度和染色體的長度是相同的，這就是子任務(wù)的總數(shù)(m)。

例如，設(shè)置3個作業(yè)任務(wù)(k=3)和3個資源(n=3)。3個作業(yè)分別分解為2、4、3個子任務(wù)，分別為m1，m2和m3，即子任務(wù)(1)=3(m1=2)，子任務(wù)(2)=4(m2=4)，子任務(wù)(3)=3(m3=3)。因此子任務(wù)的總數(shù)是m1，m2和m3之和，即9(m=m1+m2+m3=9)。因此，染色體的長度(l)為9。對9個子任務(wù)的3種資源的一種可能分配是n1={1,3,5,9}，n2={2,4}，n3={6,7,8}。這種分配在向量T中編碼為[1,2,1,2,1,3,3,3,1]，它代表種群中的一個樣本或一條染色體。T中的每個條目的值都在1～n范圍內(nèi)，令s為螢火蟲種群數(shù)。同樣，如果考慮一個工作長度為9的10個個體(s=10)的總體，則為10*9的隨機值總體矩陣?？偟膩碚f，總體矩陣的形式為Xij，其中i范圍為[1，s]，j為[1，l]，Xij中的每個條目的值為[1，n]。

目標函數(shù)是定義和制定實現(xiàn)優(yōu)化目標所需基本條件的函數(shù)。在本文所提問題中，優(yōu)化的結(jié)果必須是減少所有任務(wù)在云計算機環(huán)境中的總執(zhí)行時間，從而提高任務(wù)調(diào)度性能。因此，目標函數(shù)滿足所有子任務(wù)的總執(zhí)行時間最小。一個任務(wù)的執(zhí)行時間取決于兩個可變的實體，即由虛擬機處理器核心驅(qū)動的指令執(zhí)行速度和每個任務(wù)的指令大小或長度。每個資源或虛擬機都有自己的執(zhí)行速度，以每秒百萬條指令(MIPS)為單位，用向量Ri表示，其中i∈[1,n]。每個子任務(wù)的長度都是用i∈[1,l]編碼的百萬個指令條數(shù)來表示的。每個任務(wù)的執(zhí)行時間(以秒為單位)是通過任務(wù)的長度除以分配給它的虛擬機的速度得到的。每個實體的執(zhí)行時間或精度函數(shù)如式(1)、式(2)。

(1)

(2)

該算法的目標是使式(1)中得到的所有任務(wù)的總執(zhí)行時間最小化，式(2)給出了執(zhí)行時間的反比關(guān)系。一個特定的fi獲得的任務(wù)執(zhí)行時間越長，為該i獲得的F值就越小。因此，最好的解決方案是找到一個具有最大F的染色體，即最優(yōu)螢火蟲算法為M，如式(3)。

M=maxiFi

(3)

螢火蟲的運動流動性基于其對其他螢火蟲的吸引力，具有較高亮度的螢火蟲讓其它螢火蟲朝自己移動。為了衡量吸引力，必須計算出螢火蟲的亮度。亮度(I)是目標函數(shù)對該顏色的直接測量結(jié)果，光線I和j之間的吸引力(β)計算如式(4)、式(5)。

βi=Fi*e-γr2

(4)

βj=Fj*e-γr2

(5)

這里γ是光吸收系數(shù)，它是一個常數(shù);e是指數(shù)常數(shù);r是螢火蟲i和j之間的距離。距離表示兩個螢火蟲對應(yīng)位不同的數(shù)量，類似于漢明距離。該運動的目的是通過將吸引力更強的螢火蟲中的主要特征加入吸引力較弱的螢火蟲中，從而縮短兩個螢火蟲之間的距離。

定義目標函數(shù)：F(x),x=(x1,x2,…,x1)；生成螢火蟲的初始種群Xij(i=1,2,…,m)(j=1,2,…,n)；用F(x)表示光強度I；定義光吸收系數(shù)，設(shè)置t=>0。當t小于總?cè)簲?shù)，設(shè)置條件i=1∶s(s表示所有螢火蟲)，j=1∶i；如果Ij>Ii，吸引力β隨著距離e-γr而變化；此時把螢火蟲i移向j，評估結(jié)果并更新；直至遍歷i和j；最后對螢火蟲進行排序找出當前最優(yōu)。

2.2 遺傳算法方法

經(jīng)過螢火蟲算法的預(yù)先迭代，從螢火蟲過程中形成的最佳解集作為遺傳算法的初始種群。因此，染色體的數(shù)量等于螢火蟲的數(shù)量，同樣的編碼方法也被復(fù)制到了遺傳方案編碼中。3種主要的遺傳算子是選擇、交叉和變異，3個算子共同進化種群[13]。遺傳算法的適應(yīng)度函數(shù)與螢火蟲算法的目標函數(shù)相同，螢火蟲的符號被染色體互換。由于初始的最優(yōu)解集已經(jīng)使用螢火蟲算法找到，因此遺傳算法具有更快收斂解的優(yōu)點。

選擇是指選擇兩個父母產(chǎn)生后代的過程，目的是在保持種群大小恒定的狀態(tài)下復(fù)制種群中適應(yīng)度高的個體[14]。為了生產(chǎn)出更好更適合的后代，選擇更好的父母是至關(guān)重要的。本文選擇了輪盤賭選擇算子。

交叉，相互配對的染色體按某種方式相互交換部分基因[15]。在他們的適合度值中，從兩個父母中選出更強適應(yīng)性的染色體。根據(jù)達爾文的理論，只有適應(yīng)度最強的個體才能生存下來。因此，通過基因交換，較弱的染色體被較強的染色體淘汰。本文采用兩點交叉策略。

變異的目的是在染色體中產(chǎn)生隨機的基因抽動，以引入染色體的多樣性[16]。本文使用非均勻變異算子。

經(jīng)過所需的迭代次數(shù)后，從最終的染色體群體中選擇最佳或最適合的染色體作為結(jié)果，并根據(jù)最佳染色體中編碼的順序遵循調(diào)度順序。

遺傳算法偽代碼，使用與螢火蟲算法相同的目標函數(shù)，產(chǎn)生染色體群體并初始化交叉和突變率。設(shè)置迭代=>0。選擇2個解決方案，根據(jù)結(jié)果改變候選方案，執(zhí)行交叉算子，實現(xiàn)迭代=>迭代+1，直到達到最大迭代限制。選擇出最合適的解決方案，結(jié)束。

3 結(jié)果分析

在CloudSim中模擬了確定螢火蟲遺傳混合算法用于任務(wù)調(diào)度效率的實驗。實驗可分為3個主要部分，以證明螢火蟲遺傳混合算法的效率隨迭代次數(shù)的增加而提高，證明螢火蟲遺傳混合算法的效率高于常用的先進先出(FIFO)算法。最后，證明了組合的螢火蟲遺傳混合算法優(yōu)于單獨的遺傳算法的效率。

3.1 參數(shù)設(shè)定

為了驗證混合遺傳元啟發(fā)式算法在不同情況下的有效性。螢火蟲和遺傳算法使用總結(jié)的參數(shù)進行初始化。如表1所示。

表1 初始化參數(shù)

3.2 實驗結(jié)果分析

在第一種情況下，為了確定迭代和執(zhí)行時間之間的關(guān)系，進行了實驗。所有迭代的任務(wù)數(shù)被固定為20個，而螢火蟲和染色體的群體規(guī)模被固定為30個。所有情況下，資源或虛擬機的數(shù)量固定為5。其余全局參數(shù)與表1相同。隨著時間段數(shù)的增加，執(zhí)行時間減少。如圖2所示。

圖2 執(zhí)行時間與迭代變化的性能分析

從10次迭代開始，迭代次數(shù)增加了10倍。對于每種情況，圖2中提到的迭代值對應(yīng)于螢火蟲和遺傳算法的相同迭代值。

在第二種情況下，實驗的目的是建立螢火蟲遺傳算法優(yōu)于FIFO算法的優(yōu)越性。任務(wù)數(shù)從20開始以20的系數(shù)遞增，所有情況下資源或虛擬機的數(shù)量固定為5。在整個實驗中，螢火蟲和遺傳算法的迭代值都固定在30?？偨Y(jié)了實驗結(jié)果，如圖3所示。

圖3 FIFO與混合遺傳算法的性能分析

顯然，隨著任務(wù)數(shù)的增加，螢火蟲遺傳算法的執(zhí)行時間依然比FIFO算法要短。

在第三種情況下，該實驗旨在證明將螢火蟲遺傳算法結(jié)合在一起的能力，實驗情況與方案2相似。任務(wù)數(shù)從20開始以20的系數(shù)遞增，所有情況下資源或虛擬機的數(shù)量固定為5。兩種算法的迭代值固定為30。結(jié)果如圖4所示。

圖4 遺傳算法與混合遺傳算法的性能分析

混合螢火蟲遺傳算法在執(zhí)行越來越多的任務(wù)時執(zhí)行時間更短，這證明它比遺傳算法更好。

4 總結(jié)

本文提出了一種將螢火蟲和遺傳兩種強大的啟發(fā)式搜索算法相結(jié)合的方法，形成一個組合的元啟發(fā)式搜索算法。試圖探索一種新的混合遺傳元啟發(fā)式算法來解決云計算中的任務(wù)調(diào)度問題，其目標是使所有任務(wù)的執(zhí)行時間最小，達到近似最優(yōu)解決方法。仿真結(jié)果表明，與FIFO和遺傳等常用算法相比，混合螢火蟲遺傳算法在大搜索空間的動態(tài)云環(huán)境中具有高效、快速的搜索能力。由于混合螢火蟲遺傳算法能夠快速收斂到近似全局最優(yōu)解，因此它在云計算環(huán)境中有利于資源的優(yōu)化分配和任務(wù)調(diào)度。