基于改進(jìn)GA的云計(jì)算任務(wù)調(diào)度策略*

任金霞， 劉 敏

(江西理工大學(xué) 電氣工程與自動(dòng)化學(xué)院， 江西 贛州 341000)

隨著計(jì)算機(jī)技術(shù)的迅猛發(fā)展，云計(jì)算技術(shù)已成為現(xiàn)今社會(huì)的一個(gè)研究熱點(diǎn)和重點(diǎn).云計(jì)算是在分布式計(jì)算、網(wǎng)格計(jì)算和并行計(jì)算等基礎(chǔ)上發(fā)展起來(lái)的一種全新的大規(guī)模計(jì)算模式，利用虛擬技術(shù)和高速網(wǎng)絡(luò)技術(shù)來(lái)解決大規(guī)模的大數(shù)據(jù)處理問(wèn)題，有很多企業(yè)做出較大投入且獲得很好的成果，如亞馬遜的‘彈性云’、IBM的‘藍(lán)云’、Google的超大搜索引擎和微軟的‘Windows Azure’等.隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，互聯(lián)網(wǎng)數(shù)據(jù)量會(huì)越來(lái)越大，對(duì)云計(jì)算技術(shù)的要求也越來(lái)越高，用戶要求以最小的時(shí)間跨度來(lái)完成任務(wù)，同時(shí)企業(yè)要求盡可能帶來(lái)盈利，關(guān)于云計(jì)算任務(wù)調(diào)度策略的研究成為研究重點(diǎn)，現(xiàn)在較常用的云任務(wù)調(diào)度策略主要有蟻群算法[1]、遺傳算法[2]和粒子群算法[3]等啟發(fā)式仿生算法及其改進(jìn)算法，Min-min算法[4]等非仿生式算法及其改進(jìn)算法.

企業(yè)型云計(jì)算是以盈利為目的，所以很多文獻(xiàn)的任務(wù)調(diào)度策略中心主要是以任務(wù)完成時(shí)間和任務(wù)完成成本為優(yōu)化目標(biāo).文獻(xiàn)[5]為避免早熟現(xiàn)象等問(wèn)題提出了一種基于負(fù)載均衡和任務(wù)時(shí)間的雙適應(yīng)度函數(shù)改進(jìn)遺傳算法；文獻(xiàn)[6]針對(duì)傳統(tǒng)遺傳算法迭代次數(shù)多和耗時(shí)久的問(wèn)題提出了一種以執(zhí)行時(shí)間和執(zhí)行費(fèi)用為優(yōu)化目標(biāo)的改進(jìn)遺傳算法；文獻(xiàn)[7]提出了一種考慮時(shí)間和成本約束的改進(jìn)遺傳算法.但是，這些文獻(xiàn)針對(duì)未成熟收斂現(xiàn)象均未提出較好的改進(jìn)辦法，在遺傳算法后期可能會(huì)出現(xiàn)總是淘汰接近最優(yōu)解的個(gè)體或者所有個(gè)體陷入同一極值而終止算法的情況，無(wú)法達(dá)到降低任務(wù)完成時(shí)間和成本的優(yōu)化目標(biāo).

本文提出了基于任務(wù)完成時(shí)間和任務(wù)完成成本的雙適應(yīng)度函數(shù)的改進(jìn)遺傳算法(time and cost genetic algorithm，TCGA)，引入個(gè)體相似度概念和采用并列選擇法進(jìn)行選擇遺傳操作，盡可能保證種群多樣性，同時(shí)在算法后期采用加速收斂策略加快算法的收斂速度.

1 云計(jì)算任務(wù)調(diào)度

現(xiàn)今社會(huì)上采用的云計(jì)算編程模式是1995年由Google公司提出的Map/Reduce模式，這種模式是把云任務(wù)分成若干個(gè)子任務(wù)，各子任務(wù)按要求隨機(jī)分配給虛擬機(jī)上的資源計(jì)算節(jié)點(diǎn)并執(zhí)行，最后將結(jié)果進(jìn)行整合處理輸出，各任務(wù)或子任務(wù)之間是相互獨(dú)立的，在虛擬機(jī)上進(jìn)行并行運(yùn)算.這樣可以減少任務(wù)執(zhí)行時(shí)間且降低成本損耗，但各虛擬資源計(jì)算節(jié)點(diǎn)的任務(wù)處理性能有差異，所以各子任務(wù)完成時(shí)間不同，同時(shí)各虛擬資源計(jì)算節(jié)點(diǎn)完成任務(wù)的單位成本不同，產(chǎn)生的成本消耗也不同.

