一種基于改進樽海鞘算法的云仿真任務調(diào)度的研究

賀少婕,杜松澤,卜立平

1(中國科學院 沈陽計算技術(shù)研究所,沈陽 110168) 2(中國科學院大學,北京 100049) 3(中南大學 商學院,長沙 410000)

1 引 言

如今處于大數(shù)據(jù)時代,大數(shù)據(jù)利用云平臺作為媒介,為用戶提供大量有價值的信息.本文致力于尋找更有效地方法在提高用戶服務質(zhì)量的同時也保障云平臺提供商的利益最大化,而任務調(diào)度是實現(xiàn)更好云計算性能的重要部分,任務調(diào)度本質(zhì)上就是在多維的環(huán)境下,以求得完成任務的最短完成時間和最小成本[1].在云任務調(diào)度優(yōu)化過程中,一般有兩種的優(yōu)化方案,一種是傳統(tǒng)的任務調(diào)度算法,包括有最大最小分配算法(MAX-MIN),最小最小分配算法(MIN_MIN),先來先服務算法(FCFS)等等[2],但是都存在負載不均衡的問題,從而導致CPU利用率不高;還有一種是元啟發(fā)式算法,在本文中主要對元啟發(fā)式算法展開研究.經(jīng)過以往的實驗,證明元啟發(fā)式算法在任務調(diào)度問題上相對于傳統(tǒng)的調(diào)度算法更能發(fā)揮效用.

元啟發(fā)式算法大致分為兩大類:單解算法和基于群體的算法[3].在前一類中,針對特定函數(shù)隨機生成單個解,并進行改進,直到獲得最佳結(jié)果.基于單解的算法往往會陷入局部最優(yōu)解,那么得到的值就會與最低值產(chǎn)生較大偏差.在后一類中,在可取值的上下范圍內(nèi)隨機選擇出可行解,并增強解值,直到找到最佳解.基于群體的算法由于在迭代過程中豐富了解的多樣性,從而避免了多個局部最優(yōu)解.與基于單解的算法相比,基于群體的算法會檢查大量的搜索空間.因此,在基于群體的算法中,找到全局最優(yōu)解的概率很高.基于群體的算法相比于單解算法會在更廣闊的搜索空間內(nèi)搜索可行解,所以更容易找到最優(yōu)解,即更優(yōu)的任務調(diào)度方案[4].

在本文中針對利用元啟發(fā)式算法在多維環(huán)境下得到問題的最優(yōu)解展開討論.考慮到在云計算任務調(diào)度中,極少的涉及到樽海鞘算法.因此,在云計算中,為了尋找使得任務完成時間短、成本低的云任務調(diào)度方案,本文提出了一種改進的樽海鞘算法與云計算任務調(diào)度模型相結(jié)合的任務調(diào)度算法,使用CEC的多個單峰函數(shù)、多峰函數(shù)和復雜函數(shù)做測試,比較算法的性能,并且在 CloudSim上完成任務調(diào)度過程的模擬實驗,驗證了本文算法的高效性.

2 相關(guān)工作

Kramer O認為遺傳算法(Genetic Algorithm,GA)的基本思想是通過對種群中的個體進行交叉、變異、選擇等操作,不斷選擇更優(yōu)秀的個體,最終得到最優(yōu)秀的個體[5].由于交叉和變異過程的隨機性,算法往往不能快速收斂到最優(yōu)值[6].劉峰改進了遺傳算法,自提出了一個能雙面顧及到時間以及設備的負載均衡的適應度函數(shù),但在適應度函數(shù)中沒有涉及到對任務的完成成本的優(yōu)化[7].Sharma M提出Harmony-inspired genetic algorithm(HIGA)[8],結(jié)合了遺傳算法的探索能力和和聲搜索的開發(fā)能力,它可以智能地感知局部和全局最優(yōu)區(qū)域,而不會在局部或全局最優(yōu)區(qū)域浪費時間,并提供快速收斂.

粒子群優(yōu)化算法(PSO)實現(xiàn)簡單且有效,善于解決NP-Hard問題的應用程序,如調(diào)度問題和任務分配問題.齊平在自己的算法中考慮到了資源失效問題,提出了適應度函數(shù)評估任務的調(diào)度模型,但沒有考慮到任務的完成成本[9].王欣欣考慮到了完成時間和資源的消耗,且未考慮到任務完成成本[10].

蜉蝣優(yōu)化算法(A mayfly optimization algorithm,MA)將粒子群的個體分為雄性和雌性個體[11].此算法是混合了粒子群算法和遺傳算法的優(yōu)點,根據(jù)蜉蝣的求偶行為以及交配行為設計出的算法,在局部尋優(yōu)問題上有良好的表現(xiàn)[12].

靜電放電算法(Electrostatic Discharge Algorithm,ESDA)將多個電子設備作為種群,而電子設備在靜電放電的影響下會損壞設備,電子設備的適應度也由個體在搜索空間中的位置決定,在迭代過程中也會找到最高適應度的電子設備位置,獲得問題最優(yōu)解[13].

