基于天牛須遺傳混合算法的大規(guī)模云任務(wù)調(diào)度

張 銳，王隨園，張春霞，王建喜，郭洪飛

(1.天津科技大學(xué)電子信息與自動化學(xué)院，天津 300222；2.航天銀山電氣有限公司，珠海 519090；3.暨南大學(xué)物聯(lián)網(wǎng)與物流工程研究院，珠海 519070)

云計算自2006年首次被Google公司提出以來，眾多大型互聯(lián)網(wǎng)公司相繼進入云計算市場，其中Amazon公司和 Microsoft公司相關(guān)云計算業(yè)務(wù)營收已達百億美元規(guī)模[1].云計算之所以發(fā)展如此迅速，是由于云計算擁有傳統(tǒng)計算不具備的超大規(guī)模、虛擬化、高可靠性等優(yōu)點[2].

目前，國內(nèi)外使用不同優(yōu)化策略求解云計算任務(wù)調(diào)度的算法研究有很多.文獻[3]提出改進貓群優(yōu)化算法，算法對云計算任務(wù)調(diào)度的時間、能耗和成本目標的優(yōu)化效果顯著.文獻[4]針對霧計算中任務(wù)調(diào)度問題，通過將遺傳算法與蟻群算法相結(jié)合，在減少調(diào)度時間的同時提高了內(nèi)存分配效率.文獻[5]將羅爾斯正義分配伯格模型和博弈算法運用到海量云計算資源調(diào)度上，提出的算法顯著提高了整體服務(wù)質(zhì)量.文獻[6]將微生物遺傳算法和改進粒子群算法結(jié)合，加入動態(tài)慣性權(quán)重策略，增強算法搜索能力，有效減少任務(wù)完成時間和執(zhí)行成本.文獻[7]建立新的資源分配模型，并采用珊瑚礁優(yōu)化算法，有效改善負載均衡問題的同時降低了執(zhí)行成本.文獻[8]針對工作流云任務(wù)調(diào)度優(yōu)化問題，提出匹配和多輪匹配算法，優(yōu)化結(jié)果可有效改善任務(wù)完成時間以及資源利用率.文獻[9]提出一種基于模糊自防御算法的云計算多目標任務(wù)調(diào)度優(yōu)化算法，在最大完成時間、截止期違規(guī)率和虛擬機資源利用率方面目標優(yōu)化效果明顯.

現(xiàn)有文獻大多沒有考慮大規(guī)模云任務(wù)調(diào)度算法的性能表現(xiàn)，隨著云計算服務(wù)應(yīng)用場景不斷擴展以及云計算用戶激增，如何快速合理分配海量云任務(wù)至計算資源成為目前研究的重要問題.云計算環(huán)境下任務(wù)調(diào)度研究是NP-hard問題[10]，運用傳統(tǒng)精確求解方法，計算量巨大且難以在可接受時間內(nèi)得到最優(yōu)解.

文獻[11]通過測試函數(shù)驗證了全局搜索的遺傳算法和個體尋優(yōu)天牛須搜索算法結(jié)合的優(yōu)越性.本文將該思想應(yīng)用于云任務(wù)調(diào)度領(lǐng)域，根據(jù)迭代進程動態(tài)改變交叉方式，既加快前期尋優(yōu)能力又避免算法早熟；采用精英解保留策略，保護最優(yōu)解不被交叉變異破壞；調(diào)整混合策略，增強算法局部尋優(yōu)能力.4種算法的對比實驗結(jié)果表明：本文提出的算法在任何規(guī)模云任務(wù)調(diào)度中，尤其是大規(guī)模云任務(wù)調(diào)度中，性能表現(xiàn)優(yōu)越.

1 云計算模型

在云計算中，獨立云任務(wù)調(diào)度的情況下：當(dāng)用戶將云任務(wù)提交至服務(wù)器時，云任務(wù)會被 Map/Reduce模型分割成若干獨立、不存在依賴關(guān)系的子任務(wù)，然后這些子任務(wù)根據(jù)調(diào)度算法被分配到不同虛擬機中執(zhí)行.云計算調(diào)度模型如圖1所示，所需研究問題主要分為一級調(diào)度問題和二級調(diào)度問題.如何將不同任務(wù)分配到不同虛擬機，被稱為一級調(diào)度問題；如何在不同容量物理機上分配不同性能的虛擬機，被稱為二級調(diào)度問題.在分配后的虛擬機中執(zhí)行一級調(diào)度分配的任務(wù)，則整個云計算調(diào)度過程完成，本文研究一級調(diào)度問題.

