粗粒度并行遺傳算法的MapReduce并行化實現(xiàn)

程興國，肖南峰

(華南理工大學(xué)計算機科學(xué)與工程學(xué)院，廣州 510006)

遺傳算法(genetic algorithm，GA)是一類借鑒生物界自然選擇和遺傳機制的啟發(fā)式隨機搜索算法，它是將生物學(xué)中的遺傳進(jìn)化原理和優(yōu)化理論相結(jié)合的產(chǎn)物。遺傳算法的基本思想很簡單，它通過模擬生物界“物競天擇，適者生存，優(yōu)勝劣汰”的策略獲取種群全局最優(yōu)解。

遺傳算法作為一種應(yīng)用廣泛的高效智能搜索算法，己經(jīng)成功地應(yīng)用于工程設(shè)計、工商管理、科學(xué)實驗等領(lǐng)域中的復(fù)雜優(yōu)化問題的求解。隨著信息技術(shù)的進(jìn)步以及信息化社會的發(fā)展，遺傳算法的種群規(guī)模和迭代代數(shù)顯著增加，導(dǎo)致串行計算方法的時間復(fù)雜度比較高，處理能力存在局限性。傳統(tǒng)高性能計算中的并行編程模型(如PThread、MPI和OpenMP等)抽象度不高，開發(fā)人員需要熟悉底層的配置和并行實現(xiàn)細(xì)節(jié)［1］。MapReduce模型是Google實驗室提出的分布式并行編程模型或框架，它能在普通的PC機上構(gòu)建集群來處理大規(guī)模數(shù)據(jù)集，成為云計算平臺主流的并行數(shù)據(jù)處理模型。Apache開源社區(qū)的Hadoop項目用Java語言實現(xiàn)了該模型，同時Hadoop項目還設(shè)計了開放源代碼的云計算技術(shù)平臺［2］。本文在基于Hadoop技術(shù)的云計算基礎(chǔ)平臺上研究了粗粒度并行遺傳算法的MapReduce并行編程實現(xiàn)方法，并進(jìn)行了相關(guān)實驗。

1 MapReduce編程模型

MapReduce編程模型的基本思路是將大數(shù)據(jù)集分解為成百上千的小數(shù)據(jù)集splits，每個(或若干個)數(shù)據(jù)集分別由集群中的1個節(jié)點(一般是1臺普通計算機)并行執(zhí)行Map計算任務(wù)(指定了映射規(guī)則)，并生成中間結(jié)果，然后這些中間結(jié)果又由大量的節(jié)點并行執(zhí)行Reduce計算任務(wù)(指定了歸約規(guī)則)，形成最終結(jié)果。圖1描述了MapReduce的運行機制:在數(shù)據(jù)輸入階段，JobTracker獲得待計算數(shù)據(jù)片在NameNode上的存儲元信息;在Map階段，JobTracker指派多個TaskTracker完成Map運算任務(wù)并生成中間結(jié)果;在Partition階段完成中間結(jié)果對Reducer的分派;在Shuffle階段完成中間計算結(jié)果的混排交換;JobTracker指派TaskTracker完成Reduce任務(wù);Reduce任務(wù)完成后通知JobTracker與NameNode以產(chǎn)生最后的輸出結(jié)果。MapReduce詳細(xì)執(zhí)行過程如圖1所示［3］。

圖1 MapReduce詳細(xì)執(zhí)行過程

2 粗粒度并行遺傳算法

遺傳算法(GA)是自然遺傳學(xué)和計算機科學(xué)相互結(jié)合滲透而成的算法，是具有“生成+檢測”的迭代過程的搜索算法，即產(chǎn)生、選擇優(yōu)良個體、基因組合(變異)、再產(chǎn)生、再選擇、再組合…［4］，其基本流程如圖2所示。

圖2 遺傳算法流程

傳統(tǒng)的遺傳算法有兩個嚴(yán)重的不足:①容易過早收斂;②在進(jìn)化后期搜索效率較低，使得最終搜索得到的結(jié)果往往不是全局最優(yōu)解而是局部最優(yōu)解，并且該算法不能有效克服過早收斂現(xiàn)象［5］。因此，現(xiàn)有的大量研究集中于如何改進(jìn)傳統(tǒng)的遺傳進(jìn)化思想。目前各種改進(jìn)思想層出不窮，粗粒度模型就是其中的一種。

