基于改進GA 的云計算任務調度算法研究

姜學文

摘要：在當前的社會當中，隨著計算機技術和網絡技術的發展，云計算逐漸成為一種主要的計算方式。而在云計算當中，任務調度算法發揮著重要的作用。對此，應當對計算資源進行合理的分配，對任務調度算法進行改進，從而進一步提升云計算的效率。基于此，本文對考慮時間-成本約束的遺傳算法的改進GA任務調度算法進行了分析和研究，從而更好發揮出云計算的作用和效果。

關鍵詞：改進GA；云計算；任務調度算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2016）13-0177-02

云計算是當前網絡中一種基于云平臺提供的運算服務，其中包含軟件、平臺、基礎設施等服務，通過互聯網，拆分處理任務，使之形成若干小任務，然后通過多個服務器系統進行計算分析和搜索，并向用戶傳遞結果。在云計算當中，包括網格計算、并行計算、分布式計算等方面的內容。在云計算中，具有龐大的計算任務，因此任務調度十分重要，對于云計算的效率來說，也有著直接的影響。

1 任務調度的基本概述

在當前的云計算領域當中，對Google的Map/Reduce編程模型的應用較為廣泛，能夠并行計算大規模的數據集。通過對大任務的劃分，利用多個計算資源對劃分的小任務進行并行執行，最后對最終的計算結果進行匯總。云計算在提供服務的過程中，應當面向多個用戶，因此對各個用戶的響應時間應加以考慮，并且應當對服務所需成本進行考慮。而在一些傳統的調度算法中，往往難以對所有的因素進行考慮，因而難以同時兼顧到時間和成本[1]。在云計算當中，主要有網絡、存儲器、處理器等資源，在應用過程中，根據用量和需求進行使用和付費。在云計算當中，任務調度算法能夠向各個計算資源中更加合理的分配子任務，從而縮短任務執行時間，降低任務執行成本。

2 幾種任務調度算法的比較

在云計算環境下，基于相同的條件，對考慮成本約束的遺傳算法、考慮時間約束的遺傳算法、考慮時間-成本約束的遺傳算法等進行了比較分析。在實驗研究當中，在初期的遺傳算法進化階段，對于總任務完成時間來說，這三種遺傳算法都能夠得到基本相似的最優子任務調度結果。而在不斷增加進化代數的條件下，對于總任務完成時間來說，考慮成本約束的遺傳算法、考慮時間-成本約束的遺傳算法能夠得到更加良好的結果，而考慮時間約束的遺傳算法則難以取得較為理想的效果[2]。由此可見，在考慮成本約束的遺傳算法中，能夠得到最小總任務完成成本的子任務調度結果，但是難以有效的優化任務完成時間。而考慮時間約束的遺傳算法，能夠得到最短任務完成時間的子任務調度結果，但是難以有效的優化任務執行成本。在考慮時間-成本約束的遺傳算法當中，由于同時對任務的時間和成本進行了考慮，因而在任務調度當中，能夠取得更為理想的子任務調度結果，更好的提升云計算的效率和效益。

3 考慮時間-成本約束的遺傳算法

1） 染色體的編碼解碼

在編碼方式方面，染色體十分豐富，能夠對間接編碼和直接編碼的方式進行應用。子任務的數量，可看作染色體的長度，在染色體當中，根據子任務占用資源的具體編號，對基因取值進行確定。在初始種群的產生過程中，每一個染色體會隨機生成資源編號，在變異、較差算子之后，子任務會對任意的可用資源進行占用，因此，在最優解當中，都會有染色體編碼與之相對應。在染色體生成之后，應當對其進行解碼操作，從而對子任務分布在不同資源中的情況加以了解。根據占用資源的不同，對子任務進行劃分，根據資源編號，得到多組子任務的分類序列，然后對相應的染色體進行解碼[3]。在解碼之后，對于計算資源中分配的子任務，能夠對其序列進行了解。通過對ETC矩陣進行應用，對于計算資源中，子任務序列的完成時間，能夠進行準確的計算。在云計算當中，計算資源當中都有著并發處理的特點，因而在計算中，根據最大的計算結果，確定為子任務完成的具體時間。在考慮時間-成本約束的遺傳算法當中，由于對完成子任務的成本、時間等都要加以考慮，因此可采用貪心算法對子任務完成的最大成本、最大時間等進行計算。

