基于改進(jìn)GA 的云計(jì)算任務(wù)調(diào)度算法研究

姜學(xué)文

摘要：在當(dāng)前的社會(huì)當(dāng)中，隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展，云計(jì)算逐漸成為一種主要的計(jì)算方式。而在云計(jì)算當(dāng)中，任務(wù)調(diào)度算法發(fā)揮著重要的作用。對(duì)此，應(yīng)當(dāng)對(duì)計(jì)算資源進(jìn)行合理的分配，對(duì)任務(wù)調(diào)度算法進(jìn)行改進(jìn)，從而進(jìn)一步提升云計(jì)算的效率。基于此，本文對(duì)考慮時(shí)間-成本約束的遺傳算法的改進(jìn)GA任務(wù)調(diào)度算法進(jìn)行了分析和研究，從而更好發(fā)揮出云計(jì)算的作用和效果。

關(guān)鍵詞：改進(jìn)GA；云計(jì)算；任務(wù)調(diào)度算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）13-0177-02

云計(jì)算是當(dāng)前網(wǎng)絡(luò)中一種基于云平臺(tái)提供的運(yùn)算服務(wù)，其中包含軟件、平臺(tái)、基礎(chǔ)設(shè)施等服務(wù)，通過(guò)互聯(lián)網(wǎng)，拆分處理任務(wù)，使之形成若干小任務(wù)，然后通過(guò)多個(gè)服務(wù)器系統(tǒng)進(jìn)行計(jì)算分析和搜索，并向用戶傳遞結(jié)果。在云計(jì)算當(dāng)中，包括網(wǎng)格計(jì)算、并行計(jì)算、分布式計(jì)算等方面的內(nèi)容。在云計(jì)算中，具有龐大的計(jì)算任務(wù)，因此任務(wù)調(diào)度十分重要，對(duì)于云計(jì)算的效率來(lái)說(shuō)，也有著直接的影響。

1 任務(wù)調(diào)度的基本概述

在當(dāng)前的云計(jì)算領(lǐng)域當(dāng)中，對(duì)Google的Map/Reduce編程模型的應(yīng)用較為廣泛，能夠并行計(jì)算大規(guī)模的數(shù)據(jù)集。通過(guò)對(duì)大任務(wù)的劃分，利用多個(gè)計(jì)算資源對(duì)劃分的小任務(wù)進(jìn)行并行執(zhí)行，最后對(duì)最終的計(jì)算結(jié)果進(jìn)行匯總。云計(jì)算在提供服務(wù)的過(guò)程中，應(yīng)當(dāng)面向多個(gè)用戶，因此對(duì)各個(gè)用戶的響應(yīng)時(shí)間應(yīng)加以考慮，并且應(yīng)當(dāng)對(duì)服務(wù)所需成本進(jìn)行考慮。而在一些傳統(tǒng)的調(diào)度算法中，往往難以對(duì)所有的因素進(jìn)行考慮，因而難以同時(shí)兼顧到時(shí)間和成本[1]。在云計(jì)算當(dāng)中，主要有網(wǎng)絡(luò)、存儲(chǔ)器、處理器等資源，在應(yīng)用過(guò)程中，根據(jù)用量和需求進(jìn)行使用和付費(fèi)。在云計(jì)算當(dāng)中，任務(wù)調(diào)度算法能夠向各個(gè)計(jì)算資源中更加合理的分配子任務(wù)，從而縮短任務(wù)執(zhí)行時(shí)間，降低任務(wù)執(zhí)行成本。

2 幾種任務(wù)調(diào)度算法的比較

在云計(jì)算環(huán)境下，基于相同的條件，對(duì)考慮成本約束的遺傳算法、考慮時(shí)間約束的遺傳算法、考慮時(shí)間-成本約束的遺傳算法等進(jìn)行了比較分析。在實(shí)驗(yàn)研究當(dāng)中，在初期的遺傳算法進(jìn)化階段，對(duì)于總?cè)蝿?wù)完成時(shí)間來(lái)說(shuō)，這三種遺傳算法都能夠得到基本相似的最優(yōu)子任務(wù)調(diào)度結(jié)果。而在不斷增加進(jìn)化代數(shù)的條件下，對(duì)于總?cè)蝿?wù)完成時(shí)間來(lái)說(shuō)，考慮成本約束的遺傳算法、考慮時(shí)間-成本約束的遺傳算法能夠得到更加良好的結(jié)果，而考慮時(shí)間約束的遺傳算法則難以取得較為理想的效果[2]。由此可見，在考慮成本約束的遺傳算法中，能夠得到最小總?cè)蝿?wù)完成成本的子任務(wù)調(diào)度結(jié)果，但是難以有效的優(yōu)化任務(wù)完成時(shí)間。而考慮時(shí)間約束的遺傳算法，能夠得到最短任務(wù)完成時(shí)間的子任務(wù)調(diào)度結(jié)果，但是難以有效的優(yōu)化任務(wù)執(zhí)行成本。在考慮時(shí)間-成本約束的遺傳算法當(dāng)中，由于同時(shí)對(duì)任務(wù)的時(shí)間和成本進(jìn)行了考慮，因而在任務(wù)調(diào)度當(dāng)中，能夠取得更為理想的子任務(wù)調(diào)度結(jié)果，更好的提升云計(jì)算的效率和效益。

