云計算環境中優化遺傳算法的資源調度策略

【摘要】 資源調度是云計算的核心問題，傳統的遺傳算法雖然可以用于云計算環境中的資源調度，但是由于傳統遺傳算法存在收斂慢、易早熟等特點，所以這種算法并不適應于多聚類環境下的密集型任務調度。基于此，我們提出了云計算環境中優化遺傳算法的資源調度策略以彌補傳統遺傳算法的不足。本文主要通過對云計算概念的介紹以及如何優化遺傳算法的資源調度策略來展開討論。

【關鍵詞】 云計算環境概念 優化遺傳算法 資源調度策略

近些年來，隨著計算機技術的飛速發展，云計算計算模式應運而生。Web2.0技術以及系統虛擬化等技術的發展促進了云計算的不斷完善。目前，云計算被廣泛地應用于商業計算。它作為下一代并行與分布式計算，具有超大規模、抽象化、高可靠性、通用性等特點，受到國內各領域的廣泛關注。接下來，我們就具體的介紹云計算環境中如何通過資源調度策略進行優化遺傳算法。

一、云計算技術概述

隨著計算機技術的發展以及計算模式的創新，云計算成為一種新的計算模式。云計算是一種將分布式計算、并行計算、網格計算、虛擬化計算以及Web服務等技術進行融合和結合新的計算機技術而形成的新的計算方式。它的優點更加突出，計算方式更加便捷，計算結果更加權威。隨著現代技術的不斷發展，云計算也逐漸應用到各個領域之中。

通過對云計算的整體評估和了解，我們將云計算分為兩個方面。一方面是能夠提供用來構造應用程序的基礎設施，包括計算機方面的硬件設施和軟件設施。這一方面使得云計算能夠涵蓋一般計算方式的特點，并突破了傳統計算方式的束縛。另一方面是提供建立在基礎設施上的云應用。通過建立在基礎設施上的云應用，不僅可以增加基礎設施本身的應用范圍，而且能夠擴大云應用的適用范圍，將云應用應用到更多的領域之中。

我們除了根據云應用的功能將其非為兩個方面之外，還根據它的使用者將其分為私有云和公共云。顧名思義，私有云是私人專有的云，需要用戶自行購買硬件設備，然后自己通過所購買的設備進行維護整個系統，系統中的所有數據均是用戶自己進行管理的，信息內容也是和用戶密切相關的，用戶對于系統的管理具有自主性。私有云的規模相對有限，在使用的過程中，由于只有簡單的硬件基礎設備，所以云計算的高性能性和高性價比的優勢不能夠充分的顯示出來。而對于公共云來說，這些方面就是有云服務提供商所提供的，并不需要用戶進行投資。公共云的使用中，用戶不需要自行購買設備，也不需要自己進行系統的維護。他們只需要向云服務提供商支付一定的費用，就可以免費的使用云計算。整個公共云系統的設備維護和管理以及系統的升級的工作都是由云服務提供商負責，不需要用戶進行管理。這就使得公共云在使用和維護中具有具有更大的靈活性和成本優勢。

二、優化遺傳算法的資源調度策略

接下來，我們根據Baidu的MaP/Reduce模型，對云計算環境下優化遺傳算法的資源調度策略進行具體的介紹。首先，在傳統的遺傳算法中，我們所采用的是一種基于染色體編碼方式和適應度函數改進的遺傳算法去實現分布式大規模任務的資源調度。在這個過程中，我們通常是將任務總數作為染色體基因串的長度，而具體到每一個任務時，我們會將每一個任務所映射的資源ID作為染色體的基因值。但是這種做法會造成系統的超載，編碼的基因串的長度遠遠地超過了基因池內的資源總數，所以在具體的計算時會造成算法進化速度慢，并且容易出現錯誤的情況，由于在基因池內無法找到相應的資源，所以有些基因串在具體的計算中可能會出現亂碼和無法計算的情況，最終導致收斂到最優解的時間過長。

云計算模式的出現很好的解決了這一技術難題，它彌補了傳統的遺傳計算方式的缺陷，在技術上完善了傳統遺傳計算方式。在云計算環境中，我們改進了染色體的編碼方式，通過將資源總數作為染色體的基因串長度、每個資源所映射的任務總數以及任務ID作為染色體的基因值來加快算法的收斂速度。這種編碼方式所形成的基因串的總數小于系統資源池內的總數，所以在計算過程中可以達到最優的資源調度，從而達到提高計算速度和計算準確度的目的。這也是云計算環境中優化遺傳算法的資源調度策略的方式之一，同時也是被各個領域所接受并廣泛應用的原因之一。這種改進染色體編碼的形式，很好的彌補了傳統遺傳計算的缺陷，不僅能夠全面的提高收斂速度，而且還能夠提高正確率以增加通過遺傳計算來正確預測種群進化方向的目標。另外，由于云計算環境的動態異構的特性，所以我們在對適應度函數進行設計的時候，不僅要充分的考慮到資源節點動態的任務處理能力，還要充分的考慮到異構環境下任務的映射時間和結果的匯聚時間問題。只有充分的考慮到這兩個方面，我們才能夠在云計算環境中對遺傳計算實現最有計算。與此同時，在算法的初始階段和接近收斂的階段，還要對適應度函數作出調整，確保通過最優的遺傳計算來預測種群的正確進化方向以及尋求更廣闊的尋優空間。

