基于競爭遺傳算法的海洋云平臺資源調度模型研究

王燁嘉,王蕾,陳竹,周海英

(1.廣東省海洋發展規劃研究中心 廣州 510220;2.國家海洋局南海信息中心 廣州 510300;3.海南南沙珊瑚礁生態系統國家野外科學觀測研究站 廣州 510300;4.自然資源部海洋環境探測技術與應用重點實驗室 廣州 510310;5.廣東海洋協會 廣州 510220)

0 引言

海洋是一個動態的、連續的、邊界模糊的時空信息載體。隨著探測設備和信息技術的不斷發展,海洋數據獲取手段日益增多,海洋信息獲取的速度和精度也在不斷提高,獲取的海洋數據量越來越大,海洋數據呈現多源異構和海量的特征。海洋數據類型主要包括海洋水文、海洋氣象、海洋生物、海洋底質、海洋化學、地質地貌等多個領域,數據主要來源有海洋站觀測、標準斷面調查、浮標觀測、志愿船以及各類環境監測、歷史調查專項等多類數據。海洋數據獲取手段的多樣化以及海洋觀測要素的多元化,使得海洋數據類型呈現多類性特征。隨著海洋事業的快速發展和國家對海洋工作要求的不斷提高,在海洋數據管理、展示及信息化方面也提出了更高的要求,高效、快速的數據處理能力,對提升數據應用價值,助力海洋自然資源管理工作的發展具有重要意義。為解決實際工作中,存在的海洋數據處理效率低下的問題,本文針對海洋數據的特點,提出了基于競爭遺傳算法的海洋云平臺資源調度模型,解決了傳統云平臺在處理密集型計算海洋環境數據的“瓶頸”問題。本研究重點包括以下幾個方面:首先,對Hadoop平臺的原生資源調度算法開展研究工作,結合海洋環境數據處理密集型計算的特點,提出基于競爭模型的遺傳算法任務調度策略,并利用CloudSim 仿真軟件搭建基于競爭遺傳算法的海洋云平臺資源調度模型,通過模型實際驗證和比對,證明改進后的算法在改進云平臺資源調度的能力和效率上有較大提升。

1 云計算在海洋數據處理方面的優勢

云計算是并行計算、分布式計算和網格計算的發展,其基本概念是將通過網絡連接起來的海量信息資源進行統一管理和調配,形成為用戶提供按需服務的計算資源池[1],具有通用性、高可擴展性和高可用性。

云計算具有分布式存儲海量數據和進行大規模并行計算的能力,基于云計算平臺進行海洋信息資源的管理和處理,具有可顯著提升執行效率和性能方面的優勢,已解決面向大規模海洋環境數據串行處理時遇到的性能“瓶頸”。云計算具有分布式存儲海量數據和進行大規模計算的能力,基于云計算平臺進行海洋數據處理具有不可替代的優勢。一是可進一步提升海洋信息資源的可用性。二是可有效解決目前存在的系統資源利用率低、運行成本高的問題。三是云計算平臺具有分布式存儲海量數據和進行大規模并行計算的能力,可顯著提升執行效率和性能方面的優勢。

常規性海洋數據處理任務包含海洋環境數據質控、海洋環境數據特征值計算、數據分析等,這些任務涉及長時間序列或大范圍的海洋數據,特點為數據量大,且以密集型計算為主,計算和存儲的代價會隨著數據規模、精度的增長成平方級增長。因此,為了提升數據處理的速度,在實際應用中,一般采用算法并行、處理結果整合等技術實現這種海量數據在云平臺上的處理。然而,傳統的單機作業及通用型云平臺存在效率不高的突出問題,在實際的應用中存在“瓶頸”和制約。當前,云計算技術的實現方法有很多,在各個行業內得到了有效的應用,但是,鑒于海洋環境數據獨有的特點,包括海量性、模糊性、動態性、多源異構性、時空過程性、多學科關聯性等,現有的云計算平臺無法滿足其處理需求,需結合海洋環境數據的特點,在關鍵任務調度和并行計算等方面開展研究工作。在基于云環境的系統中,合理地分配資源池中的資源,提高利用率是任務調度主要功能,是系統設計中的重要組成部分,需要根據用戶提交的任務信息采用適當的策略將不同的任務分配到相應的資源節點上去運行。在云平臺中面對的用戶群是龐大的,要處理的任務量與數據量也是十分巨大的。因此如何對任務進行高效的調度成為云平臺中所要解決的重要問題。

2 任務調度算法

