程興國(guó)，肖南峰

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

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

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

1 MapReduce編程模型

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

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

2 粗粒度并行遺傳算法

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

圖2 遺傳算法流程

傳統(tǒng)的遺傳算法有兩個(gè)嚴(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)性最強(qiáng)和應(yīng)用最廣的遺傳算法并行化模型［6］。它將隨機(jī)生成的初始種群依處理器個(gè)數(shù)分割成若干個(gè)較大的子種群，各個(gè)子種群在不同的處理器上相互獨(dú)立地并發(fā)執(zhí)行遺傳操作，每經(jīng)過一定的進(jìn)化代數(shù)，各子種群間再相互交換若干數(shù)量的個(gè)體，以實(shí)現(xiàn)各個(gè)子種群的共同進(jìn)化。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 環(huán)境搭建

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

4.2 單機(jī)處理比較實(shí)驗(yàn)

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

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

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

NIND=120;%個(gè)體數(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)

實(shí)驗(yàn)結(jié)果如表1所示。

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

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

圖6 Shubert函數(shù)實(shí)驗(yàn)結(jié)果對(duì)比

4.3 集群加速比實(shí)驗(yàn)

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

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

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

5 結(jié)束語(yǔ)

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

［1］胡晨駿，王曉蔚.基于多核集群系統(tǒng)的并行編程模型的研究［J］.計(jì)算機(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］.北京:國(guó)防工業(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.