基于MapReduce的GA—BP神經網絡算法并行化設計及實現

楊婉婧+邢洪嘉+曹建芳

摘 要：為提高BP神經網絡算法的運行效率，利用遺傳算法和并行編程思想，提出了Hadoop平臺下基于MapReduce的遺傳算法優化BP神經網絡的并行化設計及實現方法。利用遺傳算法優化BP神經網絡的初始權值和閾值，提高算法分類準確率；采用MapReduce并行編程模型實現算法的并行化處理，解決BP神經網絡在處理大規模樣本數據集時存在的硬件開銷和通信開銷大的問題。選用Caltech 256圖像數據集，與傳統的串行遺傳算法優化BP神經網絡算法實驗對比，驗證了并行化GA-BP神經網絡算法的優越性。

關鍵詞：遺傳算法；BP神經網絡；MapReduce并行編程模型；并行化設計

DOIDOI：10.11907/rjdk.171303

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2017）007-0040-04

0 引言

BP（Back Propagation）神經網絡是一種多層前饋型神經網絡，是一種通過不斷修改各層神經元之間的連接權值以及各神經元的閾值，以使網絡輸出不斷逼近期望輸出的學習過程[1]。由于它具有很強的泛化能力，并可實現任何復雜程度的非線性映射關系，因此在很多領域得到了廣泛應用[2]。然而，BP神經網絡算法是基于函數誤差梯度下降的思想，不具備全局搜索能力；而且，網絡各層之間的連接權值和神經元的閾值在初始訓練時是0～1的任意值，這會導致算法收斂速度慢，而且不一定得到最優解。近年來，學者們先后提出一些改進的算法來優化BP神經網絡的初始權值和閾值，如遺傳算法[3]、粒子群算法、螢火蟲算法[4]等。然而，伴隨著大數據時代的到來，樣本規模愈來愈大，上述傳統的串行算法不僅存在硬件支撐瓶頸的問題，而且算法訓練時間會變得很長，系統效率明顯下降。目前，算法的并行化設計受到廣泛關注。鄭曉薇等[5]在MPI集群環境下設計了一種多BP神經網絡并行集成模型，實現了圖像的多語義分類，實驗效果良好。劉晶[6]在PVM并行環境下，對大型矩陣運行進行了并行處理，有效降低了矩陣運算的耗時。但是，基于MPI和PVM的并行設計需要開發者對計算機硬件體系結構有較清晰的了解，并且各節點間通信耗時較大，實現也較困難[7]。而近年流行起來的Hadoop平臺下的MapReduce框架是一種面向分布式環境的并行計算模式，它向開發人員提供了完整的編程接口，并不需要開發者了解計算機的體系結構，因而逐漸成為當前算法并行化設計的研究熱點[8]。針對上述問題，本文提出一種GA-BP神經網絡的并行算法，并將其應用于圖像分類問題中。該算法在MapReduce并行編程模型下設計并行處理機制，使用遺傳算法（Genetic Algorithm，GA）優化BP神經網絡的初始權值和閾值，再使用不同的優化后的多個并行BP神經網絡訓練采用不同的樣本集，既保證了BP神經網絡能獲得最優解，又加快了網絡收斂速度，而且在有效降低樣本多樣性和復雜性對BP神經網絡性能影響的同時，大大縮短了訓練時間。

1 GA-BP神經網絡算法

BP神經網絡算法具有很強的自學習和自適應能力，能夠很好地解決非線性映射問題，但因其初始權值和閾值的任意性，導致網絡收斂速度慢，并且不一定能獲得最優解。因此，有必要對BP神經網絡的初始權值和閾值進行優化。遺傳算法是一種源于生物進化的智能優化搜索算法，因其設置參數少、收斂速度快，且在計算精度要求時，計算時間少、魯棒性高、易于實現等特點而得到廣泛應用。將遺傳算法引入BP神經網絡中，優化BP神經網絡的初始權值和閾值，將很好地解決BP神經網絡由于初始權值閾值的任意性而造成的一些缺陷。其算法分為遺傳算法優化階段和BP神經網絡訓練階段。

