胡濤

（武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢 430081）

遺傳算法自Holland教授于1975年提出后，經(jīng)Goldberg等人歸納總結(jié)形成一類模擬進(jìn)化算法[1]。作為一種自適應(yīng)全局優(yōu)化搜索算法，其自組織、自適應(yīng)和智能性，對所求解問題的未知特點(diǎn)有很強(qiáng)的魯棒性。簡單通用，適于并行處理及高效特點(diǎn)，該類算法廣泛應(yīng)用于自動控制，故障診斷，模式識別，計(jì)算機(jī)科學(xué)等領(lǐng)域，尤其是近年來發(fā)展迅速的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域，也體現(xiàn)了該類算法在大規(guī)模問題上的適用性。

互聯(lián)網(wǎng)的快速發(fā)展促進(jìn)了各個(gè)學(xué)科面臨的大容量的信息高效處理的可能性，數(shù)據(jù)密集型的的架構(gòu)是一種切實(shí)可行的方案[2]。傳統(tǒng)的基于MPI架構(gòu)的并行GA算法在處理問題域時(shí)需要詳細(xì)地了解處理計(jì)算機(jī)的構(gòu)造，受到函數(shù)式語言中map和reduce原語的啟發(fā)，Google提出了易于解決大規(guī)模問題的MapReduce抽象模型[3]。底層實(shí)現(xiàn)細(xì)節(jié)掩蓋于分布式文件系統(tǒng)（DFS）的MapReduce框架使得實(shí)現(xiàn)大規(guī)模并行計(jì)算變得較容易[4]，同時(shí)傳統(tǒng)GA算法處理大規(guī)模復(fù)雜問題在運(yùn)行速度上難以接受。運(yùn)用MapReduce并行計(jì)算框架改進(jìn)傳統(tǒng)的GA算法在解決復(fù)雜性和難度增大的問題上能改善運(yùn)行速度，并使采用GA處理更大規(guī)模的數(shù)據(jù)密集型問題成為可能，使其能夠作為針對海量數(shù)據(jù)的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的一種方法[5]，比如聚類分析中聚類中心的尋找。本文通過簡單遺傳算法求解單值最大問題說明了該算法在MapReduce下的并行算法實(shí)現(xiàn)，并對實(shí)驗(yàn)結(jié)果進(jìn)行了性能分析和討論。

1 簡單遺傳算法與MapReduce并行框架

1.1 簡單遺傳算法

選擇重組遺傳算法，一種最簡單的遺傳算法之一，種群的進(jìn)化主要依賴于選擇和重組[9-11]?；镜倪z傳算法步驟總結(jié)為如下：

1）用隨機(jī)產(chǎn)生的個(gè)體初始化種群；

2）評估初始種群所有個(gè)體的適應(yīng)度值；

3）使用錦標(biāo)賽方式選擇適應(yīng)度高的個(gè)體，不進(jìn)行替換；

4）將選擇的個(gè)體使用均勻交叉算子來重組創(chuàng)建新個(gè)體；

5）評估所有后代個(gè)體的適應(yīng)度值；

6）重復(fù)步驟3－5直到滿足一定的收斂準(zhǔn)則算法結(jié)束。

1． 2 MapReduce 并行框架

MapReduce是一種編程模型，也是一種并行計(jì)算框架，它簡化了在分布式環(huán)境下的開發(fā)并行應(yīng)用的模式[6－7]，圖1給出了MapReduce的執(zhí)行流程[8]。用戶只需要編寫簡單的用于處理所面臨問題的map和reduce函數(shù)，而不用關(guān)心實(shí)際的并行計(jì)算、容錯(cuò)、數(shù)據(jù)分布和負(fù)載均衡。定義好map和reduce函數(shù)后，框架就可以提交作業(yè)，根據(jù)給定問題的輸入分配Map任務(wù)到Mapper，每一個(gè)Mapper是一個(gè)獨(dú)立可運(yùn)行的處理單元，各個(gè)Mapper任務(wù)之間不互相通信。Map任務(wù)以用戶提供的map函數(shù)處理完之后將輸出寫入到運(yùn)行該Mapper的本地磁盤，在所有Mapper任務(wù)完成之后框架收集每個(gè)Mapper的輸出，并根據(jù)用戶指定的劃分方法將Mapper的輸出輸入到指定Reducer中。每一個(gè)Reducer也是一個(gè)獨(dú)立可運(yùn)行的處理單元，Reduce任務(wù)以用戶提供的reduce函數(shù)處理其輸入，處理完成之后將輸出寫入到指定的輸出文件。至此，一個(gè)MapReduce作業(yè)就已經(jīng)完成。

