改進(jìn)遺傳算法的MapReduce并行化研究

董義明 王鵬達(dá) 李鵬 仝茵

摘要：針對遺傳算法在進(jìn)行海量數(shù)據(jù)搜索時(shí)，算法的收斂速度會隨著數(shù)據(jù)復(fù)雜度升高和數(shù)據(jù)量的增多而變慢的問題。該文將遺傳算法進(jìn)行了合并優(yōu)化，將合并后的算法在MapReduce架構(gòu)上并行化實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的遺傳算法當(dāng)運(yùn)行在MapReduce架構(gòu)上時(shí)，不僅加快了收斂速度，而且提高了加速比。

關(guān)鍵詞：遺傳算法；MapReduce；收斂速度；加速比

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

1 引言

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

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

2 MapReduce編程模型

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

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

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

3 改進(jìn)遺傳算法

遺傳算法是現(xiàn)代計(jì)算機(jī)科學(xué)與傳統(tǒng)的自然遺傳學(xué)的產(chǎn)物，它是通過迭代過程不斷搜索目標(biāo)。遺傳算法的迭代過程可以概括為：產(chǎn)生、選擇優(yōu)良個(gè)體、基因組合（變異）、再生、再組合。遺傳算法將復(fù)雜的現(xiàn)象用繁殖機(jī)制結(jié)合簡單的編程技術(shù)來表現(xiàn)，進(jìn)一步得出了相對復(fù)雜問題的較好的解。遺傳算法的基本執(zhí)行流程如下圖2所示：

4 基于MapReduce的算法實(shí)現(xiàn)

由MapReduce運(yùn)行的形可知，Map階段和Reduce階段的計(jì)算可以獨(dú)立進(jìn)行，在算法的運(yùn)行過程中相互之間沒有關(guān)聯(lián)，故在實(shí)現(xiàn)基于MapReduce的改進(jìn)遺傳算法時(shí)，需要每個(gè)從節(jié)點(diǎn)的計(jì)算都能單獨(dú)運(yùn)行。

4.1 Map函數(shù)的設(shè)計(jì)

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

5 實(shí)驗(yàn)和結(jié)果分析

5.1 實(shí)驗(yàn)環(huán)境

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

5.2 集群性能實(shí)驗(yàn)

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

圖3 性能比較試驗(yàn)結(jié)果

實(shí)驗(yàn)二選取數(shù)據(jù)量大小分別為512M，1.0G和1.5G的數(shù)據(jù)集，集群節(jié)點(diǎn)數(shù)由1個(gè)節(jié)點(diǎn)逐步增加到6個(gè)，比較它們的所用時(shí)間的加速比，實(shí)驗(yàn)結(jié)果如圖4示。由圖可以看出該集群具有良好的加速比。

6 結(jié)束語

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

參考文獻(xiàn)：

[1] 陳吉榮，樂嘉錦.基于Hadoop生態(tài)系統(tǒng)的大數(shù)據(jù)解決方案綜述[J.]計(jì)算機(jī)工程與科學(xué)，2013，35（10）：25-35.

[2] 程興國，肖南峰.粗粒度并行遺傳算法的MapReduce并行化實(shí)現(xiàn)[J].重慶理工大學(xué)學(xué)報(bào)，2013，10（27）：66-74.

[3] 包達(dá)爾罕.基于Hadoop的改進(jìn) 遺傳算法[J]內(nèi)蒙古師范大學(xué)學(xué)報(bào)，2015，44（1）：62-65.

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

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

[6] 徐肖，胡吉明.一種Hadoop中基于改進(jìn)遺傳算法的作業(yè)調(diào)度算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，3（23）：10-18.

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

[8] 許丞，劉洪，譚良.Hadoop云平臺的一種新的任務(wù)調(diào)度和監(jiān)控機(jī)制[J].計(jì)算機(jī)科學(xué)，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的大規(guī)模文本聚類并行化[J].北京科技大學(xué)學(xué)報(bào)，2014，36（10）：1411-1419.

【通聯(lián)編輯：代影】