任務調度指的是根據一定的約束規則,將物理設備分配給符合條件的處理任務的過程,任務調度的約束規則稱為調度算法,即根據一定的分配策略,針對不同的目標,采用不同的調度算法。任務調度算法的主要任務是根據一定的設計規則,合理地分配資源池中的資源,以此提高任務處理的效率,通常任務調度算法會遵循幾個原則:一是要保障用戶提交的任務得到資源最優的調度;二是最大限度地保障系統的吞吐量;三是保障負載均衡和服務的質量[2]。總體來說,作業調度的目的是使用戶提交的任務實現最優化的調度,包括實現最優的時間跨度、負載均衡、服務質量和經濟的原則[3]。

當前最流行的分布式框架平臺為Hadoop[4],其優點包括:可自主開發分布式程序;可通過并行提升處理速度;具有處理大數量數據的能力,且可靠性較高。其內核技術主要包括HDFS 分布式文件系統、HBase分布式數據庫以及Map Reduce計算模型三大項,可進行集群存儲資源、網絡資源、計算資源,實現海量數據和高速運算和存儲[5]。Hadoop的框架最核心的設計就是:HDFS 和Map Reduce。HDFS為海量的數據提供了存儲,是可以運行在通用硬件上的分布式文件系統,具有較強的容錯能力,而Map Reduce則為海量的數據提供了計算,可以處理大規模數據集,整個的數據處理過程分為了Map和Reduce兩個階段[6-7]。

Hadoop存在多個完善的任務調度機制,可實現集群作業過程中的任務調度,任務調度算法主要包括先來先服務調度算法(FIFO)、公平調度策略、容量調度算法[8]。FIFO 是Hadoop中默認的調度算法,主要是按照任務的優先級開展,只有一個任務隊列,被提交的任務按照先后順序在任務隊列中進行排序[9-10]。這種調度策略的優點是簡單直接易于實現,缺點是沒有考慮任務的緊迫程度[11];公平調度算法相當于多道批處理系統,這種策略在系統中配置了任務池,一個任務池可以運行一個任務,實現了同一時刻多任務同時進行,該算法可以保障每個作業平均的共享可用資源,但單個任務的執行效率較低。容量調度算法基本原理與公平調度算法類似,主要區別在于后者可以調整作業的優先級,因此比較適用于大型集群[12-14]。

3 云計算任務調度模型構建

構建云計算任務調度模型為:在云計算中,可使用的資源節點為v={v1,v2,v3,...,v i},v i表示第i個虛擬機基本參數,如CPU 處理能力、帶寬、數據存儲大小等,待執行的任務可表示為T={t1,t2,t3,...,t n},任務分配矩陣P可表示為:

式中:p ni為第n個任務是否選擇第i個虛擬機,故p ni∈{0,1}。

本研究主要針對海洋環境數據處理,主要包含海洋環境數據質控、海洋環境數據特征值計算、數據分析等任務,這類任務主要以密集型計算為主,因此,在搭建評價模型時,選取任務的處理效率為優化指標進行模型構建。任務的處理效率以完成任務的耗時進行評價,單個任務的耗時可表示為:

式中:MI為任務需要執行的指令數;MIPPS為虛擬機的執行能力;time為任務執行所需時間。每個虛擬機執行任務所耗費的總時間可表示為:

式中:timeitotal為第i個虛擬機所耗費的總時間;timein為第i個虛擬機執行第n個任務所用時間。

任務完成以最后一個任務結束為標志,基于以上描述,任務分配結果的評價指標可表示為:

4 任務調度算法優化改進

遺傳算法(GA)最早由美國的John holland于20世紀70年代提出,該算法是根據大自然中生物體進化規律而設計提出的,是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型,是一種通過模擬自然進化過程搜索最優解的方法。該算法通過數學的方式,利用計算機仿真運算,將問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為復雜的組合優化問題時,比常規的優化算法能夠較快地獲得較好的優化結果。遺傳算法已被人們廣泛地應用于組合優化、機器學習、信號處理和自適應控制等領域[3]。遺傳算法主要有以下幾個特點:一是適合大規模并行運行計算;二是可以同時處理群體中的多個個體;三是僅用適應度函數值來評估個體,在此基礎上進行遺傳操作;四是不采用確定性規則,采用概率的變遷規則來指導搜索方向;五是具有自組織、自適應和自學習性。

遺傳算法求解速度受初始化種群與種群進化測量的影響較大,本文提出了改進遺傳算法(CGA),主要改進方法為:為解決初始種群問題,采用混沌算法機制作為種群初始化依據,保障在每次初始化時,得到的解空間能均勻分布;此外,為加快收斂,引入競爭機制,提出基于種群競爭的自適應進化模型,以提升算法的收斂速度。

4.1 基于Logistic映射的種群初始化

遺傳算法作為啟發式搜索算法,受初始化的影響較大,本文通過構建邏輯映射模型,使得初始化種群處于混沌狀態,保障了種群的多樣性,使得優化結果更加趨于穩定。具體步驟如下。