圖1 云計算調(diào)度模型Fig.1 Cloud computing scheduling model

根據(jù)本文所研究的問題，結(jié)合實際調(diào)度環(huán)境，作出如下假設(shè)：各云任務(wù)長度不同，且相互獨立；每臺虛擬機性能不同；調(diào)度任務(wù)個數(shù)遠大于虛擬機個數(shù)；分配到一臺物理機的所有虛擬機內(nèi)存大小、帶寬和計算速度等性能不能超過該物理機實際性能.

任務(wù)執(zhí)行時間主要與任務(wù)長度以及虛擬機運算速度相關(guān)，ETC表示各任務(wù)分配到各虛擬機的執(zhí)行時間，計算公式為

式中：ETC(i，j)表示任務(wù) i分配到虛擬機 j上的執(zhí)行時間，Taski表示任務(wù) i的大小，Capacityj表示虛擬機j的運算速度.

式(2)—式(4)中：Time(j)表示虛擬機 j執(zhí)行完所有分配任務(wù)所消耗的時間；cTime表示所有虛擬機中完成任務(wù)花費時間最長虛擬機的運行時間，即任務(wù)完成所需時間；Fitness表示個體適應(yīng)度.

適應(yīng)度越高，則任務(wù)完成所需時間越短，適應(yīng)度決定種群進化方向和個體被選擇的概率.

2 算法設(shè)計

2.1 遺傳算法

遺傳算法(GA)最初是由 Holland提出的一種優(yōu)化算法，主要針對非線性優(yōu)化問題.遺傳算法是目前最常見且有效的優(yōu)化算法之一，通過仿照生物進化過程中優(yōu)勝劣汰的進化規(guī)律，算法隨機選擇兩個父輩個體，并隨機挑選各自基因片段進行交換，同時，種群中少數(shù)個體由于某個或多個基因變異，同樣產(chǎn)生新的染色體；然后，根據(jù)每個個體對環(huán)境的適應(yīng)程度，決定個體繁殖概率，這樣擁有優(yōu)質(zhì)基因片段的高適應(yīng)度個體比例不斷增加，而適應(yīng)度低的個體隨著迭代的進行則被淘汰；最后，經(jīng)過若干次交叉變異后，留下最優(yōu)個體，即為全局最優(yōu)解或者近似全局最優(yōu)解.

但傳統(tǒng)遺傳算法存在一些不確定性，例如：容易過早收斂，導(dǎo)致后續(xù)迭代不能持續(xù)優(yōu)化；局部搜索能力差，遺傳算法擅長全局搜索最優(yōu)解[11]，傳統(tǒng)遺傳算法應(yīng)用在云計算任務(wù)調(diào)度中會導(dǎo)致任務(wù)分配結(jié)果十分不穩(wěn)定.一方面，云任務(wù)分配到虛擬機存在海量可行方案，尤其是面對大規(guī)模云任務(wù)調(diào)度時，極易發(fā)生“維數(shù)爆炸”問題；另一方面，遺傳算法自身的局部搜索能力不強，當(dāng)遇到大規(guī)模任務(wù)調(diào)度時，較難得到最優(yōu)解.

2.2 天牛須搜索算法

天牛須搜索算法(BAS)是通過模仿天牛的覓食過程開發(fā)出的一種算法.通過計算左右兩端適應(yīng)度，持續(xù)更新天牛個體解的位置，尋找最優(yōu)解.假設(shè)天牛個體解表示為 X＝(X1，X2，X3，…，Xn)，則天牛左右兩須解Xl和Xr分別為

式中：d表示天牛兩須中間位置與天牛須的距離；A表示隨機生成的方向不確定的單位向量，含義為天牛在解空間的方向.

天牛個體當(dāng)前位置 Xt通過不斷迭代，持續(xù)判斷左右兩須的適應(yīng)度并向適應(yīng)度高的方向移動，下一個位置Xt+1為

式中：δ表示天牛移動的步長，sign決定天牛移動的方向.

2.3 遺傳天牛須混合算法

針對傳統(tǒng)遺傳算法和天牛須搜索算法的優(yōu)缺點，將兩個算法進行改進，并將改進天牛須搜索算法作為改進遺傳算法種群適應(yīng)度優(yōu)化的算子，將兩個算法混合，提出 GA-BAS(genetic algorithm-beetle antennae search algorithm)算法，算法流程如圖2所示.

