基于Spark的并行遺傳算法求解多峰函數(shù)極值

劉 鵬，葉 帥，孟 磊，王 燦

(1.中國礦業(yè)大學物聯(lián)網(wǎng)(感知礦山)研究中心，江蘇 徐州 221008；2.礦山互聯(lián)網(wǎng)應用技術國家地方聯(lián)合工程實驗室，江蘇 徐州 221008；3.中國礦業(yè)大學信息與控制工程學院，江蘇 徐州 221116；4.華東計算技術研究所航天產(chǎn)品部，上海 201808)

1 引言

遺傳算法GA(Genetic Algorithm)是模擬生物的遺傳進化和自然選擇發(fā)展而來的一種自適應概率的全局優(yōu)化搜索算法，其具有設計思想簡潔、易于實現(xiàn)、效果明顯等優(yōu)點，故已在眾多領域廣泛應用[1]。但是，由于當今數(shù)據(jù)海量增長，在種群數(shù)量和迭代次數(shù)大幅提高的大數(shù)據(jù)時代，單機遺傳算法在多峰函數(shù)求極值中往往出現(xiàn)運算效率低下、容易過早收斂得到局部極值等現(xiàn)象，這極大地限制了遺傳算法的實際應用。然而，遺傳算法所進行的運算操作都是以個體的集合即種群為單位進行的，對于每個個體都具有一定的并行性，故遺傳算法具有天然的并行性，當處理大規(guī)模數(shù)據(jù)集時，各個子種群間可實現(xiàn)高度的并行化運算[2,3]。

Hadoop[4]分布式計算框架最核心的設計是HDFS (Hadoop Distributed File System)和MapReduce，用戶能輕易地使用Hadoop開發(fā)包括GA在內(nèi)的分布式復雜程序并充分發(fā)揮集群的性能進行高速運算和存儲，如[5]基于MapReduce的粗粒度遺傳算法并行化研究和實現(xiàn)，一定程度上提高了GA的運算效率。但是，由于Hadoop的MapReduce[6]計算框架在兩個任務之間仍需通過不斷讀寫磁盤來進行迭代運算，因此耗費了大量時間，運算效率仍有很大提升空間。

Spark[7]是一個基于內(nèi)存計算的開源分布式并行計算框架，支持在大數(shù)據(jù)集上進行復雜的查詢、流計算及分類挖掘等，能夠輕量級地快速處理。Spark特有的彈性分布式數(shù)據(jù)集RDD(Resilient Distributed Datasets)運算機制，使得每次迭代的中間結果可保存在內(nèi)存中直接供下一次的迭代運算調(diào)用，從而顯著提高了GA過程中多次迭代運算的效率。而且，種群多節(jié)點并行數(shù)據(jù)處理帶來的優(yōu)良的天然隨機性可有效避免GA過早收斂現(xiàn)象。

本文主要貢獻在于基于Spark平臺的RDD計算模型設計并實現(xiàn)了并行化遺傳算法，進行了以200 000對大數(shù)據(jù)樣本為基礎求解舒伯特(Shubert)多峰函數(shù)最大值的研究，并通過與基于單機和Hadoop的GA算法相比較，驗證基于Spark平臺的并行GA算法執(zhí)行時間的高效率和求極值的準確率。

后續(xù)內(nèi)容安排如下：第2節(jié)介紹單機GA求解多峰函數(shù)極值的算法設計；第3節(jié)介紹基于Hadoop的GA求解多峰函數(shù)極值設計及實現(xiàn)；第4節(jié)介紹基于Spark的GA求解多峰函數(shù)極值設計及實現(xiàn)；第5節(jié)在相同數(shù)據(jù)集上對基于Hadoop和Spark平臺的并行GA算法進行性能比較；第6節(jié)是總結和展望。

2 多峰函數(shù)求極值的單機遺傳算法

2.1 Shubert多峰函數(shù)

