基于MapReduce的GA—BP神經(jīng)網(wǎng)絡(luò)算法并行化設(shè)計(jì)及實(shí)現(xiàn)

楊婉婧+邢洪嘉+曹建芳

摘 要：為提高BP神經(jīng)網(wǎng)絡(luò)算法的運(yùn)行效率，利用遺傳算法和并行編程思想，提出了Hadoop平臺下基于MapReduce的遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的并行化設(shè)計(jì)及實(shí)現(xiàn)方法。利用遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)值和閾值，提高算法分類準(zhǔn)確率；采用MapReduce并行編程模型實(shí)現(xiàn)算法的并行化處理，解決BP神經(jīng)網(wǎng)絡(luò)在處理大規(guī)模樣本數(shù)據(jù)集時存在的硬件開銷和通信開銷大的問題。選用Caltech 256圖像數(shù)據(jù)集，與傳統(tǒng)的串行遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)算法實(shí)驗(yàn)對比，驗(yàn)證了并行化GA-BP神經(jīng)網(wǎng)絡(luò)算法的優(yōu)越性。

關(guān)鍵詞：遺傳算法；BP神經(jīng)網(wǎng)絡(luò)；MapReduce并行編程模型；并行化設(shè)計(jì)

DOIDOI：10.11907/rjdk.171303

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）007-0040-04

0 引言

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

1 GA-BP神經(jīng)網(wǎng)絡(luò)算法

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

1.1 遺傳算法優(yōu)化階段

（1）種群初始化。個體采用實(shí)數(shù)編碼，由BP神經(jīng)網(wǎng)絡(luò)輸入層與隱含層的連接權(quán)值、隱含層閾值、隱含層與輸出層的連接權(quán)值、輸出層閾值4部分組成。

（2）適應(yīng)度函數(shù)確定。根據(jù)個體得到BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)值和閾值，用訓(xùn)練樣本訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)后預(yù)測系統(tǒng)輸出，將預(yù)測輸出和期望輸出之間的誤差絕對值和E作為個體適應(yīng)度值

（6）更新適應(yīng)度值并判斷是否結(jié)束迭代，產(chǎn)生BP神經(jīng)網(wǎng)絡(luò)的最優(yōu)初始權(quán)值和閾值。

1.2 BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練階段

（1）網(wǎng)絡(luò)初始化。根據(jù)樣本特征確定網(wǎng)絡(luò)結(jié)構(gòu)、期望輸出、學(xué)習(xí)速率，接收遺傳算法優(yōu)化得到的最優(yōu)解個體作為網(wǎng)絡(luò)的初始權(quán)值和閾值。

（2）輸入訓(xùn)練樣本，計(jì)算網(wǎng)絡(luò)各層輸出。

（3）計(jì)算網(wǎng)絡(luò)學(xué)習(xí)誤差。

（4）修正各層連接權(quán)值和閾值。

（5）判斷誤差是否滿足期望的要求或訓(xùn)練達(dá)到設(shè)置的迭代次數(shù)，如滿足條件，則訓(xùn)練結(jié)束，否則，繼續(xù)迭代學(xué)習(xí)。

2 GA-BP神經(jīng)網(wǎng)絡(luò)算法并行化設(shè)計(jì)與實(shí)現(xiàn)

PSO-BP神經(jīng)網(wǎng)絡(luò)算法雖然改善了傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)算法的性能，但隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練時間會很長，效率問題逐漸暴露。MapReduce并行編程框架為大數(shù)據(jù)的處理提供了一種分布式并行計(jì)算環(huán)境，為提高BP神經(jīng)網(wǎng)絡(luò)的時間效率和測試準(zhǔn)確率，本文對PSO-BP神經(jīng)網(wǎng)絡(luò)算法在MapReduce框架下進(jìn)行了并行化設(shè)計(jì)。

2.1 MapReduce編程模型

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

2.2 遺傳算法并行化設(shè)計(jì)及實(shí)現(xiàn)

2.2.1 GA-Map（）設(shè)計(jì)及實(shí)現(xiàn)