粗粒度模型又稱分布式模型(distributed style)或孤島模型(island-based model)，是適應(yīng)性最強和應(yīng)用最廣的遺傳算法并行化模型［6］。它將隨機生成的初始種群依處理器個數(shù)分割成若干個較大的子種群，各個子種群在不同的處理器上相互獨立地并發(fā)執(zhí)行遺傳操作，每經(jīng)過一定的進(jìn)化代數(shù)，各子種群間再相互交換若干數(shù)量的個體，以實現(xiàn)各個子種群的共同進(jìn)化。

對經(jīng)典遺傳算法進(jìn)行粗粒度并行改進(jìn)的主要目的是:在不增加適應(yīng)度計算量的基礎(chǔ)上，通過提高種群多樣性來提高計算結(jié)果。

粗粒度并行遺傳算法(CPGA)可以形式化地定義為一個三元組:

式中:T是進(jìn)行遷移操作的時間間隔(頻率);G是遷移操作所交換的個體和信息;SGA是經(jīng)典遺傳算法(單一種群)，它將根據(jù)子種群的數(shù)量多次重復(fù)地執(zhí)行。

粗粒度并行遺傳算法的子種群間常用的環(huán)行連接結(jié)構(gòu)［7］如圖3所示。

圖3 子種群環(huán)形連接結(jié)構(gòu)

3 粗粒度并行遺傳算法的MapReduce并行化實現(xiàn)

粗粒度并行遺傳算法進(jìn)行MapReduce的基本思路是:把串行遺傳算法的每一次迭代變?yōu)橐淮蜯apReduce操作。其中，在Map中完成計算個體適應(yīng)值、雜交、變異的操作;Reduce則判斷是否滿足收斂條件，若為“是”則輸出結(jié)果，否則進(jìn)入下一次MapReduce操作。與普通的MapReduce操作不同，在Map階段結(jié)束后，粗粒度并行遺傳算法MapReduce通過Partition實現(xiàn)并行化，在子種群間用環(huán)行算法遷移最優(yōu)個體，而其他大部分個體保持獨立，如圖4所示。

圖4 粗粒度并行遺傳算法MapReduce的并行化實現(xiàn)

為了保證各個子群獨自繁衍，Mapper和Reducer的節(jié)點數(shù)量都為n，同時確保 Mapperi的數(shù)據(jù)在對應(yīng)的Reduceri進(jìn)行處理。待處理的每個個體給予一個子群key，在Map處理過程中，最優(yōu)個體的key=(key+1)mod n，而Partition的操作是key mod n，從而實現(xiàn)最優(yōu)個體的環(huán)形遷移。

3.1 Map函數(shù)的設(shè)計

Map函數(shù)先對子群中的個體進(jìn)行雜交、變異操作，然后遍歷子群，計算其適應(yīng)值，根據(jù)適應(yīng)值找出子群中的最優(yōu)個體和最差個體，最優(yōu)個體用于遷移到下一個子群(key+1)mod n，而淘汰最差個體。當(dāng)然，也可以實現(xiàn)遷移若干最優(yōu)個體，但數(shù)量不宜過大，否則會影響子群的差異性。

Map函數(shù)偽代碼清單

3.2 Partition函數(shù)的設(shè)計

Partitioner的主要任務(wù)是對中間結(jié)果key-value對進(jìn)行劃分，以決定將其分配至哪個 reducer［8］。

Partition函數(shù)的偽代碼清單如下:

3.3 Reduce函數(shù)的設(shè)計

Reduce函數(shù)主要是判斷遺傳算法的終止條件，如果滿足條件則終止，輸出最終結(jié)果，否則進(jìn)入下一輪的MapReduce循環(huán)。

Reduce函數(shù)的偽代碼清單如下:

4 實驗和結(jié)果分析

4.1 環(huán)境搭建