圖2 GA-BAS云任務(wù)調(diào)度算法流程圖Fig.2 Flow chart of cloud task scheduling algorithm

2.3.1 算法編碼

本研究屬于獨立云任務(wù)調(diào)度問題，不存在優(yōu)先關(guān)系.因此，本文采用實數(shù)直接編碼方式.一條染色體表示一種分配策略，染色體中基因個數(shù)代表任務(wù)調(diào)度過程中待分配子任務(wù)的個數(shù)，每個基因位置上的數(shù)字表示分配給該任務(wù)虛擬機的序號.染色體編碼示例如圖3所示，該示例中 T1—T8表示共計 8個云任務(wù)；V1—V5表示共計 5臺虛擬機，即染色體中每個基因可取的數(shù)值為 1～5.因此，該示例表示編號 1—8的云任務(wù)分別分配給2、3、1、4、5、2、3、5號虛擬機.

圖3 編碼示例Fig.3 Coding example

2.3.2 選擇算子

本文的選擇算子采用保留精英解策略，即：種群每次迭代前，適應(yīng)度最高的個體不進行任何交叉變異操作，直接替換適應(yīng)度最低的個體，保留到下一代中.這樣，既可以保護種群中最優(yōu)解不被交叉變異破壞，又可以提高種群平均適應(yīng)度.

2.3.3 交叉算子

交叉操作是傳統(tǒng)遺傳算法中產(chǎn)生新個體最重要的方法.交叉操作使不同個體中各自優(yōu)秀的基因相互結(jié)合，充分挖掘和組合優(yōu)質(zhì)解，隨著迭代進行，根據(jù)適者生存原則，不斷產(chǎn)生更優(yōu)質(zhì)的解，直至迭代結(jié)束，產(chǎn)生當(dāng)前最優(yōu)解.因此，交叉操作深刻影響算法性能和收斂速度.本文交叉操作選用片段交叉和點交叉相結(jié)合的方法，如圖4所示.

圖4 交叉操作示意圖Fig.4 Schematic diagram of cross operation

相比于片段交叉，單點交叉對解的改變更小，改變幅度更小，有利于找到最優(yōu)解.當(dāng)算法需要分配大量云任務(wù)至虛擬機時，在算法迭代的初始階段，選用片段交叉的方法，可以有效加快算法迭代速度，在算法迭代后半段，采用點交叉的方法，既可以改善算法局部搜索能力，也可以有效保護優(yōu)質(zhì)解不被破壞.

2.3.4 變異算子

變異對遺傳算法進化和產(chǎn)生新個體有輔助作用，在保持種群多樣性和避免早熟方面有一定作用.在一般情況下，個體適應(yīng)度越低，則該個體變異概率越大；相反，個體適應(yīng)度越高，則該個體變異概率越小.本文參考文獻[12]中自適應(yīng)變異概率方式：首先，隨機選擇一個基因位置；然后，產(chǎn)生一個隨機數(shù)，該隨機數(shù)最大值不超過虛擬機個數(shù)，用產(chǎn)生的隨機數(shù)代替該基因原有編號，產(chǎn)生新的個體.自適應(yīng)變異公式為

式中：p表示當(dāng)前個體變異概率，pmax表示種群進化過程中每個個體最大的變異概率，pmin表示種群進化過程中每個個體最小的變異概率，f表示當(dāng)前被選擇個體的適應(yīng)度，fmax表示種群中最優(yōu)個體的適應(yīng)度，favg表示種群中所有個體的平均適應(yīng)度.

2.3.5 混合策略

在算法執(zhí)行完選擇、交叉和變異后，混合 BAS算法：隨機選擇種群中一部分個體經(jīng)過 BAS算法尋優(yōu)，然后將產(chǎn)生的新種群替代舊種群.

傳統(tǒng) BAS算法只有左右兩個方向選擇，很大程度限制了搜索范圍，本文拓展天牛搜索方向，即：隨機產(chǎn)生n個右方向的單位向量，則對應(yīng)產(chǎn)生n個左方向的單位向量，如圖5所示，改進后天牛須搜索算法可以選擇多個方向，更有利于找到濃度高的信息點.

圖5 BAS算法模型Fig.5 BAS algorithm model

