基于混合螢火蟲遺傳算法的云計(jì)算中的任務(wù)調(diào)度優(yōu)化

孟慶巖， 王晶晶

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

0 引言

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

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

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

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

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

1 算法比較

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

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

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

2 混合螢火蟲遺傳算法

該算法是優(yōu)化的螢火蟲算法和遺傳算法的混合算法。混合的目標(biāo)是通過(guò)將算法的組織分為兩個(gè)階段來(lái)實(shí)現(xiàn)，第一階段通過(guò)螢火蟲優(yōu)化算法完成，第二階段通過(guò)遺傳算法完成，如圖1所示。

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

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

2.1 螢火蟲算法方法

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

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

例如，設(shè)置3個(gè)作業(yè)任務(wù)(k=3)和3個(gè)資源(n=3)。3個(gè)作業(yè)分別分解為2、4、3個(gè)子任務(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)。因此，染色體的長(zhǎng)度(l)為9。對(duì)9個(gè)子任務(wù)的3種資源的一種可能分配是n1={1,3,5,9}，n2={2,4}，n3={6,7,8}。這種分配在向量T中編碼為[1,2,1,2,1,3,3,3,1]，它代表種群中的一個(gè)樣本或一條染色體。T中的每個(gè)條目的值都在1～n范圍內(nèi)，令s為螢火蟲種群數(shù)。同樣，如果考慮一個(gè)工作長(zhǎng)度為9的10個(gè)個(gè)體(s=10)的總體，則為10*9的隨機(jī)值總體矩陣。總的來(lái)說(shuō)，總體矩陣的形式為Xij，其中i范圍為[1，s]，j為[1，l]，Xij中的每個(gè)條目的值為[1，n]。

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

(1)

(2)

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

M=maxiFi

(3)

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

βi=Fi*e-γr2

(4)

βj=Fj*e-γr2

(5)

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

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

2.2 遺傳算法方法

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

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

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

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

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

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

3 結(jié)果分析

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

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

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

表1 初始化參數(shù)

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

4 總結(jié)

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