各虛擬資源計(jì)算節(jié)點(diǎn)單位時(shí)間完成單位任務(wù)所產(chǎn)生的成本損耗為單位成本.云計(jì)算采用的是按需收費(fèi)、即時(shí)付費(fèi)的資源服務(wù)模式，一般滿足以下幾個(gè)條件：

1) 為了有利于虛擬機(jī)的任務(wù)執(zhí)行，云任務(wù)會(huì)被分解成若干個(gè)大小均勻的子任務(wù)，子任務(wù)會(huì)被隨機(jī)地分配在不同的虛擬資源上執(zhí)行；

2) 每個(gè)子任務(wù)在虛擬資源計(jì)算節(jié)點(diǎn)上的執(zhí)行時(shí)間是可監(jiān)控的、可計(jì)算的；

3) 每個(gè)虛擬資源計(jì)算節(jié)點(diǎn)的單位成本是可估算的、已知的.

每個(gè)計(jì)算節(jié)點(diǎn)完成的子任務(wù)所用的時(shí)間可表示為etcij，etcij為資源節(jié)點(diǎn)j執(zhí)行子任務(wù)i所消耗的時(shí)間，costij為資源節(jié)點(diǎn)j執(zhí)行子任務(wù)i的成本消耗，costj為資源節(jié)點(diǎn)j的單位成本，則有costij=costj·etcij.

(1)

式中：task(k)_lengthi為云任務(wù)k中的子任務(wù)i的長(zhǎng)度，i∈{1，2，…，m}；mipsj為虛擬資源j的處理性能，j∈{1，2，…，n}.云計(jì)算環(huán)境下的子任務(wù)在虛擬資源中進(jìn)行計(jì)算時(shí)是并行獨(dú)立完成的，所以子任務(wù)在各虛擬資源中執(zhí)行時(shí)間的最大值為云任務(wù)調(diào)度的執(zhí)行時(shí)間花費(fèi)ExecuteTime，任務(wù)完成時(shí)間CompleteTime為任務(wù)執(zhí)行時(shí)間與任務(wù)傳輸時(shí)間之和，云任務(wù)在各虛擬資源的執(zhí)行成本花費(fèi)ExcuteCost與傳輸成本花費(fèi)求和即為任務(wù)調(diào)度總成本花費(fèi)CompleteCost.云任務(wù)k的執(zhí)行時(shí)間為

(2)

云任務(wù)在虛擬資源上的傳輸時(shí)間為

(3)

式中，transj為虛擬資源j的傳輸性能.任務(wù)完成時(shí)間為任務(wù)執(zhí)行時(shí)間與任務(wù)傳輸時(shí)間之和，即

CompleteTimek=ExecuteTimek+ttkj

(4)

云任務(wù)k的總成本花費(fèi)為任務(wù)執(zhí)行成本與傳輸成本之和，即

(5)

式中，costtj為虛擬資源j的傳輸成本.

2 改進(jìn)遺傳算法

2.1 遺傳算法

遺傳算法是1967年美國(guó)Michigan大學(xué)Holland教授和他的學(xué)生們受生物模擬技術(shù)啟發(fā)，提出的一種基于生物基因遺傳和進(jìn)化機(jī)制的自適應(yīng)概率優(yōu)化算法.遺傳算法具有高效性、高魯棒性和實(shí)用性，發(fā)展極為迅速，自提出后，在工程技術(shù)、科學(xué)計(jì)算和社會(huì)經(jīng)濟(jì)等方面被大面積的引用吸收，引起了全世界范圍有關(guān)學(xué)者的高度重視[8-11].

遺傳算法的優(yōu)點(diǎn)很多，但是經(jīng)過(guò)多年的發(fā)展和完善，依然存在許多問(wèn)題未得到解決，例如：

1) 遺傳算法易陷入早熟中，迄今為止沒(méi)有得到很好的解決辦法；