圖1 MapReduce執(zhí)行流圖Fig.1 Executing procedure of MapReduce

MapReduce作業(yè)的輸入是一些文件的集合，這些文件由DFS管理，在開始Map任務(wù)之前會將輸入文件劃分為M個(gè)文件片段，文件片段作為實(shí)際的Map輸入數(shù)據(jù)塊。對于輸入的數(shù)據(jù)塊，用戶可以指定輸入格式InputFormat，它負(fù)責(zé)將數(shù)據(jù)塊解析為 Map函數(shù)的輸入鍵值對，在指定為TextInputFormat情況下，V1為數(shù)據(jù)塊的一行，而K1為該行在數(shù)據(jù)塊中的索引。用戶設(shè)計(jì)的Partitioner會將Mapper的輸出中間值劃分到指定的Reducer中，它將框架收集到的Mapper的所有輸出一共劃分R份。Reducer首先合并相同鍵的鍵值對，形成，這樣就可能產(chǎn)生較小的鍵值對集合，然后框架調(diào)用用戶提供的Reduce函數(shù)處理這些，處理完成后將產(chǎn)生的根據(jù)用戶指定的OutputFormat寫入到輸出文件中。其中輸入、中間和輸出鍵值對可以互為不同的類型域。

由上可知，用戶只需要編寫與目標(biāo)功能相關(guān)的map和reduce函數(shù)，根據(jù)需要也可以重寫Partitioner，然后配置好作業(yè)相關(guān)的參數(shù)即可，比如向框架建議的Mapper數(shù)量，指定的Reducer數(shù)量，輸入輸出數(shù)據(jù)格式等。顯然，該框架的多個(gè)獨(dú)立運(yùn)行的Mapper和Reduce使得有良好的并行計(jì)算能力，同時(shí)處理的數(shù)據(jù)量的數(shù)量級可以達(dá)到PB以上。

2 基于MapReduce模型的算法及實(shí)現(xiàn)

根據(jù)上述遺傳算法流程，我們在MapReduce框架下予以實(shí)現(xiàn)。

步驟2）～5）中的個(gè)體適應(yīng)度評估需要對每個(gè)個(gè)體獨(dú)立計(jì)算，考慮到map函數(shù)的輸入是鍵值對，輸出也是鍵值對，在map中必須有如下兩個(gè)函數(shù)：

那么，map函數(shù)主要匹配于對個(gè)體適應(yīng)度的評估，如圖2算法1。同時(shí)，它跟蹤記錄最好的個(gè)體，最后將其寫入分布式文件系統(tǒng)（DFS）中的一個(gè)全局文件。步驟6）中處理該作業(yè)的客戶端在MapReduce完成后從該文件讀取這些值，檢查是否滿足收斂準(zhǔn)則。

圖2 算法1：GA迭代的Map階段Fig.2 Algorithm 1:GA iteration’s Map step

如果GA算法的第3）步在每個(gè)結(jié)點(diǎn)的本地執(zhí)行，空間的限制會被引入，減少了選擇壓力，并導(dǎo)致增加了收斂的時(shí)間。因此，分散和分布式選擇算法被提出來。觀察MapReduce框架中的執(zhí)行流程如圖1所示，唯一有全局?jǐn)?shù)據(jù)交換的地方是Map和Reduce之間的重排劃分階段，這也保證了算法具有全局搜索解的特性?？蚣苤械腜artitioner是實(shí)現(xiàn)將Map輸出重排并輸入到 Reduce的階段，其包含的函數(shù)GETPARTITION（）返回給定鍵值對將要傳遞到的Reducer的序號。