因此，本文通過改變天牛探索方向的個數(shù)，調(diào)節(jié)天牛須算法搜索范圍和尋優(yōu)能力，建立多方向感知模型，計算各個方向的適應(yīng)度，反饋給天牛搜索模型，決定天牛下次移動方向，單位向量A計算公式為

式中：rand表示隨機數(shù)函數(shù)，n為天牛右須探索方向的個數(shù)，D為個體解的維度.

為了避免BAS算法尋優(yōu)搜索使得種群多樣性降低，導(dǎo)致最優(yōu)解過早出現(xiàn)，本文設(shè)定每次迭代參與天牛須尋優(yōu)搜索的個體數(shù)量占種群規(guī)模的 50%.若BAS算法搜索到更優(yōu)位置，則更新位置，反之，保留當(dāng)前位置.最后判斷是否達到迭代次數(shù)，若達到迭代次數(shù)，則輸出種群中最優(yōu)個體，結(jié)束算法，反之，返回種群適應(yīng)度計算，繼續(xù)循環(huán).

3 實驗仿真

為了測試 GA-BAS算法的性能，本文選取傳統(tǒng)遺傳算法與 GA-BAS算法進行對比，使用 CloudSim 3.0云計算仿真平臺對云任務(wù)調(diào)度過程進行仿真.具體仿真實驗的配置條件為：Windows 10操作系統(tǒng)，Intel i5-8750處理器，8GB內(nèi)存，1TB硬盤.

3.1 仿真環(huán)境設(shè)置

為了保證各算法能夠進行合理比較，且仿真過程能順利進行，要在 CloudSim 運行仿真調(diào)度前設(shè)置仿真環(huán)境(物理機和虛擬機參數(shù)、云任務(wù)長度和傳輸數(shù)據(jù)大小)以及調(diào)度算法各參數(shù).本文云計算各運行條件設(shè)置與文獻[13]相同.作為云計算中最底層的計算資源，物理機性能參數(shù)直接影響云計算中調(diào)度任務(wù)的完成時間，本文設(shè)置兩種類別物理機，物理機參數(shù)見表1.物理機性能參數(shù)設(shè)置完成后，需要在物理機上分配若干個性能不同的虛擬機，虛擬機參數(shù)見表2.

表1 物理機參數(shù)Tab.1 Physical machine parameters

表2 虛擬機參數(shù)Tab.2 Virtual machine parameters

云任務(wù)的長度直接決定了云計算運行過程中計算量的大小，本文云任務(wù)采用隨機生成方式，云任務(wù)長度為5000～10000.

3.2 結(jié)果與分析

本文設(shè)置不同規(guī)模云任務(wù)量，并經(jīng)過多次仿真實驗，分析在不同規(guī)模任務(wù)量下算法的性能表現(xiàn).在相同仿真實驗條件下，將 GA-BAS算法和其他 3種對比算法通過各自分配策略將云任務(wù)分配到虛擬機上，算法參數(shù)見表3(SA為模擬退火算法).

表3 算法參數(shù)Tab.3 Algorithm parameters

3.2.1 小規(guī)模任務(wù)調(diào)度場景

設(shè)置 200個云任務(wù)分配給 40臺虛擬機，迭代100次.實驗結(jié)果如圖6所示.

圖6 小規(guī)模任務(wù)調(diào)度Fig.6 Small scale task scheduling

在小規(guī)模任務(wù)調(diào)度情況下，相比于 SA算法，BAS算法有更多局部搜索方向，也就有更強局部尋優(yōu)能力，因此BAS算法優(yōu)化結(jié)果比SA算法更好.但是，由于BAS算法和SA算法全局搜索能力差，優(yōu)化結(jié)果明顯低于其他兩種全局優(yōu)化算法.

在迭代初始階段，GA算法和GA-BAS算法差別不大，隨著迭代進行，GA算法在第 64代得到最優(yōu)解；而 GA-BAS算法得益于交叉策略動態(tài)改變和混合局部搜索能力強的天牛須搜索算法，在第 93代得到最優(yōu)解.

根據(jù)表4可知：通過多次小規(guī)模任務(wù)調(diào)度仿真實驗，相比于 GA 算法，GA-BAS算法優(yōu)化結(jié)果(迭代100次)的最小值、最大值和平均值分別提高了10.47%、4.30%和7.87%.

表4 小規(guī)模任務(wù)調(diào)度迭代100次結(jié)果對比Tab.4 Comparison of results of 100 iterations of small scale task scheduling

3.2.2 大規(guī)模任務(wù)調(diào)度場景