3 考慮時(shí)間-成本約束的遺傳算法

1） 染色體的編碼解碼

在編碼方式方面，染色體十分豐富，能夠?qū)﹂g接編碼和直接編碼的方式進(jìn)行應(yīng)用。子任務(wù)的數(shù)量，可看作染色體的長(zhǎng)度，在染色體當(dāng)中，根據(jù)子任務(wù)占用資源的具體編號(hào)，對(duì)基因取值進(jìn)行確定。在初始種群的產(chǎn)生過(guò)程中，每一個(gè)染色體會(huì)隨機(jī)生成資源編號(hào)，在變異、較差算子之后，子任務(wù)會(huì)對(duì)任意的可用資源進(jìn)行占用，因此，在最優(yōu)解當(dāng)中，都會(huì)有染色體編碼與之相對(duì)應(yīng)。在染色體生成之后，應(yīng)當(dāng)對(duì)其進(jìn)行解碼操作，從而對(duì)子任務(wù)分布在不同資源中的情況加以了解。根據(jù)占用資源的不同，對(duì)子任務(wù)進(jìn)行劃分，根據(jù)資源編號(hào)，得到多組子任務(wù)的分類序列，然后對(duì)相應(yīng)的染色體進(jìn)行解碼[3]。在解碼之后，對(duì)于計(jì)算資源中分配的子任務(wù)，能夠?qū)ζ湫蛄羞M(jìn)行了解。通過(guò)對(duì)ETC矩陣進(jìn)行應(yīng)用，對(duì)于計(jì)算資源中，子任務(wù)序列的完成時(shí)間，能夠進(jìn)行準(zhǔn)確的計(jì)算。在云計(jì)算當(dāng)中，計(jì)算資源當(dāng)中都有著并發(fā)處理的特點(diǎn)，因而在計(jì)算中，根據(jù)最大的計(jì)算結(jié)果，確定為子任務(wù)完成的具體時(shí)間。在考慮時(shí)間-成本約束的遺傳算法當(dāng)中，由于對(duì)完成子任務(wù)的成本、時(shí)間等都要加以考慮，因此可采用貪心算法對(duì)子任務(wù)完成的最大成本、最大時(shí)間等進(jìn)行計(jì)算。

2） 適應(yīng)度函數(shù)

在基于改進(jìn)遺傳算法的云計(jì)算任務(wù)調(diào)度算法當(dāng)中，選擇適當(dāng)?shù)倪z傳算法適應(yīng)度函數(shù)，能夠發(fā)揮出良好的效果，對(duì)于遺傳算法中查找最優(yōu)解、收斂速度等，都有著直接的影響。如果個(gè)體具有較大的適應(yīng)度，其就有更大的概率向下一代進(jìn)行遺傳。如果個(gè)體的適應(yīng)度較小，則其就有較小的概率向下一代進(jìn)行遺傳。在任務(wù)調(diào)度的過(guò)程中，應(yīng)當(dāng)對(duì)完成所有子任務(wù)需要的時(shí)間、成本等問題進(jìn)行考慮。在定義時(shí)間的適應(yīng)度函數(shù)當(dāng)中，涉及平衡任務(wù)負(fù)載因子這一參數(shù)，能夠?qū)Σ煌?jì)算資源的實(shí)際利用率進(jìn)行反映[4]。如果平衡任務(wù)負(fù)載因子具有較大的數(shù)值，則說(shuō)明計(jì)算資源具有較高的利用效率，因而任務(wù)完成時(shí)間就會(huì)相應(yīng)的較短。在定義成本的適應(yīng)度函數(shù)當(dāng)中，可根據(jù)任務(wù)完成時(shí)間進(jìn)行計(jì)算。在適應(yīng)度函數(shù)當(dāng)中，如果只對(duì)之間約束進(jìn)行考慮，在越高的計(jì)算資源利用率之下，如果子任務(wù)個(gè)體需要較短的時(shí)間就能夠完成子任務(wù)，就有較大的適應(yīng)度。而如果適應(yīng)度函數(shù)只對(duì)成本約束進(jìn)行考慮，子任務(wù)個(gè)體需要較低的成本就能夠完成任務(wù)，也會(huì)具有較大的適應(yīng)度。所以，在對(duì)考慮時(shí)間-成本約束的遺傳算法的適應(yīng)度函數(shù)進(jìn)行定義的過(guò)程中，應(yīng)當(dāng)對(duì)時(shí)間、成本等約束進(jìn)行綜合性的考慮，從而得到更加準(zhǔn)確的任務(wù)調(diào)度結(jié)果。