根據(jù)MapReduce編程模型的數(shù)據(jù)輸入格式，本文也將遺傳算法輸入的數(shù)據(jù)轉(zhuǎn)化為的格式，其中，key代表個體的編號，value代表個體的屬性。Map階段，完成個體的初始化/適應(yīng)度評價(jià)以及形成個體種群的最優(yōu)個體等操作。遺傳算法的Map過程設(shè)計(jì)如下：

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

輸出：key，最優(yōu)個體集

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

{

對每個個體，獲取value值；

fit-value=fit（value）；//計(jì)算更新個體的適應(yīng)度值//迭代更新個體If（滿足條件）key=new-key（key）；輸出key，最優(yōu)個體集； }

2.2.2 GA-Reduce（）設(shè)計(jì)及實(shí)現(xiàn)

Reduce階段，接收Map任務(wù)生成的最優(yōu)個體集，對信息進(jìn)行整合，全局更新最優(yōu)個體集，如果達(dá)到終止條件，輸出整個種群的最優(yōu)個體。遺傳算法的Reduce過程設(shè)計(jì)如下：

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

當(dāng)遺傳算法并行迭代完成后，得到的最優(yōu)個體即為BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)值和閾值。

2.3 BP神經(jīng)網(wǎng)絡(luò)并行化設(shè)計(jì)及實(shí)現(xiàn)

為克服BP神經(jīng)網(wǎng)絡(luò)在樣本數(shù)量增多時硬件開銷大、訓(xùn)練時間長等缺陷，本文基于MapReduce模型對BP神經(jīng)網(wǎng)絡(luò)進(jìn)行了并行化設(shè)計(jì)，通過Map任務(wù)和Reduce任務(wù)實(shí)現(xiàn)多BP神經(jīng)網(wǎng)絡(luò)內(nèi)部的自動并行運(yùn)行，在大大縮短樣本訓(xùn)練時間的同時，進(jìn)而提高了訓(xùn)練的精度。其模型結(jié)構(gòu)如圖2所示。

2.3.1 BP-Map（）設(shè)計(jì)及實(shí)現(xiàn)

Map階段，Map任務(wù)根據(jù)輸入逐層計(jì)算網(wǎng)絡(luò)實(shí)際輸出，并將實(shí)際輸出與期望輸出相比較，計(jì)算網(wǎng)絡(luò)學(xué)習(xí)誤差，然后根據(jù)學(xué)習(xí)誤差計(jì)算網(wǎng)絡(luò)中各連接權(quán)值的更新量。BP神經(jīng)網(wǎng)絡(luò)的Map任務(wù)設(shè)計(jì)如下：輸入：樣本id，樣本特征值輸出：樣本對應(yīng)權(quán)值ω，權(quán)值更新量ΔωBP-Map（樣本id，樣本特征值）{//對每個樣本計(jì)算網(wǎng)絡(luò)各層輸出；

計(jì)算網(wǎng)絡(luò)學(xué)習(xí)誤差；對每個連接權(quán)值ω，計(jì)算權(quán)值更新量Δω；輸出（ω，Δω）； }

2.3.2 BP-Combine（）函數(shù)設(shè)計(jì)及實(shí)現(xiàn)

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

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

2.3.3 BP-Reduce（）設(shè)計(jì)及實(shí)現(xiàn)Reduce階段，接收Combine（）函數(shù)的輸出，然后統(tǒng)計(jì)所有權(quán)值相同樣本的總體更新量和平均更新量，并更新網(wǎng)絡(luò)權(quán)值。BP神經(jīng)網(wǎng)絡(luò)的Reduce任務(wù)設(shè)計(jì)如下：

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

3 實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證本文提出的并行GA-BP神經(jīng)網(wǎng)絡(luò)算法的性能，本文在Hadoop平臺下對大量圖像的分類效果進(jìn)行了測試。

3.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

實(shí)驗(yàn)環(huán)境是局域網(wǎng)內(nèi)5臺計(jì)算機(jī)構(gòu)成的Hadoop集群，1臺計(jì)算機(jī)做Master節(jié)點(diǎn)，其余4臺做Slave節(jié)點(diǎn)；所有節(jié)點(diǎn)配置都是4G雙核處理器、1T硬盤，操作系統(tǒng)是Ubuntu。

