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

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

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

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

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

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