GOP-MRPGA：基于MapReduce大數(shù)據(jù)計算模型的遺傳算子前置并行遺傳算法

任 剛，狄文輝，郜廣蘭，王鮮芳，吳長茂，武文佳，趙開新

（1.河南工學(xué)院 計算機(jī)科學(xué)與技術(shù)學(xué)院，河南 新鄉(xiāng) 453003;2.中國科學(xué)院軟件研究所 并行軟件與計算科學(xué)實(shí)驗(yàn)室,北京 100190;3.新鄉(xiāng)市制造業(yè)物聯(lián)網(wǎng)應(yīng)用工程技術(shù)研究中心，河南 新鄉(xiāng) 453003）

0 引言

遺傳算法(Genetic Algorithm,GA)[1-3]是一種模擬自然界生物過程的全局搜索算法。該算法通常將問題空間抽象為一個種群，通過在種群個體上進(jìn)行選擇、交叉和變異等遺傳算子操作產(chǎn)生新一代種群。經(jīng)過多次迭代，最終種群趨向收斂。由于該算法在全局并行搜索上表現(xiàn)出的高效性、簡單性和魯棒性等優(yōu)點(diǎn)，被應(yīng)用于諸多領(lǐng)域。

近年來，隨著大數(shù)據(jù)時代的到來，MapReduce[4]大數(shù)據(jù)并行計算模型受到廣泛關(guān)注，成為業(yè)界研究和應(yīng)用的一個熱點(diǎn)[5-7]。該模型把數(shù)據(jù)處理抽象為Map和Reduce兩個階段，其中Map負(fù)責(zé)并行處理輸入數(shù)據(jù)，1個計算節(jié)點(diǎn)往往部署多個Map任務(wù)，從而加速數(shù)據(jù)處理速度。Reduce接收來自Map任務(wù)的數(shù)據(jù)，并規(guī)約匯總，得到最終結(jié)果。對大多數(shù)應(yīng)用來說，Reduce的數(shù)量往往遠(yuǎn)小于Map數(shù)量。MRPGA（MapReduce-based PGA）[8-11]算法是一種基于MapReduce計算模型的并行遺傳算法(Parallel Genetic Algorithm,PGA)。由于該算法綜合了MapReduce在大數(shù)據(jù)處理方面的優(yōu)勢和PGA在全局搜索方面的優(yōu)勢，因此得到了廣泛應(yīng)用。但是，由于該算法將遺傳算子集中到Reduce階段，容易造成性能瓶頸，因此，在數(shù)據(jù)規(guī)模較大時，其計算性能仍偏低。