1.1 遺傳算法優化階段

（1）種群初始化。個體采用實數編碼，由BP神經網絡輸入層與隱含層的連接權值、隱含層閾值、隱含層與輸出層的連接權值、輸出層閾值4部分組成。

（2）適應度函數確定。根據個體得到BP神經網絡的初始權值和閾值，用訓練樣本訓練BP神經網絡后預測系統輸出，將預測輸出和期望輸出之間的誤差絕對值和E作為個體適應度值

（6）更新適應度值并判斷是否結束迭代，產生BP神經網絡的最優初始權值和閾值。

1.2 BP神經網絡訓練階段

（1）網絡初始化。根據樣本特征確定網絡結構、期望輸出、學習速率，接收遺傳算法優化得到的最優解個體作為網絡的初始權值和閾值。

（2）輸入訓練樣本，計算網絡各層輸出。

（3）計算網絡學習誤差。

（4）修正各層連接權值和閾值。

（5）判斷誤差是否滿足期望的要求或訓練達到設置的迭代次數，如滿足條件，則訓練結束，否則，繼續迭代學習。

2 GA-BP神經網絡算法并行化設計與實現

PSO-BP神經網絡算法雖然改善了傳統BP神經網絡算法的性能，但隨著數據規模的不斷擴大，BP神經網絡訓練時間會很長，效率問題逐漸暴露。MapReduce并行編程框架為大數據的處理提供了一種分布式并行計算環境，為提高BP神經網絡的時間效率和測試準確率，本文對PSO-BP神經網絡算法在MapReduce框架下進行了并行化設計。

2.1 MapReduce編程模型

Hadoop下的MapReduce是由Google公司提出的一種處理大規模數據的分布式并行編程模型，它將數據的計算過程劃分成Map和Reduce兩個階段，分別對應Mapper（）函數和Reducer（）函數實現，要求數據以鍵值對（key可以看作是數據的編號，value被看作數據的值）的形式輸入。Map階段，MapReduce將輸入數據切分成大小相等的片（Split），并將每個Split分解為鍵值對的形式作為正式輸入，執行Mapper（）函數生成中間結果，然后按照k2的值排序，將與k2值相同的對應的v2值放在一起形成一個新的列表，最后根據k2的范圍進行分組，形成Reduce任務；Reduce階段，對Map任務的輸出整合排序，將作為輸入，執行Reducer（）函數，得到鍵值對輸出到Hadoop的HDFS上。其處理過程如圖1所示。

2.2 遺傳算法并行化設計及實現

2.2.1 GA-Map（）設計及實現

根據MapReduce編程模型的數據輸入格式，本文也將遺傳算法輸入的數據轉化為的格式，其中，key代表個體的編號，value代表個體的屬性。Map階段，完成個體的初始化/適應度評價以及形成個體種群的最優個體等操作。遺傳算法的Map過程設計如下：

輸入：個體id，個體屬性值

輸出：key，最優個體集

GA-Map（個體id，個體屬性值）