2) 在遺傳算法后期，最優(yōu)解會(huì)出現(xiàn)左右擺動(dòng)情況，導(dǎo)致收斂速度變慢.

2.2 編碼與解碼

圖1 任務(wù)資源映射關(guān)系Fig.1 Task-resource mapping relationship

若長(zhǎng)度為l的染色體為{1，3，4，2，3，m-2，1，3，…，m，m-1}，則任務(wù)與虛擬資源的映射關(guān)系如表1所示.

表1 映射關(guān)系Tab.1 Mapping relationship

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)值在一定程度上決定了個(gè)體被選作為父代遺傳到下一代的概率，適應(yīng)度值較大的遺傳到下一代的概率較大，適應(yīng)度值較小的遺傳到下一代的概率較小，所以適應(yīng)度函數(shù)的選擇很關(guān)鍵，本文選擇的適應(yīng)度函數(shù)是任務(wù)完成時(shí)間適應(yīng)度函數(shù)和任務(wù)完成成本適應(yīng)度函數(shù).時(shí)間適應(yīng)度函數(shù)為

(6)

(7)

式中：ulb為任務(wù)平衡負(fù)載因子，表示虛擬資源的利用率情況，ulb越大表示虛擬資源利用率越高；CompleteTimemax為任務(wù)完成時(shí)間的最大值.成本適應(yīng)度函數(shù)為

還可以利用多媒體將一些破壞環(huán)境的圖片或視頻播放出來(lái)，將環(huán)境受到破壞的情境展現(xiàn)出來(lái)，如水污染、土地沙化、臭氧層空洞等。通過(guò)這些觸目驚心的圖片，讓學(xué)生明白環(huán)境保護(hù)的重要性。同時(shí)給出一些利用化學(xué)知識(shí)保護(hù)環(huán)境的方法，如，盡量減少塑料袋的使用、少用或不用一次性筷子等。或是組織學(xué)生討論化工廠選址問(wèn)題，通過(guò)親自參與活動(dòng)的方式，加深對(duì)化學(xué)知識(shí)的理解，樹(shù)立起可持續(xù)發(fā)展理念，完成傳統(tǒng)文化元素的滲透，提高化學(xué)教學(xué)質(zhì)量。

(8)

任務(wù)完成所花費(fèi)時(shí)間越少的分配策略越接近最優(yōu)解，運(yùn)行算法所需的成本代價(jià)越低其適應(yīng)度值越大.

3 遺傳操作

3.1 個(gè)體相似度

傳統(tǒng)遺傳算法執(zhí)行一段時(shí)間后，個(gè)體之間的相似性增大，易陷入局部最優(yōu)中，本文提出個(gè)體相似度的概念來(lái)約束個(gè)體之間的相似性，加快算法的收斂速度，避免算法陷入局部最優(yōu)的情況.個(gè)體染色體的長(zhǎng)度為l，虛擬資源數(shù)為n，兩個(gè)個(gè)體之間的海明碼距為

(9)

其中，

(10)

相似度為

(11)

3.2 選擇操作

選擇操作是遺傳算法的基本操作，使用比例算子進(jìn)行運(yùn)算，選擇操作的目的是為了從當(dāng)前種群中選出優(yōu)秀的個(gè)體，使其有機(jī)會(huì)作為父體把優(yōu)良的基因通過(guò)繁殖遺傳給下一代.為了保證種群個(gè)體多樣性，個(gè)體相似度大于90%的保留適應(yīng)度值大的個(gè)體，適應(yīng)度值小的個(gè)體被淘汰.本文主要從時(shí)間適應(yīng)度函數(shù)和成本適應(yīng)度函數(shù)來(lái)考慮，個(gè)體的適應(yīng)度值越大，被選中作為父代繁殖遺傳的可能性就越大，反之越小.種群中個(gè)體被選中的概率為

(12)

式中，fiti為個(gè)體i的適應(yīng)度函數(shù)值.