(1)首先生成一個n維的混沌向量,公式如下。

式中:r為一個n×1的隨機數組,表示初始混沌值。

(2)基于混沌向量,計算每一維的混沌值,計算方式如下:

式中:μ為控制參數,用于控制生成的混沌值,x n為當前維度的第n個值。

(3)將混沌值映射到解搜索空間,公式如下。

式中:ymax和ymin為解空間的最大值和最小值;ceil為向上取整。

4.2 自適應高斯變異模型

隨著迭代的進行,解空間將趨于穩定,容易陷入局部最優,可通過提高變異概率來打破解空間的穩定性,基于以上思想,構建自適應高斯變異模型進行優化:

式中:pmax和pmin為最大及最小變異概率;k為當前迭代次數;N為總迭代次數。

4.3 基于種群競爭的自學習進化模型

進行種群迭代時,將種群分為兩種,進行組間對抗,勝者保留,敗者基于勝者標準進行自學習進化,敗者進化完成后,對敗者進行種群選擇,與勝者共同形成新的種群。具體流程如下。

(1)將種群分為pop1和pop2,如果種群數為奇數,則選取當前種群中最優解自動進入勝者組。

(2)對比選取個體的適應值,勝者進入勝者組,敗者進入敗者組。

(3)敗者與勝者對比各個虛擬機節點所耗時間,選取所耗時間差別最大的節點進行進化,進化方式如下。

式中:val ni表示第i個勝者組第n個節點所耗值,n為第i個勝者組的節點總數。該公式表示進入勝者組各任務所選節點號的均值。

式中:val i為當前組第i個節點,va為標準差。該公式表示勝者組各任務節點所選節點號的標準差。式中:new Val為基于Guass函數的變異新值。

(4)對變異值進行判斷,如果變異值超出虛擬機資源總數,則該個體死亡,否則進入進化組。

(5)兩組種群競爭完成后,對進化組進行選擇,淘汰不符合條件的個體。

5 基于改進算法的資源調度模型構建及結果比對

本文基于開源的云計算仿真平臺CloudSim 實現了基于競爭遺傳算法的資源調度模型實現。本實驗測試虛擬機總數小于10,因此,本文選取整數編碼,種群中個體由每個任務對應的虛擬機編號組成的編碼表示。選取兩個個體作為父節點進行交叉,隨機選取節點分割位置進行染色體重組,形成新的個體,對新的個體進行變異判斷,從而得到最終的個體。基于輪盤賭機制進行個體選取,選取模型如下。

式中:p為選取概率;loadmin為當前種群最優解;fit Val為當前個體的適應值,通過產生一個隨機數,當隨機數小于等于p時,該個體被選擇,否則被淘汰。

本文設定10個計算任務、5個虛擬機資源節點進行實驗,算法參數設置如表1所示。

表1 算法參數Table 1 Algorithm parameter table

基于CGA 與先進先出、貪心算法進行對比,對比結果如表2所示。

表2 CGA與先進先出和貪心算法的對比結果Table 2 Comparison results of CGA,FIFO and Greedy algorithm

為驗證算法的穩定性,對比GA 與CGA 的性能,對比結果如圖1所示。

GA 的性能主要從收斂速度及收斂結果的穩定性進行判斷,通過對比GA 和本文提出的CGA,論證本文算法的有效性。從圖1中可以看出,當基于隨機生成種群時,CGA 在收斂速度和50次收斂結果上都優于傳統GA。在實際中,可能存在初始化種群不太理想的情況,因此,本文基于邏輯映射的混沌算法進行初始化,從圖中可以看出,CGA 在收斂速度及收斂結果的穩定性上都優于傳統GA。

6 結語

海洋自然資源管理對于信息和數據支撐的實際需求中,常涉及長時間序列或大范圍的海洋數據處理工作,對于此類密集型計算為主的數據處理,通用型云平臺存在效率不高的突出問題,本文在全面分析Hadoop平臺原生資源調度算法的基礎上,結合海洋數據處理密集型計算的特點,創新性地提出了基于競爭模型的遺傳算法任務調度策略,通過搭建的模型實際驗證和比對,證明改進后的算法在收斂速度及收斂結果的穩定性上都優于傳統GA,在改進云平臺資源調度的能力和效率上有較大提升。

由于本文所搭建分布式環境節點較少,當節點過多時,以整數方式對種群進行編碼的方式將不能滿足需求,后續的研究可考慮引入二進制編碼,然而,二進制編碼空間通常會大于整個種群空間,此時,在進行進化和變異過程中,需考慮新個體是否能存活的問題,下一步將考慮從二進制編碼出發,優化進化及變異算法,提升求解能力的同時,確保收斂的穩定性,并將其應用到海洋數據的處理中,以信息和數據的力量,助力各項海洋資源管理的高質量發展。