{

對每個個體，獲取value值；

fit-value=fit（value）；//計算更新個體的適應度值//迭代更新個體If（滿足條件）key=new-key（key）；輸出key，最優個體集； }

2.2.2 GA-Reduce（）設計及實現

Reduce階段，接收Map任務生成的最優個體集，對信息進行整合，全局更新最優個體集，如果達到終止條件，輸出整個種群的最優個體。遺傳算法的Reduce過程設計如下：

輸入：key，最優個體集輸出：key，最優個體PSO-Reduce（key，最優個體集）{對各種群中的每一個最優個體，獲取其fit-value值；//全局迭代更新種群if（獲得問題最優解||達到最大迭代次數）輸出key，最優個體；}

當遺傳算法并行迭代完成后，得到的最優個體即為BP神經網絡的初始權值和閾值。

2.3 BP神經網絡并行化設計及實現

為克服BP神經網絡在樣本數量增多時硬件開銷大、訓練時間長等缺陷，本文基于MapReduce模型對BP神經網絡進行了并行化設計，通過Map任務和Reduce任務實現多BP神經網絡內部的自動并行運行，在大大縮短樣本訓練時間的同時，進而提高了訓練的精度。其模型結構如圖2所示。

2.3.1 BP-Map（）設計及實現

Map階段，Map任務根據輸入逐層計算網絡實際輸出，并將實際輸出與期望輸出相比較，計算網絡學習誤差，然后根據學習誤差計算網絡中各連接權值的更新量。BP神經網絡的Map任務設計如下：輸入：樣本id，樣本特征值輸出：樣本對應權值ω，權值更新量ΔωBP-Map（樣本id，樣本特征值）{//對每個樣本計算網絡各層輸出；

計算網絡學習誤差；對每個連接權值ω，計算權值更新量Δω；輸出（ω，Δω）； }

2.3.2 BP-Combine（）函數設計及實現

在MapReduce并行編程模型中，Combine（）函數可以對Map階段產生的中間結果作本地處理，從而大大降低通信開銷。由于使用BP神經網絡訓練的樣本數據日趨增多，因此有必要在進入Reduce任務之前使用Combine（）函數對Map任務產生的結果先進行處理。在BP神經網絡并行化設計過程中，Combine（）函數設計如下：

輸入：鍵值對<ω，Δω>輸出：鍵值對<ω′，Δω′>BP-Combine（ω，Δω）{初始化變量count=0；//統計訓練樣本的數目//對每個訓練樣本解析并處理Δω的各維坐標值；count←count+1；ω′←ω；收集所有ω相同的鍵值對，進行本地歸約，得到Δω′；輸出ω′，Δω′；}

2.3.3 BP-Reduce（）設計及實現Reduce階段，接收Combine（）函數的輸出，然后統計所有權值相同樣本的總體更新量和平均更新量，并更新網絡權值。BP神經網絡的Reduce任務設計如下：

輸入：Combine函數的輸出：<ω′，Δω′>輸出：<ω′，∑ni=1Δω′/n>BP-Reduce（ω′，Δω′）{累加所有ω′相同樣本的Δω′，得到∑ni=1Δω′；計算每個權值的平均更新量；輸出ω′，∑ni=1Δω′/n； }BP神經網絡一直重復上述Map和Reduce任務，直至誤差滿足規定的精度或達到迭代次數。

3 實驗及結果分析

為驗證本文提出的并行GA-BP神經網絡算法的性能，本文在Hadoop平臺下對大量圖像的分類效果進行了測試。

3.1 實驗環境及數據

實驗環境是局域網內5臺計算機構成的Hadoop集群，1臺計算機做Master節點，其余4臺做Slave節點；所有節點配置都是4G雙核處理器、1T硬盤，操作系統是Ubuntu。

實驗數據來自Caltech 256圖像庫，該圖像庫可供免費使用，包含30 607幅、256個類別。

3.2 實驗結果及分析

為驗證所提出算法的性能，本文從分類準確率、加速比與效率等方面作了實驗比較。

3.2.1 分類準確率

本文在不同的圖像規模下，以訓練樣本數與測試樣本數約4：1的比例，對傳統的GA-BP神經網絡算法和本文提出的并行GA-BP神經網絡算法就分類準確率進行比較。本文采用計算機隨機結合人工選擇構造了5個數據集Data1、Data2、Data3、Data4和Data5。其中，Data1包含了3個類別的300幅場景圖像，Data2包含了5個類別的800幅場景圖像，Data3包含了8個類別的2 000幅場景圖像，Data4包含了12個類別的5 000幅圖像，Data5包含了15個類別的15 000幅場景圖像。實驗結果如表1所示。

從表1可以明顯看到，本文算法分類效果明顯優于傳統的GA-BP神經網絡算法，而且，隨著數據規模的增大，雖然兩種算法的分類準確率都在降低，但本文提出的并行GA-BP神經網絡算法顯然沒有下降到很低。這充分說明，基于MapReduce并行編程模型的算法在大規模數據集下的優越性非常明顯。

3.2.2 加速比與效率

對于MapReduce并行編程模型，衡量算法性能的兩個重要指標是加速比與效率。加速比是指同一任務在單個計算節點運行與在多個計算節點運行的時間之比，而效率是加速比與計算節點數量的比值[8]。理想情況下，加速比應隨著計算節點數量的增加而線性增長，效率是1保持不變。但由于受到負載平衡、通信開銷等因素的影響，加速比不會線性增長，效率也不可能達到1。研究表明，在效率達到0.5時，系統就獲得了很好的性能[9]。為更好地驗證MapReduce并行編程模型的優勢，本文隨機從Caltech 256圖像庫隨機選取了1 000幅以上的5個不同規模的圖像數據集，圖3和圖4分別是本文提出的算法在不同規模數據集下加速比與效率的實驗對比。

從圖3可以看出，加速比在隨著計算節點數的增加呈增長趨勢，而且數據規模越大，加速比增長的幅度越大，這也進一步說明越大規模的數據集才越能充分發揮多個計算節點的性能。從圖4中系統效率對比可以看出，數據集小的效率低于數據集大的效率，而且隨著計算節點數的增加，數據集規模較小時，系統效率下降較快，而當數據集規模不斷增大時，隨著計算節點個數增多，系統效率雖有降低，但下降幅度較小。系統效率的下降主要是因為一方面數據規模增大，系統處理的時間會增多，另一方面，隨著計算節點數的增加，節點間的通行開銷也會增加，但系統效率一直都在0.5以上，說明算法具有很好的并行性能和可擴展性能。

4 結語

本文對GA-BP神經網絡算法的并行化設計與實現進行了深入的探討和分析，研究了遺傳算法如何優化BP神經網絡的初始權值和閾值、遺傳算法及BP神經網絡的并行化設計及實現，并選擇Caltech 256圖像庫中的圖像數據，對算法的性能從多方面進行了驗證。實驗結果表明，本文提出的算法具有很好的并行性，可以充分利用分布式系統資源，改善算法分類效果；另外，基于MapReduce的分布式并行系統相對于單節點架構性能有很大提高，充分體現了并行處理的強大計算能力。隨著大數據、云計算等技術的迅速發展，對大規模數據集的處理和分析必將是今后一段時間的研究熱點。本文下一步研究的內容主要有：①改變Hadoop分布式平臺節點數量，調節相關參數，進一步提高算法效率；②改進遺傳算法，能更快、更容易地找到全局最優解；③優化算法Map任務和Reduce任務設計，進而提高算法分類準確率和時間性能。

參考文獻：

[1] 胡月.BP算法并行化及在數據挖掘中的應用研究[D].重慶：重慶大學，2003.

[2] JIANFANG CAO，LICHAO CHEN.Fuzzy emotional semantic analysis and automated annotation of scene images[J].Computational Intelligence and Neuroscience，2015：1-10.

[3] 高玉明，張仁津.基于遺傳算法和BP神經網絡的房價預測分析[J].計算機工程，2014，40（4）：187-191.

[4] 王改革，郭立紅，段紅，等.基于螢火蟲算法優化BP神經網絡的目標威脅估計[J].吉林大學學報：工學版，2013，43（4）：1064-1069.

[5] 鄭曉薇，李玉丹，馬名威.MPI 集群環境下圖像語義分類算法的并行化設計[J].小型微型計算機系統，2014，35（6）：1348-1352.

[6] 劉晶.基于PVM的并行計算[J].廣東石油化工學院學報，2012，12（4）：34-35.

[7] 趙玖玲，衛海鵬.基于MPI的并行遺傳算法的設計與實現[J].計算機科學，2006，33（9）：186-189.

[8] 朱為盛，王鵬.基于Hadoop 云計算平臺的大規模圖像檢索方案[J].計算機應用，2014，34（3）：695-699.

[9] 金偉健，王春枝.適于進化算法的迭代式MapReduce框架[J].計算機應用，2013，33（12）：3591-3595.