設(shè)置大規(guī)模任務(wù)調(diào)度，即：將20000個云任務(wù)分配到 400臺虛擬機上，由于任務(wù)調(diào)度規(guī)模巨大，因此將所有算法迭代次數(shù)提升至 200次.仿真實驗結(jié)果如圖7所示.

圖7 大規(guī)模任務(wù)調(diào)度Fig.7 Large scale task scheduling

由圖7可知：在大規(guī)模任務(wù)調(diào)度情況下，BAS算法、SA算法和GA算法優(yōu)化結(jié)果相近.其中，GA算法迭代曲線和小規(guī)模任務(wù)調(diào)度情況相似，收斂速度過快，在迭代第 57次后，優(yōu)化結(jié)果提升不大，并且在第136代得到最優(yōu)解，陷入了局部最優(yōu)解，導(dǎo)致后續(xù)迭代的計算資源被浪費.而 GA-BAS算法迭代曲線呈緩慢收斂態(tài)勢，并在第197代得到最優(yōu)解.

在迭代過程中，GA-BAS算法每一代最優(yōu)解都要優(yōu)于GA算法最優(yōu)解，這是由于大規(guī)模任務(wù)調(diào)度的調(diào)度方案數(shù)量巨大，這也就導(dǎo)致種群中個體需要局部尋優(yōu)方向增多，而傳統(tǒng)GA算法的交叉變異操作并不擅長局部搜索.一方面，GA-BAS算法加入改進 BAS算法后，擴大了算法搜索方向，能更好適應(yīng)大規(guī)模任務(wù)調(diào)度；另一方面，GA-BAS算法在迭代后期采用點交叉方式，使得個體基因變化幅度變小，相比于片段交叉，不易錯過更優(yōu)質(zhì)局部解.

由表5可知：經(jīng)過多次大規(guī)模任務(wù)調(diào)度仿真實驗，相比于 GA 算法，GA-BAS算法優(yōu)化結(jié)果(迭代200次)的最小值、最大值和平均值分別提高了38.46%、30.77%和30.23%，優(yōu)化效果提升明顯.

表5 大規(guī)模任務(wù)調(diào)度迭代200次結(jié)果對比Tab.5 Comparison of results of 200 iterations of large scale task scheduling

從以上兩種不同任務(wù)規(guī)模仿真實驗可知，本文提出的 GA-BAS混合算法優(yōu)化結(jié)果的平均值、最小值和最大值均優(yōu)于其他3種對比算法，尤其在大規(guī)模云任務(wù)調(diào)度場景下，GA-BAS算法優(yōu)化結(jié)果顯著優(yōu)于其他對比算法.得益于天牛須搜索算法強大的局部尋優(yōu)能力，使 GA-BAS算法擁有更強局部搜索能力和更穩(wěn)定的優(yōu)化結(jié)果，彌補了傳統(tǒng)遺傳算法局部搜索能力不強和容易過早收斂的問題；保留精英解策略可以有效保護優(yōu)質(zhì)解不被破壞，提升種群整體適應(yīng)度；提出新型交叉策略，在迭代前期采用片段交叉，加速算法收斂速度，在迭代后期采用點交叉方式，不僅增強算法在迭代早期的尋優(yōu)能力，而且有效避免算法在迭代后期過早收斂，同時保護優(yōu)質(zhì)解不被大范圍破壞，增加了算法局部尋優(yōu)能力；引入自適應(yīng)變異方式，根據(jù)迭代過程，動態(tài)調(diào)整變異概率，提升種群多樣性，避免算法早熟.

4 結(jié) 語

在云計算環(huán)境下，本文針對大規(guī)模任務(wù)調(diào)度效率低下的問題，同時考慮傳統(tǒng)遺傳算法應(yīng)用于云任務(wù)調(diào)度中的優(yōu)缺點，將傳統(tǒng)遺傳算法進行多方面改進，并加入改進天牛須搜索算法，提出GA-BAS算法，對云計算環(huán)境下任務(wù)調(diào)度問題進行優(yōu)化.實驗結(jié)果表明：該算法能夠有效減少大規(guī)模任務(wù)調(diào)度的完成時間，是一種高效云任務(wù)調(diào)度算法.未來研究方向可以完整考慮整個云計算所有調(diào)度過程，加入 Map/Reduce模型分割任務(wù)過程，同時增加二級調(diào)度，即：物理機分配虛擬機過程.