默認(rèn)的劃分方式是哈希（Hash）法，即使用 Hash（Key）%numReducers來散列這些鍵值對，這樣能夠使得與一個(gè)給定鍵相對應(yīng)的所有值裝載到同一個(gè)Reducer，然后應(yīng)用于reduce函數(shù)。但是這并不符合遺傳算法的要求，有以下2個(gè)原因：1）哈希函數(shù)將N個(gè)個(gè)體的空間分割成r個(gè)不同的類型：N0，N1，…，Nr-1，其中 Ni={n:Hash（n）=i}，這樣每一個(gè)分區(qū)的個(gè)體孤立于其他所有的分區(qū)。因此，哈希劃分引入了人為的基于低序位的空間限制，導(dǎo)致遺傳算法的收斂需要花費(fèi)更多迭代次數(shù)或者根本不收斂。2）隨著遺傳算法的迭代運(yùn)行，接近最優(yōu)的個(gè)體占據(jù)種群的多數(shù)，支配著群體，而采用哈希法這些個(gè)體的副本將會被送到一個(gè)同一個(gè)Reducer中，這樣會導(dǎo)致某些Reducer的負(fù)載過大，個(gè)體分布便會變得不均勻，偏離均勻分布，這會加大并行處理的使用，破壞了框架的負(fù)載均衡性。最后，當(dāng)算法收斂時(shí)，所有的個(gè)體將會被那一個(gè)Reducer處理。這樣，隨著算法的趨向于收斂時(shí)并行化就降低了，也會導(dǎo)致更多次的迭代。

圖3 算法2：GA迭代的Partition階段Fig.3 Algorithm 2:GA iteration’s partition step

由于上述原因，重寫了默認(rèn)的分區(qū)函數(shù)，提供了自己編寫的分區(qū)方法，圖3算法2那樣隨機(jī)劃分了即將輸入到不同Reducer之間的個(gè)體。

圖4 算法3：GA迭代的Reduce階段Fig.4 Algorithm 3:GA iteration’s reduce step

步驟3）和4）中的種群遺傳操作：選擇，交叉，變異均實(shí)現(xiàn)于Reduce中，如圖4算法3所示。在選擇父代交叉?zhèn)€體之前，采用維護(hù)一個(gè)最優(yōu)個(gè)體最小堆tournArray[0-tSize]的最優(yōu)個(gè)體保留策略，再選擇無替換的隨機(jī)聯(lián)賽方式選擇個(gè)體。它執(zhí)行在S個(gè)隨機(jī)選擇的個(gè)體中，勝者被選擇出來。這一過程重復(fù)種群大小的次數(shù)，即產(chǎn)生父代種群。既然隨機(jī)選擇個(gè)體與隨機(jī)重排所有個(gè)體后再逐個(gè)的選擇相當(dāng)，reduce函數(shù)必須要逐個(gè)遍歷所有個(gè)體。起初個(gè)體被緩沖在競爭窗口的最后一輪，當(dāng)窗口滿時(shí)，就從其中選擇出優(yōu)勝的個(gè)體放入交叉窗口。當(dāng)交叉窗口滿時(shí)，采用均勻交叉算子在兩個(gè)父代個(gè)體之間進(jìn)行交叉操作，然后對產(chǎn)生的兩個(gè)新個(gè)體采取變異，即產(chǎn)生了下一代種群中的新個(gè)體，當(dāng)所有父代個(gè)體處理完成后算法的該次迭代完成，新種群為所有Reduce的輸出。

由于在MapReduce模型中表示循環(huán)有缺陷，每一次迭代由一個(gè)Map任務(wù)和一個(gè)Reduce任務(wù)組成，對應(yīng)于步驟6）中的循環(huán)迭代需要在框架外部采取重復(fù)提交作業(yè)的方式來實(shí)現(xiàn)，并且必須執(zhí)行到滿足收斂準(zhǔn)則為止。

3 實(shí)驗(yàn)分析

單值最大問題是一個(gè)最大化位串中1的個(gè)數(shù)組成的簡單問題。一般來說，該問題被描述成查找一個(gè)位串x→={x1，x2，…，xN}，其中 xi∈{0，1}使得等式（3）有最大值：

因此，算法的問題編碼即個(gè)體（染色體）為位串x→，可以存儲在一個(gè)整型數(shù)組中，數(shù)組大小為[N/size of（int）]，每一個(gè)bit位表示基因位xi，個(gè)體適應(yīng)度的計(jì)算即為對該數(shù)組中所有bit位累計(jì)求和；選擇操作中以reducer_id.current_time作為隨機(jī)數(shù)產(chǎn)生器種子，交叉、變異和適應(yīng)度計(jì)算均可以采用有效的位運(yùn)算來提高效率[12]；對于每一次實(shí)驗(yàn)，GA的初始種群大小設(shè)置為N log N。由于串行處理部分的存在，根據(jù)Amdahl定律[13]，算法加速是受限制的，可以考慮在一個(gè)單獨(dú)的MapReduce作業(yè)中構(gòu)造初始化種群，Map產(chǎn)生隨機(jī)個(gè)體，Reduce不需要對種群進(jìn)行任何計(jì)算，則可以將Reducers個(gè)數(shù)設(shè)置為0。