多峰函數(shù)是指存在多個峰值點的函數(shù)。本文以Shubert函數(shù)[8]為例，該函數(shù)是一個典型的多峰函數(shù)。根據(jù)Matlab的分析，在-10到10的區(qū)間上，該函數(shù)有760個局部最大值，18個全局最大值。其Matlab的仿真圖如圖1所示，函數(shù)形式如下：

-10

Figure 1 Shubert function simulation圖1 Shubert函數(shù)仿真圖

在實際應用中，對于具有多個峰值的函數(shù)往往要求取全局最大值及備選的局部最大值，而傳統(tǒng)求極值算法通常效率緩慢，準確率低，且容易陷入局部最優(yōu)的困境。

2.2 單機遺傳算法求解多峰函數(shù)極值

遺傳算法是借鑒生物進化過程發(fā)展而來的一種全局搜索尋優(yōu)策略，相比較其他傳統(tǒng)尋優(yōu)算法，更加適合解決多峰函數(shù)求極值問題。

多峰函數(shù)求極值的單機GA算法具體流程(見圖2)如下所示：

Figure 2 Stand-alone genetic algorithm圖2 單機遺傳算法求解流程圖

(1)種群初始化：隨機產(chǎn)生-10～10的200 000對隨機數(shù)，然后映射到0～2 048，生成22位二進制編碼，不足的部分首位補0。

(2)計算適應度：考慮到個體適應度為非負值，對Shubert函數(shù)做線性非負轉換，計算出個體所對應的適應度。

(3)交叉：隨機兩兩配對種群個體，按交叉概率執(zhí)行單點交叉。

(4)變異：遍歷每個個體的每位基因座，對符合變異概率的基因座取反。

(5)選擇：計算每個個體的選擇概率及對應的累積概率，進行輪盤賭選出下一代。

(6)結果輸出：滿足優(yōu)化準則結束，最優(yōu)種群通過解碼函數(shù)獲得對應函數(shù)值群，輸出其最大值。

由于單機GA求解多峰函數(shù)極值是串行運算的，所以其交叉、變異及選擇操作皆在全部種群中進行。在全部種群中進行選擇時易淘汰掉優(yōu)秀個體而過早收斂，且進化后期尋優(yōu)效率低下。但是，將全部種群分散在多個子種群中進行進化操作時，即使某個子種群的優(yōu)秀個體被淘汰后，其他子種群仍有極大可能存在其優(yōu)秀個體進行后續(xù)操作，可一定程度上防止過早收斂得到局部最優(yōu)值的現(xiàn)象發(fā)生。雖然目前已出現(xiàn)大量優(yōu)化改進思想[9]，基于分布式集群并行實現(xiàn)是其中一種更有效的方式。

3 基于Hadoop的并行遺傳算法求解多峰函數(shù)極值

為了和基于Spark的新一代并行GA算法作對比，我們首先設計并實現(xiàn)了基于Hadoop[10]的并行GA算法。基本思路是：把單機串行進行的迭代運算轉化成一次次的MapReduce操作。具體過程如圖3所示。

Figure 3 Genetic algorithm based on Hadoop圖3 基于Hadoop并行化GA流程圖

3.1 進化過程的設計

首先從HDFS中讀取初始種群individuals，將其切分為多個子種群splits，然后計算各個子種群個體的Shubert函數(shù)值，將函數(shù)值作為個體適應度fitness，并以鍵值對〈individuals,fitness〉形式作為輸入，在每個split上創(chuàng)建各自獨立的MapReduce任務，進行交叉、變異、選擇，將進化后的個體鍵值對〈individuals,fitness〉存入HDFS中。偽代碼如下：

Begin

迭代次數(shù)t=0；

while (t≤T) do

Input 預存的樣本集;

Step 1.切分種群給各節(jié)點;

Step 2.計算個體適應度fitness;

Step 3.map成鍵值對〈individuals,fitness〉作為進化輸入;

Step 4. for 每個個體ido

交叉;

變異;

選擇;

end fori

Step 5. 覆蓋迭代后的種群;

t=t+1;

end while