先來先服務調(diào)度算法(FCFS)主要是從“公平”的角度考慮,按照任務的先后順序進行調(diào)度.缺點在于排在后面的短作業(yè)的帶權(quán)周轉(zhuǎn)時間很大,對短任務的用戶體驗感不強[14,15].短作業(yè)優(yōu)先(SJF)算法[16]是選擇一個執(zhí)行時間最短的作業(yè)為其服務.但是又完全不考慮各個作業(yè)的等待時間,因此導致了對長作業(yè)不友好的問題,甚至還會造成饑餓問題.

樽海鞘算法(Salp Swarm Algorithm,SSA)利用了這種生物的活動規(guī)律,將群體分為了兩個群體,分別是領(lǐng)導者和跟隨者,領(lǐng)導者是位于食物鏈前端的樽海鞘,而其余樽海鞘則被視為追隨者[17].正如這些樽海鞘的名字所暗示的,領(lǐng)袖引導種群,追隨者互相跟隨直接或間接的領(lǐng)袖.本文就是基于該算法做出優(yōu)化并應用在云仿真平臺的任務調(diào)度系統(tǒng)中.

3 算法模型

3.1 Tent混沌映射

在生成初始化種群階段,Tent映射生成的個體在搜索空間中分布較為均勻,且本身結(jié)構(gòu)簡單,易于實現(xiàn),避免了隨機生成初始種群的不確定性.

3.2 領(lǐng)導者個體更新

將種群中1/5的個體作為領(lǐng)導者,作為樽海鞘鏈的頭部.領(lǐng)導者的個體根據(jù)食物的位置進行改變.

(1)

(2)

(3)

其中,j表示問題的維度,xj表示領(lǐng)導者樽海鞘的第j個維度,Fj表示第j維度的全局最優(yōu)位置,即食物的位置,r1隨著算法迭代逐漸減小,t表示當前迭代次數(shù),T表示最大迭代次數(shù),r2、r3是(0,1)之間的隨機數(shù),w在0～1.5之間波動.ubj和lbj是第j維度的最大和最小限度值.

3.3 跟隨者個體更新

跟隨者根據(jù)領(lǐng)導者的位置做更新.

(4)

(5)

(6)

其中,N表示種群中的個體數(shù),C1為0～2之間的隨機數(shù),xj表示領(lǐng)導者,xi表示當前個體,t是當前迭代次數(shù),T是最大迭代次數(shù),r1表示0～1之間的隨機數(shù).

3.4 群體反向?qū)W習

使用反向?qū)W習策略去搜索更多的位置,增加種群多樣性.

(7)

3.5 算法描述

LSA算法的整體流程如下:

Step1.輸入樣本的數(shù)目N,迭代次數(shù)Iter,可行解的上限值ub和下限值lb,基準函數(shù)fobj,問題維度dim;

Step2.利用Tent混沌映射的方式生成初始種群,便于之后做迭代優(yōu)化;

Step3.根據(jù)給定基準函數(shù)計算每個個體的適應度值;

Step4.根據(jù)公式(1)更新領(lǐng)導者粒子;

Step5.追隨者個體根據(jù)公式(4)更新;

Step6.根據(jù)公式(7)尋找追隨者的反向位置,對比尋找更優(yōu)秀的個體進行替補;

Step7.選擇新的種群加入下一次迭代當中,直到迭代次數(shù)完成,選出最優(yōu)解;

Step8.如果迭代到最后一次,輸出最優(yōu)的適應度函數(shù)值,否則,執(zhí)行Step 7.

算法流程圖如圖1所示.

圖1 算法流程圖Fig.1 Algorithm flow chart

4 CEC標準函數(shù)集

表1中顯示出各函數(shù)的設置維度以及搜索空間各個解的最高限度和最低限度.

表1 標準函數(shù)集Table 1 Standard set of functions

5 運行結(jié)果

在本節(jié)展示使用LSA算法以及其他經(jīng)典算法在測試集上運行所得的測試結(jié)果并進行分析.

5.1 CEC 2014運行結(jié)果

對于CEC2014測試集函數(shù)[18],以下展示出結(jié)果圖.對PSO,ESDA,MA,SSA,LSA等算法分別進行了測試,如圖2～圖5所示,從圖中可以看出LSA在搜索階段以及開發(fā)階段具有優(yōu)越性,尋優(yōu)結(jié)果更好.LSA的收斂速度較其他算法的性能快,且結(jié)果也比其他的算法更接近于最優(yōu)值.

圖2 F3測試Fig.2 F3 test result

圖3 F4測試Fig.3 F4 test result

圖4 F9測試Fig.4 F9 test result

圖5 F15測試Fig.5 F15 test result