算例采用Java編寫，運(yùn)行在8個(gè)從結(jié)點(diǎn)和1個(gè)主結(jié)點(diǎn)的小型集群上。每一個(gè)從結(jié)點(diǎn)配置為Intel 2 GHz以上雙核處理器，硬盤空間320 G以上，2 G內(nèi)存；均采用Ubuntu 10.10操作系統(tǒng)；主結(jié)點(diǎn)配置為Intel 3.2G Hz四核處理器，硬盤空間1TB，4 G內(nèi)存，所有結(jié)點(diǎn)均采用Ubuntu 10.10操作系統(tǒng)。HDFS和MapReduce版本為1.0.3發(fā)布版。部署好運(yùn)行環(huán)境后，這些主從結(jié)點(diǎn)被集成在分布式文件系統(tǒng)（HDFS）中，每個(gè)從結(jié)點(diǎn)能并行運(yùn)行5個(gè)Mapper和3個(gè)Reducer。這些結(jié)點(diǎn)盡管能滿負(fù)荷運(yùn)算，但是由于硬盤連接，或者額外的計(jì)算負(fù)荷，速度會降低。不論哪個(gè)結(jié)點(diǎn)先完成，它會寫到輸出并且其他的對該結(jié)點(diǎn)的探測性工作就會終止。

實(shí)驗(yàn)結(jié)果分析如下：

圖5 N=10 000時(shí)的收斂性Fig.5 Convergence when N=10 000

算法的收斂性分析：本實(shí)驗(yàn)中，取N=1 000的單值最大問題的GA執(zhí)行過程，在種群平均適應(yīng)度達(dá)到接近1 000的時(shí)候，搜索求解到某一個(gè)個(gè)x體所有位串的值xi=1的情況下進(jìn)化迭代終止。如圖5所示，未采取最優(yōu)個(gè)體保留策略下GA經(jīng)過220次迭代，種群平均適應(yīng)度達(dá)到接近 1 000，平均每次迭代耗時(shí) 171 s；相比較而言，采取最小堆維護(hù)的最優(yōu)個(gè)體保留的方法，平均每次迭代耗時(shí)稍微有所增加，為176，但是迭代次數(shù)減少了，經(jīng)過200次迭代就已經(jīng)滿足收斂條件了。

總體負(fù)載不變下的可擴(kuò)展性：將種群規(guī)模的大小休正到5 000個(gè)個(gè)體變量，同時(shí)增大Mapper的數(shù)量。如圖6所示，隨著越來越多的Mapper增加進(jìn)來，每次迭代的時(shí)間越來越少。因此，增加更多的計(jì)算資源并且增大種群大小會減少每次迭代時(shí)間。同樣，40個(gè)Mappers之后的Map容量的飽和引起了每次迭代時(shí)間的輕微增加。并且，在MapReduce框架之上（大約6 s的初始化和終結(jié)一個(gè)MapReduce作業(yè)）消耗的引入，根據(jù)Amdahl定律，總體速度提升是有界限的。但是，如同前一個(gè)實(shí)驗(yàn)所示，MapReduce模型及其適用于處理大規(guī)模問題，算法中初始化的種群大小比常規(guī)遺傳算法中大很多是很合理的。

圖6 負(fù)載不變下的可擴(kuò)展性Fig.6 Scalability with constant overall load

增大問題規(guī)模下的可擴(kuò)展性：使用最多的資源，同時(shí)增大變量的個(gè)數(shù)。如圖7所示，實(shí)現(xiàn)規(guī)模到N=10 000，保持種群大小。發(fā)現(xiàn)增加更多的結(jié)點(diǎn)將會使問題大小規(guī)模化到更大。隨著基因位數(shù)增加到10 000個(gè)每次迭代的時(shí)間顯著增加了，并且種群規(guī)模也以n log n增大，但此時(shí)算法搜索的解空間范圍已經(jīng)從21000增大到210000了。