Output：進化后的〈individuals,fitness〉。

3.2 尋優(yōu)過程的設計

在求最優(yōu)階段，主要是判斷終止條件，搜索種群的最大值。在滿足終止條件時，解碼種群獲取Shubert函數(shù)值群，對函數(shù)值群進行排序，輸出所求函數(shù)的全局最大值及其對應的變量值。偽代碼如下：

Input：進化后的種群。

Begin

Step 1.將個體individual執(zhí)行解碼操作;

Step 2.將Shubert函數(shù)值和對應變量map成鍵值對〈value,(x,y)〉;

Step 3.利用reduceByKey對鍵值對的value排序;

Output：全局最大值及對應變量。

迭代過程中，Reduce函數(shù)的默認操作會對進化后的種群進行排序，并以默認的文本名進行覆蓋存儲，該操作基本上打亂了種群之前的排序，在再次迭代讀取時大大增加了其隨機性，該設計相比于其他HadoopGA實現(xiàn)，其優(yōu)勢在于有效避免了局部最優(yōu)，提高了求值準確性，與下文SparkGA實現(xiàn)的結果對比更具說服力。

4 基于Spark的并行GA算法求解多峰函數(shù)極值

由于MapReduce沒有內(nèi)存運算機制[11]，每次迭代都需要從磁盤中重新讀取種群數(shù)據(jù)，從而增加了算法耗時，沒有充分發(fā)揮GA的并行潛能。和以MapReduce為核心設計的并行GA算法不同，基于Spark的GA算法并行化設計主要是依賴Spark所特有的RDD來進行GA構建、切分和并行化處理。

彈性分布式數(shù)據(jù)集RDD是一種具備高效容錯性的分布式彈性存儲系統(tǒng)，它將大量數(shù)據(jù)分布式存儲在不同計算節(jié)點的本地內(nèi)存中，然后在分布式集群上執(zhí)行基于內(nèi)存的并行計算[12]。RDD的操作主要分為兩類：(1)Transformation(轉化)，其功能是從現(xiàn)有的RDD創(chuàng)建出一個新的RDD；(2)Action(動作)，其功能是在RDD上對數(shù)據(jù)集進行實際的并行計算，然后返回給主控程序一個最終的可顯示或存儲的簡單結果。但是，RDD中的Transformation是延遲執(zhí)行(Lazy Execution)的，其通常在遇到下一個具體Action時才把前期積累的Transformations按序觸發(fā)執(zhí)行，如圖4所示。

Figure 4 Spark operating mechanism圖4 Spark執(zhí)行機制示意圖

為了與基于Hadoop的并行算法作對比，采用相同的數(shù)據(jù)集進行GA操作。結合RDD的特點，基于Spark的GA并行化實現(xiàn)主要分為進化和尋優(yōu)兩個階段。

整體流程如圖5所示，其過程如下：(1)從HDFS中讀取與上部分Hadoop實驗相同的200 000條二進制編碼作為初代種群；(2)使用Spark的APIs函數(shù)MapToPair進行各子種群內(nèi)個體的交叉、變異操作，利用Map操作進行個體選擇概率的計算，再采用循環(huán)執(zhí)行Map進行選擇；(3)判斷終止條件，對最優(yōu)值解碼排序獲得函數(shù)最大值。

Figure 5 Genetic algorithm based on Spark圖5 基于Spark的并行化GA流程圖

4.1 進化過程的設計

進化過程主要分為四個操作，均是在RDD模型內(nèi)實現(xiàn)的。Spark和HDFS高度兼容，使得可以對存儲于HDFS中的文本數(shù)據(jù)進行逐行處理，所以我們將初始種群按每個個體樣本逐行存儲于HDFS上。

(1)交叉操作：讀取全局列表樣本，隨機分配到各個節(jié)點，在每個節(jié)點上創(chuàng)建RDD，再通過take函數(shù)全部采樣，平均存儲到兩個列表中。兩個列表利用parallelize函數(shù)再次生成兩個RDD，通過組成K-V鍵值對的形式來實現(xiàn)兩個父代的隨機配對，如圖6所示。