進行多次實驗,如圖2～圖5所示,顯示出在F3、F4、F9和F15函數(shù)中,在一定的迭代次數(shù)下,通過對比找到更優(yōu)解,然后根據(jù)更優(yōu)解的位置在周圍加強搜索的深度以及反向位置尋找跳出局部最優(yōu)陷阱,增強搜索的廣度,LSA算法相比于其他算法能收斂到更優(yōu)值,收斂性好,穩(wěn)定性強,以F4單峰函數(shù)為例,在1000次的迭代次數(shù)內(nèi),LSA算法得到的函數(shù)最優(yōu)值更低,且收斂速度最快,是ESDA算法的最優(yōu)值的10-6倍,相比于其他算法也表現(xiàn)優(yōu)越.從表2中可以看出,使用多個測試函數(shù),在多個函數(shù)中LSA算法表現(xiàn)最好.在多峰函數(shù)和復雜函數(shù)方面,LSA在尋優(yōu)過程中也更好的跳出局部最優(yōu),找到性能更好的位置.

表2 對比測試顯示結(jié)果Table 2 Compare the results shown by the test

5.2 收斂性分析

LSA算法基于領(lǐng)導者和追隨者分別進行更新,根據(jù)公式(1),領(lǐng)導者的位置由r3決定根據(jù)哪一種方式進行更新,步調(diào)由控制因子w進行控制,隨著迭代次數(shù)的增加向最優(yōu)值位置逼近,逐漸收斂,追隨者跟著收斂,最終收斂到最優(yōu)值.

6 應用驗證

CloudSim是一種云計算中做任務調(diào)度研究中經(jīng)常使用的一種仿真軟件,模擬了云計算中虛擬化技術(shù),還提供了資源的監(jiān)測以及主機到虛擬機的映射.

云計算中的資源包括處理器,存儲器,網(wǎng)絡等都是按需使用的,按使用量計費的,且云計算同時需要向多個用戶提供服務,所以要考慮到每個用戶的響應時間,同時,也要考慮到服務所需的成本.因此本課題提出LSA對云計算中任務調(diào)度策略進行改進,以最大限度地提高云計算效率.

任務調(diào)度需要考慮所有子任務完成所需要的時間和成本.假設已知每個任務的任務長度,每個任務在每個虛擬機的處理速度,網(wǎng)絡寬帶的寬度以及每單位的計算資源所需要的成本,以下是設計的適應度函數(shù).

(8)

Ftime=Max(Timetrans[i][dcid]+Timeexec[i][dcid])

(9)

Timetrans[i][dcid]=cloudlength(i)/bw

(10)

Timeexec[i][dcid]=cloudlength(i)/mips(dcid)

(11)

fitness=α×Fcost+β×Ftime

(12)

其中,dcid是虛擬機的編號,Timetrans是將任務i發(fā)送到虛擬機上dcid需要的時間,Timeexec是將任務i在虛擬機上dcid執(zhí)行完成需要的時間,cost是每個單位的任務資源在虛擬機上運行的成本,α+β=1,控制時間和成本的影響比例.Fcost是運行所有任務所需要的成本,Ftime是完成所有任務所需要的時間.表3是使用多種經(jīng)典算法在CloudSim上的模擬結(jié)果.

表3 多種任務調(diào)度算法在CloudSim上模擬驗證結(jié)果Table 3 Multiple task scheduling algorithms simulate and verify the results on CloudSim

使用的對比算法有FCFS 算法,粒子群算法(PSO),模擬退火粒子群算法(SAPSO),自適應權(quán)重粒子群算法(SAWPSO),以及本文改進的樽海鞘算法(LSA).分別在任務數(shù)量為50、100、200、400的情況下,虛擬機數(shù)量為20、20、20、40,其他條件不變的情況下做對比.實驗證明,在任務數(shù)量相同的情況下,以任務的執(zhí)行時間和成本為任務指標,LSA分配的方案完成的時間更少且成本更低,大大的提高了解決問題的效率.

7 結(jié)論與展望

為了降低云計算中任務調(diào)度完成時間和成本,并且為了保證種群多樣性,避免收斂過快等問題,本文優(yōu)化了樽海鞘算法,并將其應用于任務調(diào)度中.針對空間搜索和尋優(yōu)能力不足的問題,提出了LSA算法,該算法使用群體反向?qū)W習的策略擴大搜索空間,跳出局部最優(yōu)化,改良了樽海鞘算法中更新粒子的方式,提高尋優(yōu)能力,提高搜索的深度與廣度.將任務的完成時間和成本作為性能指標,對任務調(diào)度過程中,優(yōu)化任務分配給虛擬機的分配方案,實現(xiàn)了合理的任務調(diào)度,縮短了任務的執(zhí)行時間和降低了執(zhí)行成本.

未來的工作中可以研究如何在規(guī)模更大的任務數(shù)量下優(yōu)化任務調(diào)度問題的解決方案,在成本、時間和資源等多維度上考慮任務的分配方案.