本文采用最優(yōu)保存策略進(jìn)行選擇操作，在選擇操作時(shí)，把種群中所有個(gè)體的適應(yīng)度函數(shù)值按照從大到小的順序排列，首先把適應(yīng)度值最大的0.5%的個(gè)體去掉，再把剩下的前10%的個(gè)體直接入選到子代種群中，剩余的個(gè)體通過(guò)輪盤賭算法進(jìn)行個(gè)體選擇.本文采用并列選擇法對(duì)時(shí)間適應(yīng)度值和成本適應(yīng)度值進(jìn)行選擇，即按上述選擇方法分別選出合適時(shí)間適應(yīng)度值的個(gè)體和成本適應(yīng)度值的個(gè)體，再與通過(guò)交叉和變異遺傳操作生成新的個(gè)體共同組成新的子代種群.在選擇這個(gè)遺傳操作過(guò)程中可能會(huì)淘汰一些染色體，為了保證種群的規(guī)模，每次遺傳操作開(kāi)始前添加隨機(jī)生成的若干個(gè)個(gè)體保持種群規(guī)模不變.

3.3 交叉和變異操作

交叉操作是按概率從種群中選出兩個(gè)個(gè)體交換彼此的某個(gè)或某些位產(chǎn)生新的子代，交叉操作的方式有很多，如單點(diǎn)交叉、均勻交叉和多點(diǎn)交叉等.變異操作是以較小的概率將個(gè)體的某個(gè)或某些位值變異為其他等位基因生成新的個(gè)體，變異方式有基本位變異和均勻變異等.交叉和變異操作決定了遺傳算法的尋優(yōu)搜索能力.交叉概率公式為

(13)

(14)

式中：fiti為種群中要變異的個(gè)體的適應(yīng)度值；k3為變異概率調(diào)節(jié)常數(shù)；k4為變異概率常數(shù).當(dāng)要變異個(gè)體適應(yīng)度值較大時(shí)(fiti≥fitavg)，適應(yīng)度值越大，變異的可能性越小，在一定程度上防止較優(yōu)個(gè)體被破壞.

在遺傳算法后期會(huì)出現(xiàn)適應(yīng)度值很集中的情況，這種情況很大程度上降低了算法的收斂速度.本文提出加速收斂策略[12]，當(dāng)種群個(gè)體適應(yīng)度值的最大值和最小值差與適應(yīng)度值平均值的比值ω小于收斂閾值θ時(shí)，調(diào)節(jié)交叉概率調(diào)節(jié)常數(shù)k1和變異概率調(diào)節(jié)常數(shù)k3，使得個(gè)體的交叉和變異概率變大，加快局部搜索速度，提高算法的收斂速度.

3.4 種群初始化

設(shè)種群的大小規(guī)模為S，云任務(wù)總數(shù)為TASK，子任務(wù)數(shù)為m，虛擬資源數(shù)為n，則種群初始化可描述為：由系統(tǒng)隨機(jī)生成S個(gè)長(zhǎng)度為m的染色體，基因值為[1，n]之間的隨機(jī)數(shù).

3.5 算法流程

圖2為算法流程圖.由系統(tǒng)隨機(jī)生成初始種群，計(jì)算種群中個(gè)體的適應(yīng)度值，并按遺傳操作進(jìn)行執(zhí)行尋找最優(yōu)解，步驟如下：

1) 種群初始化.系統(tǒng)隨機(jī)生成大小規(guī)模為S的初始種群.

2) 終止算法條件.算法迭代次數(shù)是否達(dá)到最大值或找到最優(yōu)解，是則終止算法；否則繼續(xù)執(zhí)行.

3) 選擇操作.計(jì)算種群個(gè)體適應(yīng)度函數(shù)值，排列后通過(guò)最優(yōu)保存策略選取前10%為下一代種群個(gè)體，采用輪盤賭方式對(duì)剩余個(gè)體進(jìn)行選擇操作.

4) 交叉操作.隨機(jī)選取兩個(gè)個(gè)體進(jìn)行交叉操作生成新種群的個(gè)體.

圖2 算法流程圖Fig.2 Flow chart of algorithm

5) 變異操作.隨機(jī)選擇一個(gè)個(gè)體進(jìn)行變異操作生成新種群的個(gè)體.

6) 對(duì)新生成種群個(gè)體進(jìn)行判斷篩選是否找到最優(yōu)解，有則輸出結(jié)果；無(wú)則跳轉(zhuǎn)到步驟2)中.