Figure 6 Random match process圖6 隨機配對過程

然后利用Map函數(shù)逐條對鍵值對〈individual,individual〉的鍵和值進行單點交叉操作，再分別提取交叉后的鍵和值，通過Map合并創(chuàng)建出交叉后的種群RDD，存于內(nèi)存中，如圖7所示。

Figure 7 Crossover process圖7 交叉操作過程

(2)變異操作：對交叉后的種群RDD使用Map操作，逐條讀取種群個體individual，遍歷每個個體編碼的每一位基因座。通過產(chǎn)生隨機數(shù)的方式來判斷其個體編碼是否滿足變異條件，個體編碼中對滿足變異條件的基因座進行取反操作，從而產(chǎn)出一個新的個體對象；否則直接輸出該個體編碼。最后生成變異后的種群RDD，存于內(nèi)存中，如圖8所示。

Figure 8 Mutation process圖8 變異操作過程

(3)計算個體適應度：根據(jù)Shubert函數(shù)，計算變異后RDD中個體對應的適應度。將個體編碼和適應度組成鍵值對，以〈individuals,fitness〉的形式保存到新的RDD中。

(4)選擇操作：在各個節(jié)點上進行自然選擇，結合Map遍歷所有鍵值對的特點，在每次選擇過程中，由適應度值來判斷選擇，挑出滿足進入下一代條件的個體，生成優(yōu)勝劣汰后的新種群RDD，存于內(nèi)存中。為避免局部最優(yōu)，自然選擇完成后合并所有RDD，在主節(jié)點上對所有的數(shù)據(jù)(本設計采用的數(shù)據(jù)量為200 000條)執(zhí)行重排序操作，然后判斷終止條件，進入下一步操作。

4.2 尋優(yōu)過程的設計

求最終代群體中的最優(yōu)解如圖9所示。若迭代次數(shù)滿足設定的終止條件，對最終生成的RDD實行Map操作。在Map操作中，定義變量解碼函數(shù)并求解Shubert函數(shù)值，將獲得的多個極值和對應變量以鍵值對的形式進行存儲，具體格式為〈value,(xy)〉。通過reduceByKey對鍵值對的鍵進行排序，將其存儲到HDFS中，輸出Shubert函數(shù)的最大值及其對應的變量值，結束。

Figure 9 Solving Shubert function based on RDD圖9 基于RDD尋優(yōu)Shubert函數(shù)極值

5 實驗與分析

實驗主要從兩個方面進行驗證分析：

(1)高效性：對比Local、Hadoop和Spark平臺下GA的運算耗時、加速比、平均迭代耗時，驗證基于Spark平臺并行GA算法的高效性；

(2)準確率：對比不同迭代次數(shù)下求解Shubert函數(shù)的極值結果，檢驗基于分布式平臺的并行GA尋優(yōu)結果的準確率和穩(wěn)定性。

5.1 環(huán)境搭建

本實驗平臺的集群由1個主節(jié)點(Master)和19個從節(jié)點(Slave)組成，具體配置參見表1。實驗中各平臺采用相同的樣本數(shù)據(jù)集。

Table 1 Configuration of experiment cluster

本文遺傳算法的核心參數(shù)設置如下：

(1)NIND=200000;/*種群規(guī)模(Number of Individuals)*/

(2)PRECI=22;/*變量二進制位數(shù)(Precision of Variables)*/

(3)PC=0.9;/*交叉概率(Probability of Crossover)*/

(4)PM=0.05;/*變異概率(Probability of Mutation)*/

5.2 單機和分布式遺傳算法效率比較

