改進遺傳算法的MapReduce并行化研究

董義明 王鵬達 李鵬 仝茵

摘要：針對遺傳算法在進行海量數據搜索時，算法的收斂速度會隨著數據復雜度升高和數據量的增多而變慢的問題。該文將遺傳算法進行了合并優化，將合并后的算法在MapReduce架構上并行化實現。實驗結果表明，改進后的遺傳算法當運行在MapReduce架構上時，不僅加快了收斂速度，而且提高了加速比。

關鍵詞：遺傳算法；MapReduce；收斂速度；加速比

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2019）10-0151-02

開放科學（資源服務）標識碼（OSID）：

1 引言

當今社會隨著互聯網技術的快速發展，數據量已經呈現出爆炸增長的趨勢，數據的形式更是呈現出多樣性[1]。分布式計算模型的提出為解決大數據的數據挖掘問題提供了一個新的思路，這幾年以來分布式計算已經成為國內外許多專家研究的熱點。程興國，肖南峰針對粗粒度并行遺傳算法的特點，給出了MapReduce編程模型實現遺傳算法的方法[2]；包達爾罕在研究完Hadoop并行處理技術之后，將遺傳算法實現了并行化[3]；胡濤提出基于最優個體保留策略的遺傳算法并在Hadoop集群上進行了實現，進一步提高了算法的收斂速度[4]；嘉瑞玉、管玉龍等人利用遺傳算法的并行化設計思想，在Hadoop平臺下遺傳k-means算法進行了并行化設計[5]；徐肖、胡吉明提出在編碼的時候將計算資源作為操作的基本單元，由此提出了新的區域雜交法子和變異算子[6]。

但是將遺傳算法在移植到并行計算模型上運行時[7]，由于算法需要對數據進行全局搜索，算法的收斂速度會隨著數據復雜度升高和數據量的增多而變慢。為了提高算法的收斂速度和加速比，在總結前人工作的基礎上，本文將對遺傳算法進行了并行化的實現，將實現后的算法在MapReduce模型上進行類的實現。

2 MapReduce編程模型

MapReduce并行處理模型最早是由Google提出的一種分布式計算模型，該模型主要有Map和Reduce兩個階段組成，現在由Apache提供的開源框架Hadoop[8]也是在MapReduce基礎上發展而來的，本實驗中也采用開源架構Hadoop作為實驗集群的架構。MapReduce[9]采用“拆分處理再合并”的設計思想，首先將要處理的數據集進行大量地拆分，經過拆分之后形成多個小的數據塊 ，然后主節點將這些拆分后的小數據塊交給各個從節點處理，各個從節點可以獨立完成自己的計算任務，這樣就可以將一個較大的任務拆分為多個較小的任務并行執行，從而提高了任務執行的速度。Map和Reduce的過程可以簡單的描述的如式1的形式：

[map（k1，v1）→list（k2，v2）reduce（k2，list（v2））→list（v3）] （1）

在程序開始的時候， MapReduce會調用庫函數UserProgram[10]，庫函數能夠將輸入文件split為若干份小份，通常每一份大小為64M，作為Map函數的輸入數據，然后由fork函數將這些拆分的split文件由主節點分配到各個從節點上。從節點上的Map函數首先對文件以（key，value）的形式讀取，然后對其進行處理計算產生一個中間鍵值對，也就是上述的list（k2，v2）。Reduce函數會將Map函數輸出的作為輸入，中間還需要對其進行匯總計算，形成最后的輸出結果 OutputFile。MapReduce的模型如圖1所示：

3 改進遺傳算法

遺傳算法是現代計算機科學與傳統的自然遺傳學的產物，它是通過迭代過程不斷搜索目標。遺傳算法的迭代過程可以概括為：產生、選擇優良個體、基因組合（變異）、再生、再組合。遺傳算法將復雜的現象用繁殖機制結合簡單的編程技術來表現，進一步得出了相對復雜問題的較好的解。遺傳算法的基本執行流程如下圖2所示：

4 基于MapReduce的算法實現