3） 遺傳操作

在遺傳操作當(dāng)中，主要包括選擇操作、交叉操作、變異操作等。在選擇操作當(dāng)中，將具有較強(qiáng)適應(yīng)度的個(gè)體在種群中進(jìn)行選擇，從而對(duì)新種群的形成過(guò)程進(jìn)行產(chǎn)生。從優(yōu)勝劣汰的基本原則中，如果個(gè)體具有越高的適應(yīng)度，就會(huì)由更大的概率向下一代進(jìn)行遺傳，因而在種群當(dāng)中，能夠連續(xù)的優(yōu)化適應(yīng)度，從而向最優(yōu)解進(jìn)行不斷靠近[5]。在考慮時(shí)間-成本約束的遺傳算法當(dāng)中，選擇操作因子為輪盤賭選擇的方式，根據(jù)相應(yīng)的公式對(duì)個(gè)體被選擇概率進(jìn)行計(jì)算。在適應(yīng)度函數(shù)當(dāng)中，對(duì)任務(wù)調(diào)度的成本約束、時(shí)間約束等進(jìn)行了考慮。經(jīng)過(guò)相應(yīng)的選擇操作，完成任務(wù)成本較低、時(shí)間較短的個(gè)體，都會(huì)包含在種群當(dāng)中。在新個(gè)體的產(chǎn)生過(guò)程當(dāng)中，交叉操作發(fā)揮著重要的作用，其能夠?qū)z傳算法中的全局搜索能力進(jìn)行確定。在變異操作當(dāng)中，對(duì)于遺傳算法的這種局部搜索能力，可以進(jìn)行相應(yīng)的優(yōu)化和完善。通過(guò)這種方式，能夠?qū)ΨN群的多樣性加以保護(hù)，從而避免早熟現(xiàn)象的出現(xiàn)。在考慮時(shí)間-成本約束的遺傳算法當(dāng)中，通過(guò)對(duì)自適應(yīng)遺傳算法的應(yīng)用，優(yōu)化了變異、交叉概率的計(jì)算公式，使其能夠?qū)ψ儺惒僮?、較差操作等概率進(jìn)行自動(dòng)的適應(yīng)和調(diào)整。在結(jié)束遺傳操作的時(shí)候，考慮時(shí)間-成本約束的遺傳算法能夠?qū)Τ跏妓惴ㄇ蟮玫某杀炯s束、時(shí)間約束等，能夠和最優(yōu)子任務(wù)調(diào)度結(jié)果染色體進(jìn)行比較，而如果算法中沒有產(chǎn)生合理的最優(yōu)子任務(wù)調(diào)度結(jié)果，則重新對(duì)算法進(jìn)行運(yùn)行，從而得到最優(yōu)結(jié)果。

4 結(jié)論

在當(dāng)前的社會(huì)中，云計(jì)算是一種十分重要的應(yīng)用形式，在各個(gè)領(lǐng)域中都發(fā)揮出了良好的效果。而在云計(jì)算的執(zhí)行當(dāng)中，需要通過(guò)一定的任務(wù)調(diào)度算法，得出完成任務(wù)的最優(yōu)時(shí)間和成本。基于此，本文對(duì)基于改進(jìn)遺傳算法的云計(jì)算任務(wù)調(diào)度算法進(jìn)行了研究，極大促進(jìn)了云計(jì)算更加高效的應(yīng)用。

參考文獻(xiàn)：

[1]張?zhí)?，于炯，楊興耀，等. 基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2013（19）：68-72.

[2]劉愉，趙志文，李小蘭，等. 云計(jì)算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略[J]. 北京師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（4）：378-384.

[3]劉冬梅. 云計(jì)算環(huán)境下改進(jìn)加權(quán)輪轉(zhuǎn)任務(wù)調(diào)度算法研究[J]. 牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2015（1）：11-12.

[4]孫凌宇，冷明. 基于不同分配策略的云計(jì)算任務(wù)調(diào)度性能比較與分析[J]. 井岡山大學(xué)學(xué)報(bào)：自然科學(xué)版，2016（1）：62-68+74.

[5]袁恩隆，李飛，唐籍濤，等. 改進(jìn)蟻群算法的云存儲(chǔ)任務(wù)調(diào)度算法研究[J]. 四川理工學(xué)院學(xué)報(bào)：自然科學(xué)版，2014（1）：41-44.