圖7 增大問題規(guī)模下的可擴(kuò)展性Fig.7 Scalability with increasing the problem size

4 結(jié)束語

文中在仔細(xì)探討了MapReduce并行計(jì)算框架的基礎(chǔ)上改進(jìn)了典型的簡單遺傳算法使其適應(yīng)MapReduce模型，并且提出了適用于框架的最優(yōu)個(gè)體保留策略的一種新并行遺傳算法，結(jié)合遺傳算法本身含有的隱并行性及已有的并行遺傳算法模型，描述了在Hadoop MapReduce框架下遺傳算法的執(zhí)行流程。設(shè)計(jì)并實(shí)現(xiàn)了求解單值最大問題的算例，通過該算例收斂性分析和擴(kuò)展性分析說明了在針對數(shù)據(jù)密集型的大規(guī)模問題應(yīng)用時(shí)，基于該框架的并行遺傳算法是個(gè)切實(shí)可行的方法。本文只是探討了標(biāo)準(zhǔn)遺傳算法在該框架下的設(shè)計(jì)和實(shí)現(xiàn)，對于一些擴(kuò)展的GA算法未作討論，這些擴(kuò)展的算法可以依據(jù)本文中的方法給予具體實(shí)現(xiàn)，基于該框架的更多的并行算法有待今后探討。

[1]Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan Press，1975.

[2]Beynon M D，Kurc T，Sussman A，et al.Design of a framework for data-intensive wide-area applications.In HCW’00:Proceedings of the 9th Heterogeneous Computing Workshop [C]//IEEE Computer Society.Washington，DC，USA，2000.

[3]Dean J，Ghemawat S.Mapreduce:Simplified data processing on large clusters.Commun[J].ACM，2008，51（1）:107-113.

[4]朱珠．基于Hadoop的海量數(shù)據(jù)處理模型研究和應(yīng)用[D].北京:北京郵電大學(xué)，2008.

[5]賈兆紅，倪志偉.改進(jìn)型遺傳算法在數(shù)據(jù)挖掘中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2002，22（9）:31-33.JIA Zhao-hong，NI Zhi-wei.An improved genetic algorithm and its application in data mining[J].Computer Applications，2002，22（9）:31-33.

[6]鄭啟龍，房明，汪勝.基于MapReduce模型的并行科學(xué)計(jì)算[J].微電子學(xué)與計(jì)算機(jī)，2009，26（8）:13-17.ZHENGQi-long，F(xiàn)ANGMing，WANGSheng.Scientific parallel computing based on MapReduce model[J].Microelectronics&Computer，2009，26（8）:13－17.

[7]Apache hadoop.MapReduce.[EB/OL].http://hadoop.apache.org.

[8]孫廣中，肖鋒，熊曦.MapReduce模型的調(diào)度及容錯(cuò)機(jī)制研究[J].微電子學(xué)與計(jì)算機(jī)，2007，9（24）:14－17.SUN Guang-zhong，XIAO Feng，XIONG Xi.Study on scheduling and fault tolerance strategy of MapReduce[J].Microelectronics&Computer，2007，9（24）:14－17.

[9]周明，孫樹棟．遺傳算法原理及應(yīng)用[M].北京:國防工業(yè)出版社，1999.

[10]Goldberg D E.Genetic algorithms in search，optimization and machine learning[M].Boston：Addison—Wesley Longman Press，1989.

[11]Goldberg D E，Korb B，Deb K.Messy genetic algorithms:Motivation， analysis， and first results[J].Complex Systems，1989，3（5）:493－530.

[12]楊啟文，蔣靜坪，張國宏．遺傳算法優(yōu)化速度的改進(jìn)[J]．軟件學(xué)報(bào)，2001，12（2）:270－275.YANGQi-wen，JIANGJing-ping，ZHANGGuo-hong.Improving optimization speed for genetic algorithms[J].Journal of Software，2001，12（2）:270－275.

[13]馮葉，鄧倩妮.非對稱多核體系下的阿姆達(dá)爾定律性能模型研究[J].微電子學(xué)與計(jì)算機(jī)，2011，28（8）:32－34.FENGYe，DENGQian-ni.A study of Amdahl’slaw performace model on asymmetric multicore system[J].Microelectronics&Computer，2011，28（8）:32－34.