面向并行遺傳算法的云計算關鍵技術研究.pdf

1、云計算(Cloud Computing)是近年來科技界新興的一個名詞,用以指代以服務形式存在的大規(guī)模的虛擬硬件平臺或者軟件。盡管云計算的概念有些泛濫,但是云計算還是帶來了很多不同于以往的新產品、新問題。如:用以支撐大規(guī)模虛擬硬件平臺的虛擬化技術,大規(guī)模分布式文件系統(tǒng),由于數(shù)據(jù)中心的集中所帶來的安全問題等。MapReduce就是隨著云計算出現(xiàn)的一種高效的分布式計算框架。
　　 并行遺傳算法(Parallel Genetic Alg

2、orithms,PGAs)是一類在求解NP完全問題方面較為有效的啟發(fā)式算法,然而相比遺傳算法,其編程實現(xiàn)難度及其運行平臺的管理復雜度大大阻礙了它的廣泛應用。將傳統(tǒng)并行遺傳算法移植到云計算平臺上,借助MapReduce簡化其實現(xiàn)難度及解決由此帶來的效率低下問題是本文的主要研究內容。
　　 圍繞并行遺傳算法在云計算平臺下的實現(xiàn),在綜述當前研究進展的基礎上,本文從以下三個方面進行了研究:
　　 1.提出了基于云計算平臺的并行遺

3、傳算法。針對并行遺傳算法實現(xiàn)難、難以在實踐中應用的問題,在深入研究MapReduce框架和并行遺傳算法架構的基礎上,對應于傳統(tǒng)的并行遺傳算法架構,提出了三種具有典型代表的基于云計算平臺的并行遺傳算法。在開源云軟件Hadoop上的實驗表明,基于MapReduce的并行遺傳算法只需要實現(xiàn)兩個函數(shù)接口即可,其實現(xiàn)簡單,但在本文的測試函數(shù)中,求解時間上最高僅獲得12.36倍的加速比。
　　 2.為改進基于云計算平臺并行遺傳算法的調度效率

4、,提出了面向并行遺傳算法的云計算平臺的動態(tài)任務調度算法。不同于基于slot的調度算法,其基本思想是不固定slot個數(shù),而是依據(jù)當前的設備情況和要調度的任務請求的資源情況,動態(tài)地進行調度。首先對調度問題進行了精確的數(shù)學建模,提出了以“吞吐量”和“短作業(yè)優(yōu)先”為評價指標的目標函數(shù),然后對該模型采用分布估計算法(Estimation of Distribution Algorithm,EDA)來進行求解。在模擬的任務調度試驗中,對比現(xiàn)有的Ha

5、doop的FIFO調度算法,面向并行遺傳算法的云計算平臺的動態(tài)調度算法能獲得較高的函數(shù)適應度。
　　 3.針對基于MapReduce的并行遺傳算法在實踐過程中發(fā)現(xiàn)的非計算開銷大的問題,提出了面向并行遺傳算法的增強的MapReduce框架CMapReduce(Communication MapReduce)。其核心思想是構建一個通訊模塊,允許任務在Map/Reduce任務間進行通訊。對CMapReduce框架進行了詳細的描述,同時