面向并行遺傳算法的云計算關(guān)鍵技術(shù)研究.pdf

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

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

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

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

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