由MapReduce運行的形可知，Map階段和Reduce階段的計算可以獨立進行，在算法的運行過程中相互之間沒有關聯，故在實現基于MapReduce的改進遺傳算法時，需要每個從節點的計算都能單獨運行。

4.1 Map函數的設計

Map函數主要完成，從HDFS的文件中讀取數據，對種群進行初始化，更新粒子群的速度與方向，對種群中的個體進行雜交、變異、計算其適應度，生成新一代種群，并輸出給Reduce函數。Map函數的偽代碼描述如下：

5 實驗和結果分析

5.1 實驗環境

實驗運行在由7臺計算機運行的集群上，集群框架采用Apache開源框架Hadoop。在這7臺機器中，將其中1臺機器作為NameNode，其余6臺機器作為DataNode。每臺機器的硬件配置如下：CPU型號為AMD Trinity APU A8-5800B、頻率為3.2GHz，內存大小為8G，硬盤大小為1T，操作系統為Ubuntu 13.10、JDK 1.7、Hadoop 2.2.0。

5.2 集群性能實驗

實驗分為兩次，在相同的配置集群下，第一次運行未改進的遺傳算法，第二次運行改進后的遺傳算法，設置它們的最大進化次數為100次，交叉概率為0.7，變異概率為0.01，假設算法在10次迭代中所用的時間并沒有改變，則認為該算法趨于收斂，算法結束。實驗比較從數據讀入到完成算法收斂所需要的時間。實驗結果如圖3示：

圖3 性能比較試驗結果

實驗二選取數據量大小分別為512M，1.0G和1.5G的數據集，集群節點數由1個節點逐步增加到6個，比較它們的所用時間的加速比，實驗結果如圖4示。由圖可以看出該集群具有良好的加速比。

6 結束語

當今社會已經加入大數據的時代，在這個時代要善于從數據中尋找機會。如何從海量的數據中挖掘出具有價值的信息，是現在研究的一個熱點，許多學者和大型機構也一直致力于這方面的研究。本文針對傳統的遺傳算法在MapReduce并行化時出現的收斂速度以及加速比慢的問題，對遺傳算法的并行化改進中，改進后的算法進行了并行化的設計，使其在MapReduce并行編程模型上實現。實驗運行結果表明：改進后的遺傳算法，在MapReduce模型上進行運算時，算法的加速比提高，算法的收斂速度加快。

參考文獻：

[1] 陳吉榮，樂嘉錦.基于Hadoop生態系統的大數據解決方案綜述[J.]計算機工程與科學，2013，35（10）：25-35.

[2] 程興國，肖南峰.粗粒度并行遺傳算法的MapReduce并行化實現[J].重慶理工大學學報，2013，10（27）：66-74.

[3] 包達爾罕.基于Hadoop的改進 遺傳算法[J]內蒙古師范大學學報，2015，44（1）：62-65.

[4] 胡濤.基于MapReduce模型遺傳算法的一種改進與實現[J].電子設計工程，2013，5（21）：32-39.

[5] 賈瑞玉，管玉勇，李亞龍.基于MapReduce模型的并行遺傳k-means聚類算法[J].計算機工程與設計，2014，2（35）：657-660.

[6] 徐肖，胡吉明.一種Hadoop中基于改進遺傳算法的作業調度算法[J].計算機技術與發展，2013，3（23）：10-18.

[7] 李建江，崔健.MapReduce并行編程模型研究綜述[J].電子學報，2013，11（11）：2635-2642.

[8] 許丞，劉洪，譚良.Hadoop云平臺的一種新的任務調度和監控機制[J].計算機科學，2013，40（1）：112-117.

[9] Jimmy Lin， ChrisDyer. Data-Intensive Text Progressing with MapReduce[J].Morgan & Claypool Publishers， 2011，22（5）： 26-28.

[10] 武森，馮小東，楊杰，等.基于MapReduce的大規模文本聚類并行化[J].北京科技大學學報，2014，36（10）：1411-1419.

【通聯編輯：代影】