基于MapReduce模型遺傳算法的一種改進與實現(xiàn)
2013-01-18 12:04:22胡濤
電子設計工程 2013年5期
胡濤
（武漢科技大學 信息科學與工程學院，湖北 武漢 430081）
遺傳算法自Holland教授于1975年提出后，經(jīng)Goldberg等人歸納總結形成一類模擬進化算法[1]。作為一種自適應全局優(yōu)化搜索算法，其自組織、自適應和智能性，對所求解問題的未知特點有很強的魯棒性。簡單通用，適于并行處理及高效特點，該類算法廣泛應用于自動控制，故障診斷，模式識別，計算機科學等領域，尤其是近年來發(fā)展迅速的機器學習和數(shù)據(jù)挖掘領域，也體現(xiàn)了該類算法在大規(guī)模問題上的適用性。
互聯(lián)網(wǎng)的快速發(fā)展促進了各個學科面臨的大容量的信息高效處理的可能性，數(shù)據(jù)密集型的的架構是一種切實可行的方案[2]。傳統(tǒng)的基于MPI架構的并行GA算法在處理問題域時需要詳細地了解處理計算機的構造，受到函數(shù)式語言中map和reduce原語的啟發(fā)，Google提出了易于解決大規(guī)模問題的MapReduce抽象模型[3]。底層實現(xiàn)細節(jié)掩蓋于分布式文件系統(tǒng)（DFS）的MapReduce框架使得實現(xiàn)大規(guī)模并行計算變得較容易[4]，同時傳統(tǒng)GA算法處理大規(guī)模復雜問題在運行速度上難以接受。運用MapReduce并行計算框架改進傳統(tǒng)的GA算法在解決復雜性和難度增大的問題上能改善運行速度，并使采用GA處理更大規(guī)模的數(shù)據(jù)密集型問題成為可能，使其能夠作為針對海量數(shù)據(jù)的機器學習和數(shù)據(jù)挖掘的一種方法[5]，比如聚類分析中聚類中心的尋找。本文通過簡單遺傳算法求解單值最大問題說明了該算法在MapReduce下的并行算法實現(xiàn)，并對實驗結果進行了性能分析和討論。
1 簡單遺傳算法與MapReduce并行框架
1.1 簡單遺傳算法
選擇重組遺傳算法，一種最簡單的遺傳算法之一，種群的進化主要依賴于選擇和重組[9-11]。基本的遺傳算法步驟總結為如下：
1）用隨機產(chǎn)生的個體初始化種群；
2）評估初始種群所有個體的適應度值；
3）使用錦標賽方式選擇適應度高的個體，不進行替換；
4）將選擇的個體使用均勻交叉算子來重組創(chuàng)建新個體；
5）評估所有后代個體的適應度值；
6）重復步驟3－5直到滿足一定的收斂準則算法結束。
1． 2 MapReduce 并行框架
MapReduce是一種編程模型，也是一種并行計算框架，它簡化了在分布式環(huán)境下的開發(fā)并行應用的模式[6－7]，圖1給出了MapReduce的執(zhí)行流程[8]。用戶只需要編寫簡單的用于處理所面臨問題的map和reduce函數(shù)，而不用關心實際的并行計算、容錯、數(shù)據(jù)分布和負載均衡。定義好map和reduce函數(shù)后，框架就可以提交作業(yè)，根據(jù)給定問題的輸入分配Map任務到Mapper，每一個Mapper是一個獨立可運行的處理單元，各個Mapper任務之間不互相通信。Map任務以用戶提供的map函數(shù)處理完之后將輸出寫入到運行該Mapper的本地磁盤，在所有Mapper任務完成之后框架收集每個Mapper的輸出，并根據(jù)用戶指定的劃分方法將Mapper的輸出輸入到指定Reducer中。每一個Reducer也是一個獨立可運行的處理單元，Reduce任務以用戶提供的reduce函數(shù)處理其輸入，處理完成之后將輸出寫入到指定的輸出文件。至此，一個MapReduce作業(yè)就已經(jīng)完成。
圖1 MapReduce執(zhí)行流圖Fig.1 Executing procedure of MapReduce
MapReduce作業(yè)的輸入是一些文件的集合，這些文件由DFS管理，在開始Map任務之前會將輸入文件劃分為M個文件片段，文件片段作為實際的Map輸入數(shù)據(jù)塊。對于輸入的數(shù)據(jù)塊，用戶可以指定輸入格式InputFormat，它負責將數(shù)據(jù)塊解析為 Map函數(shù)的輸入鍵值對
由上可知，用戶只需要編寫與目標功能相關的map和reduce函數(shù)，根據(jù)需要也可以重寫Partitioner，然后配置好作業(yè)相關的參數(shù)即可，比如向框架建議的Mapper數(shù)量，指定的Reducer數(shù)量，輸入輸出數(shù)據(jù)格式等。顯然，該框架的多個獨立運行的Mapper和Reduce使得有良好的并行計算能力，同時處理的數(shù)據(jù)量的數(shù)量級可以達到PB以上。
2 基于MapReduce模型的算法及實現(xiàn)
根據(jù)上述遺傳算法流程，我們在MapReduce框架下予以實現(xiàn)。
步驟2）～5）中的個體適應度評估需要對每個個體獨立計算，考慮到map函數(shù)的輸入是
那么，map函數(shù)主要匹配于對個體適應度的評估，如圖2算法1。同時，它跟蹤記錄最好的個體，最后將其寫入分布式文件系統(tǒng)（DFS）中的一個全局文件。步驟6）中處理該作業(yè)的客戶端在MapReduce完成后從該文件讀取這些值，檢查是否滿足收斂準則。
圖2 算法1：GA迭代的Map階段Fig.2 Algorithm 1:GA iteration’s Map step
如果GA算法的第3）步在每個結點的本地執(zhí)行，空間的限制會被引入，減少了選擇壓力，并導致增加了收斂的時間。因此，分散和分布式選擇算法被提出來。觀察MapReduce框架中的執(zhí)行流程如圖1所示，唯一有全局數(shù)據(jù)交換的地方是Map和Reduce之間的重排劃分階段，這也保證了算法具有全局搜索解的特性。框架中的Partitioner是實現(xiàn)將Map輸出重排并輸入到 Reduce的階段，其包含的函數(shù)GETPARTITION（）返回給定鍵值對將要傳遞到的Reducer的序號。
默認的劃分方式是哈希（Hash）法，即使用 Hash（Key）%numReducers來散列這些鍵值對，這樣能夠使得與一個給定鍵相對應的所有值裝載到同一個Reducer，然后應用于reduce函數(shù)。但是這并不符合遺傳算法的要求，有以下2個原因：1）哈希函數(shù)將N個個體的空間分割成r個不同的類型：N0，N1，…，Nr-1，其中 Ni={n:Hash（n）=i}，這樣每一個分區(qū)的個體孤立于其他所有的分區(qū)。因此，哈希劃分引入了人為的基于低序位的空間限制，導致遺傳算法的收斂需要花費更多迭代次數(shù)或者根本不收斂。2）隨著遺傳算法的迭代運行，接近最優(yōu)的個體占據(jù)種群的多數(shù)，支配著群體，而采用哈希法這些個體的副本將會被送到一個同一個Reducer中，這樣會導致某些Reducer的負載過大，個體分布便會變得不均勻，偏離均勻分布，這會加大并行處理的使用，破壞了框架的負載均衡性。最后，當算法收斂時，所有的個體將會被那一個Reducer處理。這樣，隨著算法的趨向于收斂時并行化就降低了，也會導致更多次的迭代。
圖3 算法2：GA迭代的Partition階段Fig.3 Algorithm 2:GA iteration’s partition step
由于上述原因，重寫了默認的分區(qū)函數(shù)，提供了自己編寫的分區(qū)方法，圖3算法2那樣隨機劃分了即將輸入到不同Reducer之間的個體。
圖4 算法3：GA迭代的Reduce階段Fig.4 Algorithm 3:GA iteration’s reduce step
步驟3）和4）中的種群遺傳操作：選擇，交叉，變異均實現(xiàn)于Reduce中，如圖4算法3所示。在選擇父代交叉?zhèn)€體之前，采用維護一個最優(yōu)個體最小堆tournArray[0-tSize]的最優(yōu)個體保留策略，再選擇無替換的隨機聯(lián)賽方式選擇個體。它執(zhí)行在S個隨機選擇的個體中，勝者被選擇出來。這一過程重復種群大小的次數(shù)，即產(chǎn)生父代種群。既然隨機選擇個體與隨機重排所有個體后再逐個的選擇相當，reduce函數(shù)必須要逐個遍歷所有個體。起初個體被緩沖在競爭窗口的最后一輪，當窗口滿時，就從其中選擇出優(yōu)勝的個體放入交叉窗口。當交叉窗口滿時，采用均勻交叉算子在兩個父代個體之間進行交叉操作，然后對產(chǎn)生的兩個新個體采取變異，即產(chǎn)生了下一代種群中的新個體，當所有父代個體處理完成后算法的該次迭代完成，新種群為所有Reduce的輸出。
由于在MapReduce模型中表示循環(huán)有缺陷，每一次迭代由一個Map任務和一個Reduce任務組成，對應于步驟6）中的循環(huán)迭代需要在框架外部采取重復提交作業(yè)的方式來實現(xiàn)，并且必須執(zhí)行到滿足收斂準則為止。
3 實驗分析
單值最大問題是一個最大化位串中1的個數(shù)組成的簡單問題。一般來說，該問題被描述成查找一個位串x→={x1，x2，…，xN}，其中 xi∈{0，1}使得等式（3）有最大值：
因此，算法的問題編碼即個體（染色體）為位串x→，可以存儲在一個整型數(shù)組中，數(shù)組大小為[N/size of（int）]，每一個bit位表示基因位xi，個體適應度的計算即為對該數(shù)組中所有bit位累計求和；選擇操作中以reducer_id.current_time作為隨機數(shù)產(chǎn)生器種子，交叉、變異和適應度計算均可以采用有效的位運算來提高效率[12]；對于每一次實驗，GA的初始種群大小設置為N log N。由于串行處理部分的存在，根據(jù)Amdahl定律[13]，算法加速是受限制的，可以考慮在一個單獨的MapReduce作業(yè)中構造初始化種群，Map產(chǎn)生隨機個體，Reduce不需要對種群進行任何計算，則可以將Reducers個數(shù)設置為0。
算例采用Java編寫，運行在8個從結點和1個主結點的小型集群上。每一個從結點配置為Intel 2 GHz以上雙核處理器，硬盤空間320 G以上，2 G內存；均采用Ubuntu 10.10操作系統(tǒng)；主結點配置為Intel 3.2G Hz四核處理器，硬盤空間1TB，4 G內存，所有結點均采用Ubuntu 10.10操作系統(tǒng)。HDFS和MapReduce版本為1.0.3發(fā)布版。部署好運行環(huán)境后，這些主從結點被集成在分布式文件系統(tǒng)（HDFS）中，每個從結點能并行運行5個Mapper和3個Reducer。這些結點盡管能滿負荷運算，但是由于硬盤連接，或者額外的計算負荷，速度會降低。不論哪個結點先完成，它會寫到輸出并且其他的對該結點的探測性工作就會終止。
實驗結果分析如下：
圖5 N=10 000時的收斂性Fig.5 Convergence when N=10 000
算法的收斂性分析：本實驗中，取N=1 000的單值最大問題的GA執(zhí)行過程，在種群平均適應度達到接近1 000的時候，搜索求解到某一個個x體所有位串的值xi=1的情況下進化迭代終止。如圖5所示，未采取最優(yōu)個體保留策略下GA經(jīng)過220次迭代，種群平均適應度達到接近 1 000，平均每次迭代耗時 171 s；相比較而言，采取最小堆維護的最優(yōu)個體保留的方法，平均每次迭代耗時稍微有所增加，為176，但是迭代次數(shù)減少了，經(jīng)過200次迭代就已經(jīng)滿足收斂條件了。
總體負載不變下的可擴展性：將種群規(guī)模的大小休正到5 000個個體變量，同時增大Mapper的數(shù)量。如圖6所示，隨著越來越多的Mapper增加進來，每次迭代的時間越來越少。因此，增加更多的計算資源并且增大種群大小會減少每次迭代時間。同樣，40個Mappers之后的Map容量的飽和引起了每次迭代時間的輕微增加。并且，在MapReduce框架之上（大約6 s的初始化和終結一個MapReduce作業(yè)）消耗的引入，根據(jù)Amdahl定律，總體速度提升是有界限的。但是，如同前一個實驗所示，MapReduce模型及其適用于處理大規(guī)模問題，算法中初始化的種群大小比常規(guī)遺傳算法中大很多是很合理的。
圖6 負載不變下的可擴展性Fig.6 Scalability with constant overall load
增大問題規(guī)模下的可擴展性：使用最多的資源，同時增大變量的個數(shù)。如圖7所示，實現(xiàn)規(guī)模到N=10 000，保持種群大小。發(fā)現(xiàn)增加更多的結點將會使問題大小規(guī)模化到更大。隨著基因位數(shù)增加到10 000個每次迭代的時間顯著增加了，并且種群規(guī)模也以n log n增大，但此時算法搜索的解空間范圍已經(jīng)從21000增大到210000了。
圖7 增大問題規(guī)模下的可擴展性Fig.7 Scalability with increasing the problem size
4 結束語
文中在仔細探討了MapReduce并行計算框架的基礎上改進了典型的簡單遺傳算法使其適應MapReduce模型，并且提出了適用于框架的最優(yōu)個體保留策略的一種新并行遺傳算法，結合遺傳算法本身含有的隱并行性及已有的并行遺傳算法模型，描述了在Hadoop MapReduce框架下遺傳算法的執(zhí)行流程。設計并實現(xiàn)了求解單值最大問題的算例，通過該算例收斂性分析和擴展性分析說明了在針對數(shù)據(jù)密集型的大規(guī)模問題應用時，基于該框架的并行遺傳算法是個切實可行的方法。本文只是探討了標準遺傳算法在該框架下的設計和實現(xiàn)，對于一些擴展的GA算法未作討論，這些擴展的算法可以依據(jù)本文中的方法給予具體實現(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ù)處理模型研究和應用[D].北京:北京郵電大學，2008.
[5]賈兆紅，倪志偉.改進型遺傳算法在數(shù)據(jù)挖掘中的應用[J].計算機應用，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模型的并行科學計算[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模型的調度及容錯機制研究[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]周明，孫樹棟．遺傳算法原理及應用[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]．軟件學報，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]馮葉，鄧倩妮.非對稱多核體系下的阿姆達爾定律性能模型研究[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.