為此，提出一種新的MRPGA算法——遺傳算子前置MRPGA算法GOP-MRPGA (Genetic Operator Pre-posed MRPGA），并通過數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證提出算法的有效性。

1 MapReduce大數(shù)據(jù)編程模型

MapReduce是一種專門處理大數(shù)據(jù)的并行計算模型，數(shù)據(jù)以分片形式存儲在集群計算節(jié)點(diǎn)上。如圖1所示，整個計算過程可分為Map和Reduce兩個階段。在Map階段，每個計算節(jié)點(diǎn)啟動若干Map任務(wù)，每個Map任務(wù)并行讀取數(shù)據(jù)分片，并把分片中的每行數(shù)據(jù)都分解為鍵值對(key1,value1)，key1默認(rèn)設(shè)置為行號，value1為每行數(shù)據(jù)的實(shí)際內(nèi)容。然后，按照具體業(yè)務(wù)邏輯將其轉(zhuǎn)換為新的鍵值對(key2,value2)，Map處理邏輯表示如下：

在收到(key2,list(value2))后，Reduce任務(wù)按照具體業(yè)務(wù)邏輯進(jìn)行規(guī)約處理，并輸出(key3,value3)，其邏輯表示如下：

圖1 MapReduce大數(shù)據(jù)計算模型

2 算法實(shí)現(xiàn)

經(jīng)典MRPGA算法[9]的實(shí)現(xiàn)如圖2所示。種群初始化(Initialization of population)操作被映射到Main函數(shù)中，適應(yīng)度評估(Evaluation)操作被映射到Map階段，選擇(Selection)，交叉(Crossover)和變異(Mutation)遺傳算子被映射到Reduce階段。不難看出，該算法通過Map階段中多個Map任務(wù)并行處理種群個體的適應(yīng)度評估操作來提高計算效率，該方式在一定程度上提高了串行遺傳算法的計算效率。然而，這種映射關(guān)系有一個明顯缺點(diǎn)：Reduce階段包含了選擇、交叉和變異等大部分遺傳算子，在整個計算過程中，承擔(dān)的計算量較大。我們知道，在MapReduce計算框架中，Reduce任務(wù)主要負(fù)責(zé)規(guī)約Map任務(wù)計算結(jié)果，因此Map數(shù)通常小于Map任務(wù)數(shù)。在這種情況下，當(dāng)遺傳算法種群規(guī)模較大、Map任務(wù)數(shù)較多時，Reduce階段容易成為系統(tǒng)性能瓶頸。

為解決上述問題，本文算法采用一種新的映射關(guān)系，如圖3所示。與經(jīng)典MRPGA算法相同的是：遺傳算法1次迭代也被封裝為1個單獨(dú)的MapReduce作業(yè)，種群的初始化操作由主函數(shù)來實(shí)現(xiàn)。與經(jīng)典MRPGA算法不同的是，遺傳算法的適應(yīng)度評估、選擇、交叉和變異等操作都被分配到Map階段來完成。Reduce階段僅負(fù)責(zé)收集各Map任務(wù)送來的新個體，而后選擇出最優(yōu)個體，判斷收斂條件并輸出新種群。這種方式的Reduce階段包含較少的計算。在處理大規(guī)模神經(jīng)網(wǎng)絡(luò)時，該階段不易形成系統(tǒng)性能瓶頸。

3 性能驗(yàn)證

采用OneMax問題[12]作為評價準(zhǔn)則。該問題用于最大化一個二進(jìn)制串中1的個數(shù)。采用Hadoop 2.7集群系統(tǒng)，該集群包含8個計算節(jié)點(diǎn)，每節(jié)點(diǎn)運(yùn)行1個4組雙核Intel Quad CPU。

3.1 收斂性

該實(shí)驗(yàn)用于驗(yàn)證本文提出的GOP-MRPGA算法與經(jīng)典MRPGA算法的收斂性能。每個Map包含1000個個體，共啟動8個Map任務(wù)，Reduce任務(wù)個數(shù)設(shè)置為10。實(shí)驗(yàn)共運(yùn)行350次迭代，并記錄下每次迭代種群個體中數(shù)字1的總數(shù)量。如圖4所示，經(jīng)典MRPGA算法在150代左右就開始收斂，本文算法直到200代左右才開始收斂，并且本文算法在收斂時種群質(zhì)量要明顯高于經(jīng)典MRPGA算法，說明本文算法具有較好的收斂精度。

3.2 Reduce數(shù)量擴(kuò)展性

該實(shí)驗(yàn)用于比較Reduce數(shù)量對算法性能的影響。個體總數(shù)為10,000，每個Map包含1000個遺傳個體。Reduce任務(wù)從1增加到8。如圖5所示，隨著Reduce數(shù)量增加，兩種算法計算時間都逐步減少，本文算法計算時間總是小于經(jīng)典MRPGA算法，這說明本文算法的有效性。其次，當(dāng)Reduce數(shù)量較少時，兩種算法計算時間差異較大，其原因是本文算法Reduce包含更少的計算，即使Reduce任務(wù)數(shù)量被設(shè)置得非常小，對本文算法影響也不太大。

圖2 經(jīng)典MRPGA映射關(guān)系

圖3 GOP-MRPGA映射關(guān)系

3.3 Map數(shù)量擴(kuò)展性

該實(shí)驗(yàn)用于比較本文算法與經(jīng)典MRPGA算法在任務(wù)負(fù)載恒定情況下的擴(kuò)展性，每個Map保持1000個個體。Reduce任務(wù)數(shù)量設(shè)置為10，將Map數(shù)量從10增加到80。如圖6所示，對于兩種算法，每次迭代時間增加到500秒后會保持一段時間，這是因?yàn)殡S著Map任務(wù)數(shù)量的增加，更多的資源會被添加進(jìn)來，整體計算時間變動不大。另外，隨著Map數(shù)量增加，兩種算法計算時間差逐漸增加，說明本文算法具有較好的擴(kuò)展性。

3.4 總負(fù)載恒定Map任務(wù)數(shù)量擴(kuò)展性

該實(shí)驗(yàn)用于比較兩種算法在總負(fù)載恒定時增加Map數(shù)量對系統(tǒng)性能的影響。Reduce任務(wù)數(shù)量固定為10。種群個體數(shù)量為80,000，Map任務(wù)數(shù)從10增加到80。如圖7所示，當(dāng)Map數(shù)量較少時，兩種算法計算時間相差不大；然而，隨著Map數(shù)量增加，本文算法下降幅度遠(yuǎn)遠(yuǎn)大于經(jīng)典MRPGA算法，其原因在于本文算法能夠利用多種群并行進(jìn)化機(jī)制加快收斂速度。

圖4 收斂性比較

圖5 Reduce數(shù)量擴(kuò)展性比較

圖6 Map任務(wù)數(shù)量擴(kuò)展性比較

圖7 總負(fù)載恒定Map數(shù)量擴(kuò)展性比較

4 結(jié)論

提出的一種遺傳算子前置的MRPGA算法GOP-MRPGA。經(jīng)實(shí)驗(yàn)驗(yàn)證，該算法具有較高的收斂速度和計算效率。今后的工作是研究在其他大數(shù)據(jù)計算平臺上實(shí)現(xiàn)該算法的可能性。