2） 適應度函數

在基于改進遺傳算法的云計算任務調度算法當中，選擇適當的遺傳算法適應度函數，能夠發揮出良好的效果，對于遺傳算法中查找最優解、收斂速度等，都有著直接的影響。如果個體具有較大的適應度，其就有更大的概率向下一代進行遺傳。如果個體的適應度較小，則其就有較小的概率向下一代進行遺傳。在任務調度的過程中，應當對完成所有子任務需要的時間、成本等問題進行考慮。在定義時間的適應度函數當中，涉及平衡任務負載因子這一參數，能夠對不同計算資源的實際利用率進行反映[4]。如果平衡任務負載因子具有較大的數值，則說明計算資源具有較高的利用效率，因而任務完成時間就會相應的較短。在定義成本的適應度函數當中，可根據任務完成時間進行計算。在適應度函數當中，如果只對之間約束進行考慮，在越高的計算資源利用率之下，如果子任務個體需要較短的時間就能夠完成子任務，就有較大的適應度。而如果適應度函數只對成本約束進行考慮，子任務個體需要較低的成本就能夠完成任務，也會具有較大的適應度。所以，在對考慮時間-成本約束的遺傳算法的適應度函數進行定義的過程中，應當對時間、成本等約束進行綜合性的考慮，從而得到更加準確的任務調度結果。

3） 遺傳操作

在遺傳操作當中，主要包括選擇操作、交叉操作、變異操作等。在選擇操作當中，將具有較強適應度的個體在種群中進行選擇，從而對新種群的形成過程進行產生。從優勝劣汰的基本原則中，如果個體具有越高的適應度，就會由更大的概率向下一代進行遺傳，因而在種群當中，能夠連續的優化適應度，從而向最優解進行不斷靠近[5]。在考慮時間-成本約束的遺傳算法當中，選擇操作因子為輪盤賭選擇的方式，根據相應的公式對個體被選擇概率進行計算。在適應度函數當中，對任務調度的成本約束、時間約束等進行了考慮。經過相應的選擇操作，完成任務成本較低、時間較短的個體，都會包含在種群當中。在新個體的產生過程當中，交叉操作發揮著重要的作用，其能夠對遺傳算法中的全局搜索能力進行確定。在變異操作當中，對于遺傳算法的這種局部搜索能力，可以進行相應的優化和完善。通過這種方式，能夠對種群的多樣性加以保護，從而避免早熟現象的出現。在考慮時間-成本約束的遺傳算法當中，通過對自適應遺傳算法的應用，優化了變異、交叉概率的計算公式，使其能夠對變異操作、較差操作等概率進行自動的適應和調整。在結束遺傳操作的時候，考慮時間-成本約束的遺傳算法能夠對初始算法求得的成本約束、時間約束等，能夠和最優子任務調度結果染色體進行比較，而如果算法中沒有產生合理的最優子任務調度結果，則重新對算法進行運行，從而得到最優結果。

4 結論

在當前的社會中，云計算是一種十分重要的應用形式，在各個領域中都發揮出了良好的效果。而在云計算的執行當中，需要通過一定的任務調度算法，得出完成任務的最優時間和成本。基于此，本文對基于改進遺傳算法的云計算任務調度算法進行了研究，極大促進了云計算更加高效的應用。

參考文獻：

[1]張陶，于炯，楊興耀，等. 基于改進粒子群算法的云計算任務調度算法[J]. 計算機工程與應用，2013（19）：68-72.

[2]劉愉，趙志文，李小蘭，等. 云計算環境中優化遺傳算法的資源調度策略[J]. 北京師范大學學報：自然科學版，2012（4）：378-384.

[3]劉冬梅. 云計算環境下改進加權輪轉任務調度算法研究[J]. 牡丹江師范學院學報：自然科學版，2015（1）：11-12.

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

[5]袁恩隆，李飛，唐籍濤，等. 改進蟻群算法的云存儲任務調度算法研究[J]. 四川理工學院學報：自然科學版，2014（1）：41-44.