1、染色體的編碼和種群的初始化。染色體本身的編碼方式有很多，這里我們采用資源-任務的間接實數編碼方式來進行介紹。這種編碼方式的的主要步驟是：首先對染色體進行預編碼，設有m個任務，設定任務的ID={1；2；3；4，…，m}，n個資源節點，設定資源的ID={1，2，3，…，n}，那么我們就可以得到染色體的基因串長度為任務總數m，染色體基因值為資源ID。假設某一參數的取值范圍是[umin，umax]，我們用長度為l的二進制編碼符號串來表示該參數，則它總共能夠產生 2l種不同的編碼，參數編碼時的對應關系如下：

00000000…00000000=0 umin

00000000…00000001=1 umin+δ

……

11111111…11111111=2l–1 umax

其中，δ為二進制編碼的編碼精度。

當我們確定了染色體的編碼方式之后，還需要進行種群的初始化，由于初始的種群具有多樣性和不確定性，所以在這里我們采用隨機的方式來產生初始種群，種群的大小我們設定為Scale。下面是由初始化種群形成適應度值最優的染色體的圖解。

2、基于最優跨度和負載均衡的雙適應度函數。適應度函數是通過最有跨度和負載均衡來衡量的。對于任何一種染色體來說，它的任務資源分配方案的最優跨度應該是該分配方案下最晚完成任務的資源節點所用的總任務的執行時間。

3、選擇復制。遺傳算法對個體適應性的評價方式是選擇操作。選擇操作也是實現群體優良基因傳播的基本方式。在科研角度上通過選擇復制可以將種群內的基因進行自由的組合，從而組合出最優的基因組和。

4、交叉。產生新個體的主要方法是交叉算子。交叉算子能夠決定遺傳算法的全局搜索能力。在具體的操作中，我們從全局的角度出發去尋找交叉對。即基因重組。交叉對是按照較大的概率從群體中選擇2個個體進行交換2個個體某位或某些位基因。通過對交叉對的研究，我們能夠將種群內的基因進行簡單的組合，從而發現最優基因以及簡單的對種群的進化方向進行預測等。

5、變異。產生新個體的輔助方法則是變異算子。交叉算子雖然能夠實現全局搜索，但是它卻做不到對搜索空間的細節進行局部的搜索。在這個時候，如果我們采用變異算子來調整個體編碼串中的部分基因值，就可以從局部角度出發式個體更加逼近最優解。交叉算子和變異算子的完美結合有利于我們在遺傳算法中進行全面的搜索能力的提高。

三、算法性能的正確評估

上面我們采用的Baidu中的MaP/Reduce模型進行介紹，接下來我們通過對云仿真器上的CloudSim進行仿真計算的介紹。CloudSim是在離散時間模擬包SimJava上開發的一種函數庫，CloudSim繼承了GridSim的編程模型，不僅突破了原有模型的局限性而且形成了屬于自己的一套新型計算模式。CloudSim具有以下幾個特點：首先，CloudSim能夠做到支持大型云計算的基礎設施的建模和仿真，這對于傳統的仿真計算模式來說是不可能實現的。其次CloudSim是一個自足的支持數據中心、服務代理人、調度和分配策略的平臺。該平臺包含了各種軟件結構框架和體系結構組件，從而擴大了資源池的資源總數，并且所包含的大量軟件對提高收斂速度也有很大的幫助，對提高遺傳計算的正確率也就不言而喻了。CloudSim所包含的軟件結構框架和體系結構組件包括SimJava、GridSim、CloudSim、UserCode4各層次。其中的CIS和DataCenterBroker能夠很好的實現資源發現和信息交互，這是整個CloudSim模擬調度的核心，這種算法主要是在DataCenterBroker中實現的。這兩個特點很好的體現了改進后的遺傳算法的優點，使得改進后的遺傳算法比傳統的遺傳算法的收斂速度更快，性能更優秀。這兩點不僅僅表現在任務執行時間最短上面，同時也表現在能夠滿足資源負載均衡上面。它可以很好的用于大梁任務的資源調度上。而進行大量的資源調度正是云計算環境的特性以及它被廣泛應用在各個領域的主要原因。所以，本位所提出來的遺傳算法能夠很好的使用在云計算環境中的資源調度上面。

四、總結

本文提出了一種改進遺傳算法的資源調度算法，該方法是參考云計算的Map/Reduce模型，在染色體編碼上結合云計算環境中海量數據處理和大規模任務執行的特性，設計合理的染色體編碼方案，通過對目標函數的設定，設計出一種基于最有跨度和負載均衡的雙適應度函數，然后再結合云計算環境中的其他系統的配合，通過資源調度策略達到遺傳算法的最優。

參 考 文 獻

[1] 英海燕，王友波. 基于自適應遺傳算法的模板匹配研究[J]. 微電子學與計算機. 2008（01）

[2] 李冰. 云計算環境下動態資源管理關鍵技術研究[D]. 北京郵電大學. 2012

[3] 葛新. 基于云計算集群擴展中的調度問題研究[D]. 中國科學技術大學. 2011

[4] 李棟. 基于經濟原則的網格調度系統研究[D]. 北京化工大學，2012年