4 仿真實(shí)驗(yàn)結(jié)果分析

本文采用墨爾本大學(xué)Buyya教授領(lǐng)導(dǎo)開(kāi)發(fā)的CloudSim仿真模擬器對(duì)算法進(jìn)行仿真模擬實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行比較分析.將本文方法與遺傳算法、文獻(xiàn)[5]中的SAIGA算法進(jìn)行實(shí)驗(yàn)對(duì)比，分析比較各算法在不同情況下的任務(wù)完成時(shí)間、任務(wù)完成成本和收斂結(jié)果.對(duì)算法中的各參數(shù)取值進(jìn)行初始化，如表2所示.

表2 參數(shù)初始化Tab.2 Parameter initialization

算法初始條件：種群規(guī)模S取值為30，子任務(wù)數(shù)m取值為1 000，虛擬資源n取值為10，虛擬資源的單位成本costj和傳輸成本costtj由系統(tǒng)隨機(jī)生成，算法的最大迭代次數(shù)設(shè)置為100.實(shí)驗(yàn)結(jié)果如圖3～5所示.

圖3 任務(wù)完成時(shí)間對(duì)比Fig.3 Comparison of task completion time

圖3中總?cè)蝿?wù)數(shù)量為1 000個(gè)，從圖3中可以看出，在相同任務(wù)數(shù)量情況下，分別運(yùn)行遺傳算法、TCGA算法和SAIGA算法，在迭代次數(shù)較少時(shí)，3種算法的任務(wù)完成時(shí)間各不相同，TCGA算法花費(fèi)時(shí)間最少，遺傳算法花費(fèi)時(shí)間最多，但是3種算法花費(fèi)的時(shí)間相差較小；隨著迭代次數(shù)的增多，3種算法花費(fèi)的時(shí)間差距越來(lái)越大，在最大迭代次數(shù)的情況下，TCGA算法的任務(wù)完成時(shí)間比遺傳算法和SAIGA算法分別降低了13%和8%.

圖4 任務(wù)完成成本對(duì)比Fig.4 Comparison of task completion cost

圖5 收斂結(jié)果對(duì)比Fig.5 Comparison of convergence results

圖4中總?cè)蝿?wù)數(shù)量為1 000個(gè)，從圖4中可以看出，TCGA算法、遺傳算法和SAIGA算法在算法初期，任務(wù)完成成本相差不大；隨著算法迭代次數(shù)的增多，3種算法的任務(wù)完成成本會(huì)降低且降低的程度各不相同，算法之間的任務(wù)完成成本差距變大，TCGA算法的任務(wù)完成成本相比較于遺傳算法和SAIGA算法分別降低了4%和3%.

圖5中總?cè)蝿?wù)數(shù)量為1 000個(gè)，從圖5中可以看出，TCGA算法、遺傳算法和SAIGA算法的收斂速度各不相同，隨著迭代次數(shù)的增加，收斂所需時(shí)間差距變大，遺傳算法的收斂速度最慢，TCGA算法的收斂速度更快，尋優(yōu)時(shí)間最短.

綜上分析可知，本文提出的雙適應(yīng)度函數(shù)改進(jìn)遺傳算法的任務(wù)完成時(shí)間更短，成本更低，收斂速度更快，尋優(yōu)能力更強(qiáng)，能較好地完成云任務(wù)調(diào)度問(wèn)題.

5 結(jié) 論

云計(jì)算調(diào)度優(yōu)化策略通常是以任務(wù)完成時(shí)間和任務(wù)完成成本為優(yōu)化目標(biāo)，本文提出并列選擇法根據(jù)適應(yīng)度函數(shù)值確定選擇概率完成選擇操作，把任務(wù)完成時(shí)間和任務(wù)完成成本作同等地位來(lái)處理云計(jì)算任務(wù)調(diào)度的優(yōu)化問(wèn)題，這樣能根據(jù)各自優(yōu)化目標(biāo)函數(shù)選出符合要求的個(gè)體，本文算法沒(méi)有考慮其他因素對(duì)云任務(wù)調(diào)度過(guò)程的影響，如網(wǎng)絡(luò)服務(wù)質(zhì)量等，下一步討論研究需要把這些因素考慮在內(nèi).