從表2中可以直觀地看出，在相同的GA運算任務下，基于分布式平臺的實現(xiàn)運算效率要明顯高于單機實現(xiàn)。在間隔為20代的迭代運算中，隨著迭代次數(shù)的增加，分布式系統(tǒng)的遺傳算法運行效率會遠遠高于單機系統(tǒng)；同時從圖10中可以看出，各個平臺上的迭代次數(shù)和運算時間均呈線性分布，在分布式算法實現(xiàn)中，基于Hadoop的運行耗時也顯著多于Spark十余倍，并且從兩條曲線運行時間的趨勢可看出，隨著迭代次數(shù)的增加，基于Spark實現(xiàn)的迭代執(zhí)行效率越來越高，領先基于Hadoop實現(xiàn)的差距亦越來越大。

Table 2 Time-consuming comparison of GA iterations based on Hadoop and Spark

Figure 10 Time-consuming comparison of GA iterations based on Hadoop and Spark圖10 基于Hadoop和Spark的GA迭代耗時比較

5.3 單機和分布式遺傳算法準確率比較

為保證最終求極值結果的準確性，降低異常值的影響，實驗中取10次運算結果的平均值作為分析對象。遺傳算法容易陷入局部最優(yōu)解的主要原因是，在于單一種群中，局部最優(yōu)解附近的個體被選擇的概率高，在歷經(jīng)多次迭代后樣本皆容易集中在同一局部最優(yōu)解附近，限制后續(xù)搜索空間的大小。而切分為多種群后，可讓各個局部最優(yōu)解附近都存在樣本，從而盡可能增大后續(xù)搜索空間。故從圖11中可以明顯地看出，在相同迭代次數(shù)的條件下，單機函數(shù)結果相對不穩(wěn)定，與基于分布式平臺的結果差值較大，多次得到局部最大值，只有在迭代次數(shù)大到一定程度(90次)才緩慢趨于穩(wěn)定。而分布式系統(tǒng)中的函數(shù)結果變化幅度很小，和迭代次數(shù)關系不大，開始時就接近準確值，且隨著迭代次數(shù)越多，越趨于Shubert函數(shù)的準確值，其準確率顯著高于單機結果。該結果說明了并行化運算帶來的高度隨機性能使GA運算充分挖掘算法的“遺傳”潛能,有效避免局面最優(yōu)，顯著提高多峰函數(shù)求極值的準確率和穩(wěn)定性。

Figure 11 Comparison of extreme value of Shubert function圖11 Shubert函數(shù)求極值結果對比

5.4 基于Hadoop和Spark的遺傳算法加速比分析

加速比是衡量在同規(guī)模任務下系統(tǒng)的性能優(yōu)劣的重要指標。加速比越大，對應平臺相對于單機系統(tǒng)的效率和性能提升就越大。其計算公式為Sp=T1/Tp，其中，Sp是加速比，T1是單機執(zhí)行GA耗時，Tp是分布式平臺執(zhí)行相同任務的耗時。

MapReduce是一種批量處理引擎，需要從磁盤中讀取數(shù)據(jù)，然后對數(shù)據(jù)執(zhí)行操作，將結果寫回到磁盤。迭代進化需要不斷地讀取磁盤占用大量時間，而Spark將數(shù)據(jù)集緩存在內(nèi)存中，執(zhí)行類似的操作是在內(nèi)存中一步執(zhí)行，故其運算速率大大提升。圖12為Hadoop和Spark兩個平臺在不同迭代次數(shù)下的加速比分布，可直觀地看出，Spark平臺的加速比要明顯高于Hadoop，Spark的平均加速比約為194.4，Hadoop的平均加速比約為13.9，這說明Spark在GA運算方面具有顯著優(yōu)于Hadoop的加速比。

Figure 12 Comparison of GA speedup ratio based on Spark and Hadoop圖12 基于Spark和Hadoop的GA算法加速比

5.5 基于Hadoop和Spark的遺傳算法單次迭代耗時分析

通過對比每代進化平均耗時來進一步分析Hadoop和Spark兩個大數(shù)據(jù)平臺在處理遺傳算法的大規(guī)模迭代運算時的性能。