實驗中云計算平臺的結(jié)構(gòu):1臺機器作為NameNode和JobTracker的服務(wù)節(jié)點，其他8臺機器作為DateNode和TaskTracker的服務(wù)節(jié)點。每臺節(jié)點的硬件配置如下:CPU型號為Intel(R)Core(TM)Duo T8300@2.40GHz;內(nèi)存為 2GB;硬盤為2TB;基于 hadoop－0.20.2 版本構(gòu)建集群。

4.2 單機處理比較實驗

本文采用的算例是Shubert函數(shù)。它是一個典型的多峰問題，有760個局部最小，其中18個是全局最小，Shubert函數(shù)的仿真如圖5所示，函數(shù)如下:

圖5 Shubert函數(shù)的仿真

遺傳算法的實驗參數(shù)設(shè)置:

NIND=120;%個體數(shù)(number of individuals)

MAXGEN=50;%最大遺傳代數(shù)(maximum number of generations)

NVAR=2;%變量數(shù)目

PRECI=25;%變量二進(jìn)制位數(shù)(precision of varibles)

GGAP=0.9;%代溝(generation gap)

實驗結(jié)果如表1所示。

表1 Shubert函數(shù)實驗結(jié)果比較

從表1不難得出，當(dāng)隨機個體數(shù)在640以下時，單機的性能比集群的要好。這是因為集群有節(jié)點間的通信開銷，此時通信時間占主要地位。隨著個體數(shù)的增加，集群的優(yōu)勢逐漸表現(xiàn)出來，尤其是海量數(shù)據(jù)的處理，其優(yōu)勢更加明顯。

圖6 Shubert函數(shù)實驗結(jié)果對比

4.3 集群加速比實驗

加速比是衡量一個系統(tǒng)在擴展性方面優(yōu)劣的主要指標(biāo)，主要考察計算硬件資源增加時，對于相同規(guī)模的作業(yè)，系統(tǒng)的處理能力。

實驗分別選擇1、3、6、8 個 TaskTracker節(jié)點參與隨機個體數(shù)為1 200的計算，考察在逐漸增加節(jié)點的情況下系統(tǒng)完成任務(wù)的時間。實驗結(jié)果如圖7所示。從圖7可以看出:每個作業(yè)運行的時間都隨著節(jié)點的增加而降低，增加節(jié)點可以顯著地提高系統(tǒng)對同規(guī)模數(shù)據(jù)的處理能力，這說明MapReduce在處理遺傳算法方面具有較好的加速比。

圖7 遺傳算法MapReduce實現(xiàn)方法的加速比實驗結(jié)果

5 結(jié)束語

MapReduce算法模型實現(xiàn)粗粒度并行遺傳算法是通過不同的子種群各自獨立地進(jìn)行，把每次進(jìn)化找到的當(dāng)前最優(yōu)解分配到各個子種群中去，以促進(jìn)其他子種群的進(jìn)化。采用該方法可以選取和保留每個子群的優(yōu)秀個體，在保持優(yōu)秀個體進(jìn)化穩(wěn)定性的同時，加快進(jìn)化速度，避免單種群進(jìn)化過程中出現(xiàn)的過早收斂現(xiàn)象。

［1］胡晨駿，王曉蔚.基于多核集群系統(tǒng)的并行編程模型的研究［J］.計算機技術(shù)與發(fā)展，2008，18(4):70－74.

［2］Apache Hadoop.Hadoop［EB/OL］.［2011 － 02 － 15］.http://hadoop.apache.org.

［3］Tom White，Hadoop.The.Definitive.Guide，OReilly Yahoo Press，2ndedition，2009:175 －186.

［4］Goldberg D E.Genetic Algorithms in Search，Optimization＆ Machine Learning［J］.Addison Wesley，Reading，1989.

［5］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京:國防工業(yè)出版社，1999:68－112.

［6］Corcoran A L，Wainwright R L.A Parallel Island Model Genetic Algorithm for the Multiprocessor Scheduling Problem［C］//Proceedings of the 1994 ACM/SIGAPP Symposium on Applied Computing.USA:ACM Press，1994:483－487.

［7］Erick Cantú-Paz.A Survey of Parallel Genetic Algorithms［J］.Calculateurs paralleles，reseaux et systems repartis，1998.

［8］Jimmy Lin，ChrisDyer.Data-Intensive Text Processing with MapReduce［J］.Morgan ＆ Claypool Publishers，2010:26－28.