粗粒度并行遺傳算法的MapReduce并行化實現

程興國，肖南峰

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

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

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

1 MapReduce編程模型

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

圖1 MapReduce詳細執行過程

2 粗粒度并行遺傳算法

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

圖2 遺傳算法流程

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

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

對經典遺傳算法進行粗粒度并行改進的主要目的是:在不增加適應度計算量的基礎上，通過提高種群多樣性來提高計算結果。

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

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

粗粒度并行遺傳算法的子種群間常用的環行連接結構［7］如圖3所示。

圖3 子種群環形連接結構

3 粗粒度并行遺傳算法的MapReduce并行化實現

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

圖4 粗粒度并行遺傳算法MapReduce的并行化實現

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

3.1 Map函數的設計

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

Map函數偽代碼清單

3.2 Partition函數的設計

Partitioner的主要任務是對中間結果key-value對進行劃分，以決定將其分配至哪個 reducer［8］。

Partition函數的偽代碼清單如下:

3.3 Reduce函數的設計

Reduce函數主要是判斷遺傳算法的終止條件，如果滿足條件則終止，輸出最終結果，否則進入下一輪的MapReduce循環。

Reduce函數的偽代碼清單如下:

4 實驗和結果分析

4.1 環境搭建

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

4.2 單機處理比較實驗

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

圖5 Shubert函數的仿真

遺傳算法的實驗參數設置:

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

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

NVAR=2;%變量數目

PRECI=25;%變量二進制位數(precision of varibles)

GGAP=0.9;%代溝(generation gap)

實驗結果如表1所示。

表1 Shubert函數實驗結果比較

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

圖6 Shubert函數實驗結果對比

4.3 集群加速比實驗

加速比是衡量一個系統在擴展性方面優劣的主要指標，主要考察計算硬件資源增加時，對于相同規模的作業，系統的處理能力。

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

圖7 遺傳算法MapReduce實現方法的加速比實驗結果

5 結束語

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

［1］胡晨駿，王曉蔚.基于多核集群系統的并行編程模型的研究［J］.計算機技術與發展，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］周明，孫樹棟.遺傳算法原理及應用［M］.北京:國防工業出版社，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.