從圖13中不同進化代數(shù)的兩個平臺耗時分布可看出，基于兩個分布式平臺下的GA迭代運算時，隨著進化代數(shù)增加，在迭代次數(shù)超過80次后，每代的進化耗時趨于穩(wěn)定，Hadoop平臺下平均每代耗時3.09 s，而Spark平臺下的平均每代耗時為0.22 s，即在處理單次進化運算上，Spark平臺要比Hadoop平臺快2.87 s，效率提升了約13倍。

Figure 13 Time-consuming comparison of GA single iteration based on Hadoop and Spark圖13 基于Hadoop和Spark的GA單次迭代耗時對比

6 結束語

本文進行了基于Spark的并行遺傳算法求解多峰函數(shù)極值的研究。相比傳統(tǒng)單機及Hadoop平臺的實現(xiàn)，本文提出的并行遺傳算法在面對大數(shù)據(jù)樣本時，處理進化迭代的計算效率有顯著提升，同時由于算法本身具有的天然隨機性能夠有效避免局部最優(yōu)，因此也明顯提高了多峰函數(shù)求極值的準確性。未來我們考慮繼續(xù)在并行框架下將遺傳算法與機器學習算法進行融合應用研究。

[1] Goldberg D E.Genetic algorithms in search,optimization & machine learning[M].Boston:Addison Wesley,Publishing,1989.

[2] Corcoran A L,Wainwright R L.A parallel island model genetic algorithm for the multiprocessor scheduling problem[C]∥Proc of the 1994 ACM/SIGAPP Symposium on Applied Computing,1994:483-487．

[3] Cantu-Paz E.A survey of parallel genetic algorithms[J].Calculateurs Paralleles,Reseaux et Systems Repartis,1998,10(4):429-449．

[4] An Xiu-jun,Wang Peng,Jin Yu-chang.The basic and application of the big data processing technology based on Hadoop[M].Beijing:The People’s Posts and Telecommunications Press,2015:15-45.(in Chinese)

[5] Cheng Xing-guo，Xiao Nan-feng.Coarse-grained parallel genetic algorithm by MapReduce[J].Journal of Chongqing University of Technology(Natural & Science),2013,27(10):66-70.(in Chinese)

[6] Lam W, Liu L,Prasad S, et al. Muppet:MapReduce-style processing of fast data[J].PVLDB,2012,5 (12):1814-1825.

[7] Xia Jun-luan,Liu Xu-hui,Shao Sai-sai,et al.The big data processing technology based on Spark[M].Beijing:Electronic Industry Press,2015:22-48.(in Chinese)

[8] Gong Jia-fen,Zou Xiu-fen,Jin Hui.A dynamic two-level evolutionary algorithm for solving multi-modal function optimization problem[C]∥Proc of Progress in Intelligence Computation & Applications,2005:62-68.

[9] Tomassini M,Vanneschi L.Special issue on parallel and distributed evolutionary algorithms[J].Genetic Programming and Evolvable Machines,2009,10 (4):339-341.

[10] Verma A,Llor’a X,Goldberg D E,et al.Scaling genetic algorithms using MapReduce[C]∥Proc of the 9th International Conference on Intelligent Systems Design and Applications,2009:13-18.

[11] Dean J,Ghemawat S.MapReduce:Simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.

[12] Pentreath N.Machine learning based on Spark[M].Cai Li-yu, et al translation. Beijing:The People’s Posts and Telecommunications Press,2015:32-56.(in Chinese)

附中文參考文獻：

[4] 安俊秀,王鵬,靳宇倡.Hadoop大數(shù)據(jù)處理技術基礎與實踐[M].北京:人民郵電出版社,2015:15-45.

[5] 程興國,肖南峰.粗粒度并行遺傳算法的MapReduce并行化實現(xiàn)[J].重慶理工大學學報(自然科學),2013,27(10):66-70.

[7] 夏俊鸞,劉旭輝,邵賽賽,等.Spark大數(shù)據(jù)處理技術[M].北京:電子工業(yè)出版社,2015.

[12] Pentreath N.Spark機器學習[M].蔡立宇等,譯.北京:人民郵電出版社,2015:32-56.