實(shí)驗(yàn)數(shù)據(jù)來自Caltech 256圖像庫，該圖像庫可供免費(fèi)使用，包含30 607幅、256個類別。

3.2 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證所提出算法的性能，本文從分類準(zhǔn)確率、加速比與效率等方面作了實(shí)驗(yàn)比較。

3.2.1 分類準(zhǔn)確率

本文在不同的圖像規(guī)模下，以訓(xùn)練樣本數(shù)與測試樣本數(shù)約4：1的比例，對傳統(tǒng)的GA-BP神經(jīng)網(wǎng)絡(luò)算法和本文提出的并行GA-BP神經(jīng)網(wǎng)絡(luò)算法就分類準(zhǔn)確率進(jìn)行比較。本文采用計(jì)算機(jī)隨機(jī)結(jié)合人工選擇構(gòu)造了5個數(shù)據(jù)集Data1、Data2、Data3、Data4和Data5。其中，Data1包含了3個類別的300幅場景圖像，Data2包含了5個類別的800幅場景圖像，Data3包含了8個類別的2 000幅場景圖像，Data4包含了12個類別的5 000幅圖像，Data5包含了15個類別的15 000幅場景圖像。實(shí)驗(yàn)結(jié)果如表1所示。

從表1可以明顯看到，本文算法分類效果明顯優(yōu)于傳統(tǒng)的GA-BP神經(jīng)網(wǎng)絡(luò)算法，而且，隨著數(shù)據(jù)規(guī)模的增大，雖然兩種算法的分類準(zhǔn)確率都在降低，但本文提出的并行GA-BP神經(jīng)網(wǎng)絡(luò)算法顯然沒有下降到很低。這充分說明，基于MapReduce并行編程模型的算法在大規(guī)模數(shù)據(jù)集下的優(yōu)越性非常明顯。

3.2.2 加速比與效率

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

從圖3可以看出，加速比在隨著計(jì)算節(jié)點(diǎn)數(shù)的增加呈增長趨勢，而且數(shù)據(jù)規(guī)模越大，加速比增長的幅度越大，這也進(jìn)一步說明越大規(guī)模的數(shù)據(jù)集才越能充分發(fā)揮多個計(jì)算節(jié)點(diǎn)的性能。從圖4中系統(tǒng)效率對比可以看出，數(shù)據(jù)集小的效率低于數(shù)據(jù)集大的效率，而且隨著計(jì)算節(jié)點(diǎn)數(shù)的增加，數(shù)據(jù)集規(guī)模較小時，系統(tǒng)效率下降較快，而當(dāng)數(shù)據(jù)集規(guī)模不斷增大時，隨著計(jì)算節(jié)點(diǎn)個數(shù)增多，系統(tǒng)效率雖有降低，但下降幅度較小。系統(tǒng)效率的下降主要是因?yàn)橐环矫鏀?shù)據(jù)規(guī)模增大，系統(tǒng)處理的時間會增多，另一方面，隨著計(jì)算節(jié)點(diǎn)數(shù)的增加，節(jié)點(diǎn)間的通行開銷也會增加，但系統(tǒng)效率一直都在0.5以上，說明算法具有很好的并行性能和可擴(kuò)展性能。

4 結(jié)語

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

參考文獻(xiàn)：

[1] 胡月.BP算法并行化及在數(shù)據(jù)挖掘中的應(yīng)用研究[D].重慶：重慶大學(xué)，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īng)網(wǎng)絡(luò)的房價(jià)預(yù)測分析[J].計(jì)算機(jī)工程，2014，40（4）：187-191.

[4] 王改革，郭立紅，段紅，等.基于螢火蟲算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的目標(biāo)威脅估計(jì)[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，2013，43（4）：1064-1069.

[5] 鄭曉薇，李玉丹，馬名威.MPI 集群環(huán)境下圖像語義分類算法的并行化設(shè)計(jì)[J].小型微型計(jì)算機(jī)系統(tǒng)，2014，35（6）：1348-1352.

[6] 劉晶.基于PVM的并行計(jì)算[J].廣東石油化工學(xué)院學(xué)報(bào)，2012，12（4）：34-35.

[7] 趙玖玲，衛(wèi)海鵬.基于MPI的并行遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)，2006，33（9）：186-189.

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

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